Connector Problems and Shortest Path Revision Notes for HSC SSCE Mathematics Standard

Connector Problems and Shortest Path

What are connector problems?

A connector problem involves finding the most economical way to link all locations or objects in a network. These problems use minimum spanning trees to work out the least total weight needed to keep all vertices connected together.

chatImportant

Definition: A connector problem uses a minimum spanning tree to find the least cost to link locations or objects.

The minimum spanning tree represents the smallest possible total weight that connects all vertices in the graph. When the edges of a network represent costs (such as the expense of laying cables or pipes), the total weight of the minimum spanning tree shows the minimum cost to connect all the locations.

infoNote

Real-world applications:

Connecting towns to a gas pipeline
Providing power supply to multiple locations
Installing telecommunications cables
Building road or rail networks
Any situation where you need to link all points with minimum expense

The key characteristic of connector problems is that all vertices must be connected using the minimum possible total cost.

Solving connector problems

Connector problems are solved by finding the minimum spanning tree of the network. This can be done using Prim's algorithm.

lightbulbExample

Worked Example: Connecting locations to power

Problem: There are $11$ locations that need access to power. The diagram shows possible cable connections between adjacent locations. The numbers indicate the minimum length of cable (in metres) required to connect these locations. Find the minimum length of cable needed to provide power to each location.

Solution:

The cables will be a minimum length if they are placed on the edges of the minimum spanning tree for the network.

Step 1: Choose a good starting point for Prim's algorithm. A vertex that is connected by just one edge is ideal, as this edge must be included in the minimum spanning tree.

Step 2: Follow Prim's algorithm to build the minimum spanning tree by repeatedly adding the edge with the smallest weight that connects a new vertex to the tree.

Step 3: Calculate the length of the minimum spanning tree by adding up the weights of all the selected edges:

$\text{Length} = 60 + 60 + 40 + 60 + 50 + 40 + 50 + 60 + 40 + 50$

$= 510 \text{ m}$

Answer: The minimum length of cable needed is $510$ metres.

This example demonstrates how minimum spanning trees provide practical solutions to real-world connection problems by minimising the total cost or length required.

Understanding shortest path problems

The shortest path in a network is the route between two specific vertices where the sum of the edge weights is minimised.

chatImportant

Definition: The shortest path between two vertices in a network is the path where the sum of the weights of its edges is minimised.

Finding the shortest path is useful in many practical situations:

If weights represent time, you can choose a route that minimises travel time
If weights represent distance, you can find the route with the shortest distance
Weights could also represent cost, fuel consumption, or other measures

chatImportant

Distance vs time: Be aware that travelling the shortest distance is not necessarily the quickest route. For example, if the shortest path has a speed limit of $60$ km/h but another path has a speed limit of $110$ km/h, the shortest path may actually take longer. In such cases, you should redraw the network diagram using time values for each edge instead of distance values.

infoNote

Key characteristics of shortest paths:

The shortest path connects two specific vertices (unlike connector problems which connect all vertices)
There can be more than one shortest path between two vertices
The shortest path may not pass through all vertices in the network
Multiple paths might have the same minimum length

Finding the shortest path by inspection

The method of inspection is a straightforward technique for finding the shortest path. It involves three steps:

List all likely shortest routes between the two vertices
Calculate the total length of each path
Compare the lengths and identify the shortest path

lightbulbExample

Worked Example 1: Finding the shortest path between two towns

Problem: Find the shortest path between Town C and Town F.

Solution:

Step 1: Identify all the likely shortest routes between Town C and Town F and work out their lengths.

Note: You can save time by eliminating any route that 'takes the long way around'. For example, when travelling from Town B to Town D, ignore the route via Town A because it's clearly longer.

Possible routes:

$C - D - E - F = 6 + 9 + 7 = 22$ km
$C - B - E - F = 5 + 4 + 7 = 16$ km
$C - B - A - F = 5 + 7 + 6 = 18$ km

Step 2: Compare the different path lengths and identify the shortest.

The route $C - B - E - F$ has a length of $16$ km, which is less than the other routes.

Answer: The shortest path is $C - B - E - F$ with a length of $16$ km.

lightbulbExample

Worked Example 2: Finding shortest paths to multiple destinations

Problem: Find the length of the shortest path from vertex A to each of the following vertices:

a) A and E
b) A and F
c) A and G
d) A and H

Solution:

Part a) Find the shortest path from A to E:

Looking at the network, the most direct route is:

$A - C - E = 6 + 5 = 11$

Part b) Find the shortest path from A to F:

The shortest route is:

$A - C - F = 6 + 6 = 12$

Part c) Find the shortest path from A to G:

The shortest route is:

$A - C - F - G = 6 + 6 + 8 = 20$

Part d) Find the shortest path from A to H:

The shortest route is:

$A - C - F - G - H = 6 + 6 + 8 + 10 = 30$

This example shows how to systematically find shortest paths from one vertex to multiple destinations by building up paths progressively.

lightbulbExample

Worked Example 3: Solving a time-based shortest path problem

Problem: Darcy has drawn a network diagram representing several streets for travelling from his home (vertex A) to the shops (vertex I). The numbers indicate travelling times in minutes. Find the shortest path and the minimum travelling time.

Solution:

Step 1: List all likely shortest routes between Home and Shops and calculate their times.

Possible routes:

$A - D - E - H - I = 1 + 2 + 3 + 5 = 11$ minutes
$A - D - G - H - I = 1 + 3 + 2 + 5 = 11$ minutes
$A - B - E - H - I = 2 + 1 + 3 + 5 = 11$ minutes
$A - B - C - F - I = 2 + 3 + 2 + 3 = 10$ minutes

Step 2: Compare the path lengths to identify the shortest.

Three routes have a time of $11$ minutes, but the route $A - B - C - F - I$ has a time of only $10$ minutes.

Answer: The shortest path is $A - B - C - F - I$ with a travelling time of $10$ minutes.

This example demonstrates that:

Multiple paths can have the same length (three paths each took $11$ minutes)
Careful checking of all possibilities is important to find the true shortest path
The shortest path doesn't necessarily go through the middle of the network

Remember!

bookmarkSummary

Key Points to Remember:

Connector problems use minimum spanning trees to find the minimum cost to connect all vertices in a network.
Shortest path problems find the route with minimum total weight between two specific vertices.
The method of inspection involves: List possible paths → Calculate each length → Compare to find shortest.
Shortest distance does not always mean shortest time - consider speed limits and redraw networks using time if needed.
There can be multiple shortest paths between two vertices, and the shortest path may not pass through all vertices in the network.

Connector Problems and Shortest Path (HSC SSCE Mathematics Standard): Revision Notes