Year 12 · Networks
Quick tips — memory joggers
Network terms
Degree & edges
Minimum spanning tree
Shortest path
Level 1 · Fluency
For the network shown, state the degree of vertex Q.
3
Q is connected to P, R and S, so its degree is 3.
A vertex in a network is joined by edges to five other vertices and has no other connections. State the degree of this vertex.
5
The degree of a vertex is the number of edges meeting it, so the degree is 5.
An edge in a directed network has an arrow drawn on it. What does the arrow tell you about travelling along that edge?
Travel is allowed in one direction only — the direction of the arrow.
An arrow marks a directed edge, meaning movement along it is permitted only in the direction of the arrow (a one-way connection).
Level 2 · Application
A tree is a connected network with no cycles. Explain whether the network above is a tree.
not
It is not a tree: P–Q–R–P forms a cycle, and a tree cannot contain a cycle.
A connected network has 6 vertices and 6 edges. Explain whether it can be a tree.
No
No. A tree on 6 vertices has exactly 6 − 1 = 5 edges. A connected network with 6 edges therefore has one edge too many, which creates a cycle, so it is not a tree.
A network is connected and contains no cycles. State the name given to such a network, and state how many edges it has if it contains 8 vertices.
It is a tree; it has 7 edges.
A connected network with no cycles is a tree. A tree on n vertices has n − 1 edges, so with 8 vertices it has 8 − 1 = 7 edges.
Level 3 · Further Application
A network has 5 vertices in which exactly two vertices have degree 3 and the remaining three vertices have degree 2.
6
(a) Sum of degrees = 2 × 3 + 3 × 2 = 12.
(b) Sum of degrees = 2 × (number of edges), so edges = 12 ÷ 2 = 6.
A network has 6 vertices: three of degree 4 and three of degree 2.
9
(a) Sum of degrees = 3 × 4 + 3 × 2 = 12 + 6 = 18.
(b) Sum of degrees = 2 × (number of edges), so edges = 18 ÷ 2 = 9.
A network has 4 vertices, each of degree 3.
6
(a) Sum of degrees = 4 × 3 = 12.
(b) Edges = 12 ÷ 2 = 6.
Level 1 · Fluency
Using the network below, state the distance of the direct road between B and D.
5 km
The edge B–D is labelled 5 km.
A network of five campsites has tracks: P–Q 3 km, Q–R 4 km, R–S 2 km, P–T 6 km, T–S 5 km. State the length of the direct track between R and S.
2 km
The edge R–S is labelled 2 km.
Using the campsite tracks P–Q 3 km, Q–R 4 km, R–S 2 km, P–T 6 km, T–S 5 km, state the length of the direct track from P to T.
6 km
The edge P–T is labelled 6 km.
Level 2 · Application
Using the network above, calculate the total length of the route A → B → D → E → F.
17 km
4 + 5 + 3 + 5 = 17 km.
Using the campsite tracks P–Q 3 km, Q–R 4 km, R–S 2 km, P–T 6 km, T–S 5 km, calculate the total length of the route P → Q → R → S.
9 km
3 + 4 + 2 = 9 km.
Using the same campsite tracks, calculate the total length of the route P → T → S → R.
13 km
6 + 5 + 2 = 13 km.
Level 3 · Further Application
Using the network above:
1 km
(a) 6 + 7 + 5 = 18 km.
(b) A → B → D → E → F is 17 km, so it is shorter by 1 km.
Using the campsite tracks P–Q 3 km, Q–R 4 km, R–S 2 km, P–T 6 km, T–S 5 km:
P → Q → R → S, by 2 km
(a) P → Q → R → S = 3 + 4 + 2 = 9 km.
(b) P → T → S = 6 + 5 = 11 km, so P → Q → R → S is shorter by 2 km.
Using the same campsite tracks:
Q → P → T, by 2 km
(a) Q → P → T = 3 + 6 = 9 km.
(b) Q → R → S → T = 4 + 2 + 5 = 11 km, so Q → P → T is shorter by 2 km.
Level 1 · Fluency
In a network modelling flights between airports, what do the vertices represent?
The airports (the vertices are the airports; the edges are the flights connecting them).
In a network modelling roads between towns, what do the edges represent?
The roads connecting the towns (the towns are the vertices).
In a network modelling a rail system, state what the vertices represent.
The stations (the rail lines between them are the edges).
Level 2 · Application
Explain why a social-media friendship structure can be modelled as a network.
Each person is a vertex and each friendship is an edge joining two people; this captures who is connected to whom.
Explain why a set of towns joined by roads can be modelled as a network.
Each town is a vertex and each road joining two towns is an edge, so the network captures which towns are directly connected and (with weights) how far apart they are.
Explain why the connections between computers on the internet can be modelled as a network.
Each computer or device is a vertex and each cable or wireless link between two devices is an edge, so the network shows which devices can communicate directly.
Level 3 · Further Application
Describe two real-world situations (other than transport or friendships) that could be modelled as a network, stating what the vertices and edges represent in each.
(a) e.g. a water/pipe network — vertices are junctions/reservoirs, edges are pipes (weights = capacity or length).
(b) e.g. a computer network — vertices are devices, edges are cable/wireless links (weights = distance or data speed). (Other valid answers: electricity grid, project tasks, family tree.)
Describe how each of the following could be modelled as a network, stating what the vertices and edges represent.
(a) Vertices are power stations, substations and houses; edges are the power lines (weights = length or capacity).
(b) Vertices are junctions, reservoirs and taps; edges are the pipes (weights = length or flow capacity).
Describe how each of the following could be modelled as a network, stating what the vertices and edges represent.
(a) Vertices are the tasks (or events); edges show which task must follow which (weights = time taken).
(b) Vertices are people; edges are the parent–child relationships joining them.
Level 1 · Fluency
When a map is converted to a network, what do the edge weights usually represent?
The distance (or travel time) along each road between two locations.
When a map is drawn as a network, what do the vertices represent?
The locations on the map, such as towns, junctions or landmarks.
On a network drawn from a map, an edge has no arrow on it. What does this tell you about travelling along that road?
The road can be travelled in both directions (it is an undirected edge).
Level 2 · Application
A map shows four towns. Roads: W–X 8 km, X–Y 5 km, Y–Z 6 km, W–Z 10 km, X–Z 7 km. Draw a weighted network to represent this map.
A valid network has 4 vertices W, X, Y, Z with the five weighted edges shown:
A map has three towns with roads A–B 7 km, B–C 4 km and A–C 9 km. Describe the weighted network you would draw (vertices, edges and their labels).
Draw three vertices A, B and C. Join A–B, B–C and A–C with edges, labelling them 7, 4 and 9 (km) respectively. The positions of the vertices do not matter — only the connections and weights.
A student draws a network of a map but places the vertices in different positions from the real map. Explain whether their network can still be a correct representation.
Yes. A network only needs to show the correct connections and edge weights, not the true positions or scale. As long as the same pairs of vertices are joined and the weights match, the network is correct no matter where the vertices are drawn.
Level 3 · Further Application
A map shows six towns connected by the roads in the table.
| Road | Distance (km) |
|---|---|
| A–B | 4 |
| A–C | 6 |
| B–C | 2 |
| B–D | 5 |
| C–D | 8 |
| C–E | 7 |
| D–E | 3 |
| D–F | 9 |
| E–F | 5 |
4
(a) The network is:
(b) D is joined to B, C, E and F, so its degree is 4.
A map’s roads are listed in a table: P–Q 5, P–R 8, Q–R 3, Q–S 6, R–S 4, S–T 7 (all in km).
5 vertices, 6 edges; degree of S = 3
(a) The towns are P, Q, R, S, T, so there are 5 vertices, and each listed road is one edge, giving 6 edges.
(b) S is joined to Q, R and T, so its degree is 3.
A map’s roads are listed: A–B 4, A–C 6, B–C 5, C–D 3, C–E 8, D–E 2 (all in km).
degree of C = 4; total 28 km
(a) C is joined to A, B, D and E, so its degree is 4.
(b) 4 + 6 + 5 + 3 + 8 + 2 = 28 km.
Level 1 · Fluency
A table lists a connection “Office 1 – Office 3, $250”. On the network, how is this shown?
As an edge joining the vertices Office 1 and Office 3, labelled 250.
A table lists a cable “Depot A – Depot D, 320 m”. When this is drawn as a network, what does the number 320 become?
The weight (label) on the edge joining Depot A and Depot D.
A connection table has one row for each link between two buildings. If the table has 7 rows, how many edges will the finished network have, and why?
7 edges — each row of the table is one connection, drawn as one edge.
Level 2 · Application
A table gives internet-cabling costs between 5 offices: 1–2 $180, 1–3 $250, 2–3 $120, 3–4 $200, 4–5 $150, 2–5 $300. Draw the weighted network.
A valid network has vertices 1–5 with the six weighted edges:
A table gives flight times between four cities: A–B 2 h, A–C 3 h, B–C 1 h, B–D 4 h, C–D 2 h. Describe the weighted network you would draw from this table.
Draw four vertices A, B, C and D. For each row, join the two cities with an edge labelled with its time: A–B 2, A–C 3, B–C 1, B–D 4, C–D 2 (hours). Each table row becomes one labelled edge.
Explain the step-by-step method for drawing a network from a connection table.
1) Draw one vertex for each item named in the table. 2) For each row, draw an edge joining the two named vertices. 3) Label each edge with the value (weight) given in that row. The positions of the vertices can be chosen freely.
Level 3 · Further Application
Using the table of cabling costs in the Application question above:
3; $1200
(a) Office 3 connects to 1, 2 and 4, so its degree is 3.
(b) 180 + 250 + 120 + 200 + 150 + 300 = $1200.
A table of cabling costs between five offices: 1–2 $200, 1–3 $150, 2–3 $180, 3–4 $220, 4–5 $170, 3–5 $240.
degree of Office 3 = 4; $1160
(a) Office 3 connects to 1, 2, 4 and 5, so its degree is 4.
(b) 200 + 150 + 180 + 220 + 170 + 240 = $1160.
A table of pipe lengths between four pumping stations: A–B 12, B–C 9, C–D 15, A–D 20, B–D 11 (all in m).
degree of B = 3; 67 m
(a) B is joined to A, C and D, so its degree is 3.
(b) 12 + 9 + 15 + 20 + 11 = 67 m.
Level 1 · Fluency
A garbage truck must travel along every street exactly once and return to the depot. What network feature is it trying to minimise?
The total distance travelled.
A delivery driver plans a route that visits every customer once and returns to the depot, wanting to drive as little as possible. What quantity is being minimised?
The total distance travelled.
A street-sweeper must clean every street and wants to finish the round as quickly as possible. In network terms, what is being kept as small as possible?
The total length (distance) of the route travelled.
Level 2 · Application
Using the towns network above, a courier starts at A and must reach F. Give a route and its total distance, then state whether it is the shortest possible.
A → B → D → E → F = 17 km. This is the shortest route from A to F (no route is shorter).
A courier’s route between two depots has legs of 6 km, 9 km, 4 km and 7 km. Calculate the total distance of the route.
26 km
6 + 9 + 4 + 7 = 26 km.
A driver can take route 1 with legs 8 km, 5 km and 9 km, or route 2 with legs 7 km, 6 km and 10 km. State which route is shorter and by how much.
Route 1, by 1 km
Route 1 = 8 + 5 + 9 = 22 km; route 2 = 7 + 6 + 10 = 23 km. Route 1 is shorter by 1 km.
Level 3 · Further Application
A council must connect the six towns A–F (network above) to a single water main using the existing roads, laying pipe along chosen roads only.
5 edges
(a) A minimum spanning tree connects all towns with the least total pipe length and no wasteful cycles.
(b) A spanning tree on 6 vertices always uses 6 − 1 = 5 edges.
A town planner must connect 8 new houses to a single water main by laying pipe along the streets, using chosen streets only.
7 edges
(a) A minimum spanning tree links all the houses with the least total pipe and no wasteful cycles.
(b) A spanning tree on 8 vertices uses 8 − 1 = 7 edges.
A company must link 10 offices into one connected network using cable along existing ducts, for the least total cost.
9 links
(a) A minimum spanning tree connects every office with the smallest total cable length and no cycles, so no cable is wasted.
(b) A spanning tree on 10 vertices uses 10 − 1 = 9 links.
Level 1 · Fluency
A minimum spanning tree connects n vertices. How many edges does it contain?
n − 1 edges.
A minimum spanning tree of a network has 8 edges. How many vertices does the network have?
9
A spanning tree on n vertices has n − 1 edges, so n − 1 = 8 gives n = 9.
A network has 12 vertices. State the number of edges in any of its spanning trees.
11
A spanning tree on n vertices has n − 1 edges, so 12 − 1 = 11.
Level 2 · Application
For the towns network above, determine the minimum spanning tree and state its total length.
19 km
Choosing the smallest edges that avoid a cycle: BC (2), DE (3), AB (4), BD (5), EF (5). Total length = 2 + 3 + 4 + 5 + 5 = 19 km.
A network has vertices J, K, L, M with edges J–K 3, K–L 5, L–M 2, J–M 8, J–L 6. Determine the minimum spanning tree and state its total weight.
10
Choose the smallest edges that avoid a cycle: L–M (2), J–K (3), K–L (5). These connect all four vertices. Total = 2 + 3 + 5 = 10.
A network has vertices A, B, C, D, E with edges A–B 6, B–C 2, C–D 4, D–E 3, A–E 8, B–E 5. Determine the minimum spanning tree and state its total weight.
15
Smallest edges avoiding cycles: B–C (2), D–E (3), C–D (4), then A–B (6) to bring in A. B–E (5) is rejected because it would form a cycle. Total = 2 + 3 + 4 + 6 = 15.
Level 3 · Further Application
For the towns network above:
19 km; 18 km
(a) MST = {BC, DE, AB, BD, EF}, length 19 km.
(b) The new edge C–F (4) is cheaper than EF (5). Replacing EF with CF still connects F and lowers the total: 2 + 3 + 4 + 5 + 4 = 18 km.
A network has vertices P, Q, R, S with edges P–Q 5, Q–R 3, R–S 4, P–S 9, P–R 6.
12; 10
(a) MST = {Q–R (3), R–S (4), P–Q (5)}; total = 3 + 4 + 5 = 12.
(b) With Q–S (2) added, take Q–S (2), Q–R (3), P–Q (5): total = 2 + 3 + 5 = 10.
A network has vertices A, B, C, D with edges A–B 7, B–C 4, C–D 5, A–D 6, A–C 9.
15; 12
(a) MST = {B–C (4), C–D (5), A–D (6)}; total = 4 + 5 + 6 = 15.
(b) With A–B now 3, take A–B (3), B–C (4), C–D (5): total = 3 + 4 + 5 = 12.
Level 1 · Fluency
In Kruskal’s algorithm, which edge do you consider first?
The edge with the smallest weight.
In Prim’s algorithm you begin at a chosen vertex. What is the first edge you add?
The smallest-weight edge that is joined to the starting vertex.
In Kruskal’s algorithm, when the next edge you consider would form a cycle, what do you do?
Reject (skip) that edge and move on to the next-smallest edge.
Level 2 · Application
Apply Kruskal’s algorithm to the towns network above. List the edges chosen, in order, and any edge you reject and why.
Add BC(2), DE(3), AB(4), BD(5). Reject AC(6) and CE(7) — each would form a cycle. Add EF(5). Chosen: BC, DE, AB, BD, EF (5 edges).
Apply Kruskal’s algorithm to the network with edges A–B 6, B–C 2, C–D 4, D–E 3, A–E 8, B–E 5. List the edges chosen in order and any edge you reject, with the reason.
Chosen in order: B–C (2), D–E (3), C–D (4), A–B (6). Rejected: B–E (5) and A–E (8), because each would form a cycle. The tree has 4 edges.
Apply Kruskal’s algorithm to the network with edges P–Q 5, Q–R 3, R–S 4, P–S 9, P–R 6. List the edges chosen in order and any edge you reject, with the reason.
Chosen in order: Q–R (3), R–S (4), P–Q (5). Rejected: P–R (6) and P–S (9), because each would form a cycle. The tree has 3 edges.
Level 3 · Further Application
Using Prim’s algorithm starting at vertex A on the towns network above:
(a) From A: AB(4); then from {A,B} the cheapest new edge BC(2); then BD(5); then DE(3); then EF(5).
(b) Total = 4 + 2 + 5 + 3 + 5 = 19 km — the same as Kruskal’s (the MST length is unique).
Use Prim’s algorithm, starting at vertex A, on the network with edges A–B 6, B–C 2, C–D 4, D–E 3, A–E 8, B–E 5.
A–B, B–C, C–D, D–E; total 15
(a) From A: A–B (6). From {A,B}: B–C (2). From {A,B,C}: C–D (4). From {A,B,C,D}: D–E (3).
(b) Total = 6 + 2 + 4 + 3 = 15.
Use Prim’s algorithm, starting at vertex P, on the network with edges P–Q 5, Q–R 3, R–S 4, P–S 9, P–R 6.
P–Q, Q–R, R–S; total 12
(a) From P: P–Q (5). From {P,Q}: Q–R (3). From {P,Q,R}: R–S (4).
(b) Total = 5 + 3 + 4 = 12.
Level 1 · Fluency
What is a spanning tree of a network?
all
A tree (no cycles) that connects all the vertices of the network.
A spanning tree of a network with 7 vertices has how many edges?
6
A spanning tree on n vertices has n − 1 edges, so 7 − 1 = 6.
A tree is a connected network with one special property. What property is that?
It contains no cycles (no closed loops).
A tree is a connected network that contains no cycles.
Level 2 · Application
Explain why a spanning tree connecting n vertices must contain exactly n − 1 edges.
Starting from one vertex, each new edge can connect exactly one new vertex without forming a cycle. To reach all n vertices you add n − 1 edges; a further edge would create a cycle.
Explain why adding one extra edge to a spanning tree must create a cycle.
A spanning tree already connects every vertex, so any two vertices are joined by a path. Adding an edge between two vertices creates a second connection between them, and this new edge together with the existing path forms a closed loop — a cycle.
A connected network on n vertices has more than n − 1 edges. Explain why it cannot be a tree.
A tree on n vertices has exactly n − 1 edges and no cycles. Having more than n − 1 edges means at least one edge joins two vertices that are already connected, which creates a cycle, so the network is not a tree.
Level 3 · Further Application
A network of towns has several spanning trees.
(a) The minimum spanning tree is the spanning tree with the smallest possible total edge weight.
(b) Yes — the globally shortest edge is always safe to include, since it cannot create a cycle on its own and no cheaper connection exists.
A network of cities has many different spanning trees.
(a) It is the one with the smallest total edge weight. (b) The tree of weight 40.
(a) The minimum spanning tree is the spanning tree whose edge weights add to the smallest possible total.
(b) The tree of weight 40 could be the minimum spanning tree, since the MST has the least total weight and 46 is larger.
A network has a single most-expensive edge.
(a) Not necessarily.
(a) Not necessarily.
(b) If the most-expensive edge is the only way to connect a particular vertex to the rest of the network, the minimum spanning tree must include it. An edge is only left out when a cheaper set of edges can connect the same vertices.
Level 1 · Fluency
A minimum spanning tree connecting 5 towns to a power station has total cable 42 km. If a 6th town is added, will the total cable increase or decrease?
Increase — an extra vertex needs at least one more edge, adding to the total length.
A minimum spanning tree connecting 4 towns has total cable 30 km. A 5th town is added to the network. Will the minimum total cable increase or decrease?
Increase — connecting an extra town needs at least one more edge, which adds to the total length.
A minimum spanning tree connects 6 houses to a hub using 5 cables. If two houses are removed from the plan, will the number of cables in the minimum spanning tree increase or decrease?
Decrease — with 4 houses the spanning tree needs only 4 − 1 = 3 cables instead of 5.
Level 2 · Application
An irrigation company connects the six towns A–F (network above) to a water source using the least total pipe. State the minimum total length of pipe required.
19 km
This is the minimum spanning tree: 2 + 3 + 4 + 5 + 5 = 19 km of pipe.
Six sensors must be joined with the least total wire. The minimum spanning tree uses wires of 2 m, 3 m, 4 m, 5 m and 5 m. State the minimum total length of wire required.
19 m
Add the minimum spanning tree edges: 2 + 3 + 4 + 5 + 5 = 19 m.
A minimum spanning tree connecting five buildings uses fibre links of 6 m, 4 m, 7 m and 5 m. State the minimum total length of fibre needed.
22 m
Sum the minimum spanning tree edges: 6 + 4 + 7 + 5 = 22 m.
Level 3 · Further Application
Pipe costs $8000 per kilometre.
$152 000
(a) 19 × 8000 = $152 000.
(b) A non-minimum spanning tree has a greater total length, so at $8000/km it costs more.
Cable costs $6000 per kilometre. A minimum spanning tree connecting several towns has length 15 km.
$90 000
(a) 15 × 6000 = $90 000.
(b) A non-minimum spanning tree has a greater total length, so at $6000/km it costs more.
Pipe costs $5000 per kilometre, and each town needs one $2000 connection valve. A minimum spanning tree connecting 6 towns has length 20 km.
$100 000; $112 000
(a) 20 × 5000 = $100 000.
(b) Valves: 6 × 2000 = $12 000. Total = 100 000 + 12 000 = $112 000.
Level 1 · Fluency
The “shortest path” between two vertices is the path with the smallest total of what?
The smallest total edge weight (e.g. distance or time).
When finding the shortest path between two vertices in a weighted network, what do you add up along each route?
The edge weights (distances or times) along the route.
A shortest-path problem asks for the route between two vertices with the least total distance. Does the route with the fewest edges always have the least total distance?
No — a route with fewer edges can still be longer once the edge weights are added, so you must compare total weights, not the number of edges.
Level 2 · Application
For the towns network above, find the shortest path from A to F and state its length.
17 km
A → B → D → E → F = 4 + 5 + 3 + 5 = 17 km, which is the shortest.
The routes from town X to town Y are X → M → Y (6 km + 8 km) and X → N → Y (9 km + 4 km). Find the shortest path from X to Y and state its length.
X → N → Y = 13 km
X → M → Y = 6 + 8 = 14 km; X → N → Y = 9 + 4 = 13 km. The shortest path is X → N → Y = 13 km.
From A to D the routes are A → B → D (5 + 7), A → C → D (4 + 6) and A → B → C → D (5 + 3 + 6), all in km. Find the shortest path and its length.
A → C → D = 10 km
A → B → D = 12 km; A → C → D = 10 km; A → B → C → D = 14 km. The shortest path is A → C → D = 10 km.
Level 3 · Further Application
For the towns network above:
12 km
(a) A → B → D → E = 4 + 5 + 3 = 12 km (shorter than A → C → E = 13). Shortest A–E = 12 km.
(b) Shortest A–F = 17 km via A → B → D → E → F.
In a network the routes from P to S are P → Q → S (5 + 9), P → R → S (7 + 4) and P → Q → R → S (5 + 3 + 4), all in km.
P → R → S = 11 km
(a) P → Q → S = 14 km; P → R → S = 11 km; P → Q → R → S = 12 km.
(b) The shortest path is P → R → S = 11 km.
The routes from town A to town E are A → B → E (8 + 6), A → C → E (5 + 7) and A → B → C → E (8 + 4 + 7), all in km.
A → C → E = 12 km
(a) A → B → E = 14 km; A → C → E = 12 km; A → B → C → E = 19 km.
(b) The shortest path is A → C → E = 12 km.
Level 1 · Fluency
On the towns network above, state the length of the direct edge from D to F.
9 km
On a network, the direct edge between towns H and P is labelled 7. State the length of the direct route from H to P.
7 km
The direct edge H–P is labelled 7 km.
Towns G and K are joined by a direct edge of 15 km, but the route G → H → K has legs of 6 km and 8 km. State the length of the shorter of these two options.
14 km
G → H → K = 6 + 8 = 14 km, which is less than the direct 15 km, so the shorter option is 14 km.
Level 2 · Application
On the towns network above, a driver claims the route A → D is direct. Explain why they must instead travel via other towns, and give the shortest such distance.
9 km
There is no direct A–D edge, so the driver must pass through B or C. Shortest is A → B → D = 4 + 5 = 9 km.
A driver wants to travel from town H to town S. There is no direct road, but H → P → S has legs 5 km and 6 km, and H → Q → S has legs 8 km and 4 km. Explain why the driver cannot go direct and give the shortest distance.
11 km
There is no H–S edge, so the driver must pass through P or Q. H → P → S = 5 + 6 = 11 km; H → Q → S = 8 + 4 = 12 km. The shortest is H → P → S = 11 km.
Between towns G and K there is no direct road. The options are G → H → K (6 km + 8 km) and G → J → K (5 km + 7 km). Explain why travel must be indirect and state the shortest distance.
12 km
With no G–K edge, travel must pass through H or J. G → H → K = 6 + 8 = 14 km; G → J → K = 5 + 7 = 12 km. The shortest is G → J → K = 12 km.
Level 3 · Further Application
Using the towns network above:
not
(a) B → D → E → F = 5 + 3 + 5 = 13 km, which is the shortest from B to F.
(b) B → D → F = 5 + 9 = 14 km, which is longer than 13 km, so it is not optimal.
In a network the routes from B to F are B → D → F (5 + 9), B → E → F (7 + 5) and B → D → E → F (5 + 3 + 5), all in km.
B → E → F = 12 km; not optimal
(a) B → D → F = 14 km; B → E → F = 12 km; B → D → E → F = 13 km. Shortest = B → E → F = 12 km.
(b) B → D → F = 14 km > 12 km, so it is not optimal.
The routes from town P to town T are P → R → T (8 + 6), P → S → T (5 + 10) and P → R → S → T (8 + 4 + 10), all in km.
P → R → T = 14 km; not optimal
(a) P → R → T = 14 km; P → S → T = 15 km; P → R → S → T = 22 km. Shortest = P → R → T = 14 km.
(b) P → S → T = 15 km > 14 km, so it is not optimal.
Level 1 · Fluency
True or false: the shortest path between two vertices is always part of the minimum spanning tree.
False.
False. They solve different problems and need not overlap.
True or false: the minimum spanning tree always contains the shortest path between every pair of vertices.
False.
False. The minimum spanning tree minimises the total length needed to connect all vertices, so the route it provides between two particular vertices can be longer than their true shortest path.
True or false: the edge with the largest weight in a network can never be part of the minimum spanning tree.
False.
False. If the largest-weight edge is the only way to connect a particular vertex to the rest of the network, the minimum spanning tree must include it.
Level 2 · Application
Give one reason, other than distance, why the shortest path between two towns might not be the “best” route to take.
Other factors such as heavy traffic, road quality, tolls, road works or safety can make a slightly longer route quicker or preferable.
Give one reason, other than distance, why a delivery company might not choose the shortest path between two depots.
Factors such as traffic congestion, tolls, poor road quality, roadworks or low speed limits can make a longer route faster, cheaper or more reliable than the shortest one.
Explain why the shortest path between two towns and the minimum spanning tree of the road network can use completely different edges.
They solve different problems: the shortest path minimises the distance between two specific towns, while the minimum spanning tree minimises the total length needed to connect every town with no cycles. An edge vital to one town-to-town trip can be left out of the MST because all towns can be linked more cheaply another way.
Level 3 · Further Application
Using the towns network above:
(a) F can be reached more cheaply via E–F (5 km), so the MST uses EF and omits the longer DF; the MST minimises the total length, not the link from any one vertex.
(b) A shortest path minimises the distance between two specific vertices, while an MST minimises the total length needed to connect all vertices — different goals, so different edges.
In a road network, town F can be reached directly from D by a 9 km road, or from E by a 5 km road.
(a) The 5 km E–F road connects F more cheaply than the 9 km D–F road.
(a) The minimum spanning tree connects F as cheaply as possible. Since E–F (5 km) is shorter than D–F (9 km), the MST uses E–F (once E is connected) and omits the longer D–F.
(b) A shortest path minimises the distance between two specific vertices, while the MST minimises the total connecting length for all vertices, so an edge needed for one trip may be excluded from the MST.
A network has a shortest path from A to C that runs directly along the edge A–C.
(a) The MST may connect A and C more cheaply through other vertices.
(a) The MST might link A and C more cheaply through other vertices (for example A–B–C could total less than A–C), so it omits A–C even though A–C is the shortest direct route; including A–C could also create a cycle.
(b) The MST minimises the total weight needed to connect all vertices with no cycles, whereas a shortest path minimises the weight between just two chosen vertices.