Topics

Choosing and justifying the right network method

The decision that carries the marks

All three methods act on the same picture, so the diagram never tells you which to use. The wording of the context does.
Read the question for the objective before you touch the network:

The context wants…	Method	Answer looks like
Every site connected for least cost	Minimum spanning tree	A set of $n-1$ arcs and a total
To get from one place to another cheaply	Shortest path	A route and a distance
To cover every link once	Traversability	Yes/no, plus start and finish or a repeat

A one-line justification is expected in an internal. "The council must reach every settlement, so this is a minimum spanning tree problem, not a shortest path problem" is the sentence that shows you chose rather than guessed.

The traps that look like each other

"Cheapest way to connect the towns" vs "cheapest way to travel between two towns." The first is a spanning tree; the second is a shortest path. The words connect and travel decide it.
"Visit every town" vs "drive down every road." Only the second is traversability; the first is outside this standard and should be tackled by systematic listing, not by a named algorithm.
"Least cable" vs "shortest journey" on the same network give different answers, because they optimise different things. Being able to say why is a Merit-level observation.

Common features of a good write-up

State the model — what the nodes are, what the arcs are, what the weights measure and in what units.
Name the method and say why it fits the context.
Show the systematic working — the sorted list, the labelled nodes, or the degree table.
Check the answer with the appropriate structural test:
- spanning tree → exactly $n - 1$ arcs, every node reached, no cycle
- shortest path → route re-added, no obvious shorter route
- traversability → route length equals the arc count
Answer in context, with units, and say what it means for the person in the problem.
State the limitations of the model where they matter — missing links, one-way roads, costs the weights do not include.

Making the model harder, and what to do

A site that must be included, or one that must not be. Include it by starting Prim's algorithm there; exclude a node by deleting it and its arcs before running anything.
An arc that already exists. Give it weight 0 so the algorithm takes it first — it is free to use.
An arc that is unavailable (closed road, failed cable). Delete it and re-run. Comparing the before and after totals is the standard "what if" question.
Fixed costs per site plus per-kilometre costs. The per-site costs are the same whichever arcs you choose, so they do not affect which tree is minimum — but they must be added to the final quoted cost.
A cost that is not proportional to length (a river crossing, a consent fee). Put the whole real cost on the arc as its weight; the algorithms do not care what the weight measures, only that bigger means worse.

Comparing solutions

The MST is cheapest to build but can be slow to travel. A chain-shaped tree can force a long detour between neighbouring sites.
The MST is fragile. With exactly $n-1$ arcs, any single failure splits the network. Adding one arc to create a loop buys resilience for a known price — and quantifying that price is a natural Excellence question.
The shortest path ignores most of the network, so a route that is optimal today can be badly affected by one closure. The slack on each arc measures how much delay the route can absorb.

Tips and Tricks

Say which method you chose and why, in one sentence, before you start. Assessors are explicitly looking for evidence you selected a method rather than recognised a familiar picture.

"Connect them all" is never a shortest-path question, and "get from A to B" is never a spanning tree question. If your answer to a travel question is a set of $n-1$ arcs, you have solved the wrong problem.

Do not stop at the number. Convert it into what the context measures — dollars, minutes, kilometres of trench — and say what should be done.

Re-run, do not patch. When an arc is removed or a cost changes, run the algorithm again from the start. Editing a previous answer by eye almost always misses a knock-on change.

Mention what the model leaves out. Every real network has costs the weights do not carry — consents, maintenance, delivery windows. Naming one is a cheap and genuine Excellence-level observation.

Worked ExampleOne network, three questions

A district council models five settlements with these road distances in km: $PQ = 8$ , $PR = 5$ , $QR = 4$ , $QS = 9$ , $RS = 6$ , $RT = 12$ , $ST = 3$ .

(a) The council wants to run a water main to every settlement. What is the least length of pipe needed? (b) An ambulance must travel from P to T. What is the fastest route? (c) A road inspector must drive every road once. Can it be done?

Step 1 — Build the model once, and use it three times

Nodes: the five settlements P, Q, R, S, T
Arcs: the seven roads listed
Weights: road distance in km

Degrees: P = 2 ( $PQ$ , $PR$ ), Q = 3 ( $PQ$ , $QR$ , $QS$ ), R = 4 ( $PR$ , $QR$ , $RS$ , $RT$ ), S = 3 ( $QS$ , $RS$ , $ST$ ), T = 2 ( $RT$ , $ST$ ).

Handshake check: $2 + 3 + 4 + 3 + 2 = 14 = 2 \times 7$ ✓

Step 2 — Part (a): choose the method

The council wants every settlement supplied, at the least total pipe. That is "connect everything for the smallest total", so this is a minimum spanning tree — not a route question.

Sort the arcs:

$ST\,3, \quad QR\,4, \quad PR\,5, \quad RS\,6, \quad PQ\,8, \quad QS\,9, \quad RT\,12$

Kruskal, needing $5 - 1 = 4$ arcs:

Arc	Weight	Decision
$ST$	3	Accept
$QR$	4	Accept
$PR$	5	Accept — brings in P
$RS$	6	Accept — joins $\{P,Q,R\}$ to $\{S,T\}$ ; 4 arcs, stop
$PQ$	8	Reject — cycle $PQR$
$QS$	9	Reject — cycle
$RT$	12	Reject — cycle $RST$

Check: 4 arcs for 5 nodes ✓, all of P, Q, R, S, T used ✓

$3 + 4 + 5 + 6 = 18$

Step 3 — Part (b): choose the method

The ambulance travels from one place to another, so this is a shortest path — the spanning tree from part (a) is the wrong tool and would give a wrong answer.

Dijkstra from P:

P permanent at 0.
From P: $Q = 8$ , $R = 5$ . Smallest is 5 → R permanent at 5.
From R: $Q = 5 + 4 = 9$ ? No — 8 is already smaller, discard 9. $S = 5 + 6 = 11$ . $T = 5 + 12 = 17$ .
Smallest is 8 → Q permanent at 8.
From Q: $S = 8 + 9 = 17$ — larger than 11, discard.
Smallest is 11 → S permanent at 11.
From S: $T = 11 + 3 = 14$ — smaller than 17, so 14 replaces 17.
T permanent at 14 — stop.

Node	P	Q	R	S	T
Label	0	8	5	11	14
Discarded	—	9	—	17	17

Back-trace: $11 + ST(3) = 14$ ✓ via S; $5 + RS(6) = 11$ ✓ via R; $0 + PR(5) = 5$ ✓ from P.

Sense-check: $P \to R \to T = 5 + 12 = 17$ and $P \to Q \to S \to T = 8 + 9 + 3 = 20$ — both longer ✓

Step 4 — Part (c): choose the method

"Drive every road once" is traversability, decided entirely by the odd degrees.

From Step 1, the odd nodes are Q (3) and S (3) — exactly two.

A valid route: $Q \to P \to R \to Q \to S \to R \to T \to S$

Verify: $QP$ , $PR$ , $RQ$ , $QS$ , $SR$ , $RT$ , $TS$ — seven arcs, each used once ✓

Step 5 — Compare the three answers

The three methods used the same network and produced completely different arc sets:

Method	Arcs used	Total
Minimum spanning tree	$PR$ , $QR$ , $RS$ , $ST$	18 km
Shortest path P→T	$PR$ , $RS$ , $ST$	14 km
Traversal	all seven	47 km