7.04b - Minimum spanning trees | OCR A-Level Further Mathematics A

Connect every location with the least total length of cable. You will construct minimum spanning trees using Prim's graphical and tabular algorithms and Kruskal's algorithm, then adapt a connector to practical restrictions.

Prim's graphical algorithm

Five buildings need a shared cable connection. Must the cheapest network also give the shortest journey between every pair of buildings? The diagram will let you test that claim: connecting everybody and shortening one journey are different objectives.

You already know

A tree is connected and has no cycles. A spanning tree includes every vertex of the given graph. A tree on $n$ vertices has $n-1$ edges.

For cable, each installed edge is paid for once. A cycle is unnecessary if the only requirement is connectivity: removing an edge of the cycle leaves a connection between every pair. With non-negative weights, this cannot increase the total cost.

[DIAGRAM: asset_name: A minimum cable connector; asset_slug: h245_7_04_prim_network; caption: Prim's algorithm grows one connected tree; the highlighted minimum connector has total weight 8; description: Undirected complete network A B C D E with AB 2 AC 6 AD 5 AE 9 BC 3 BD 4 BE 7 CD 1 CE 8 DE 2. Highlight AB BC CD DE and show Prim from A chooses AB then BC then CD then DE.]

Minimum spanning tree

A minimum spanning tree, or minimum connector, is a spanning tree with the least possible total arc weight. There may be more than one minimum spanning tree, but their total weights are equal.

Prim's algorithm keeps one connected set of included vertices. At each step it crosses the boundary between that set and the vertices still outside it.

Prim's graphical algorithm

For a connected undirected weighted network, start at any vertex. Repeatedly add a least weight edge joining an included vertex to a vertex not yet included. Stop when all vertices are included.
In the formula booklet.

An edge joining two included vertices is ineligible, even if it is extremely cheap. Adding an outside vertex each time prevents cycles automatically.

Worked example 1: growing from A

Question. Use Prim's algorithm, starting at $A$ , to find a minimum spanning tree of the diagram.

Plan. Compare all edges crossing from the included set to its complement at each step.

Included before choice	Edge chosen	Reason
$\{A\}$	$AB=2$	least edge from $A$
$\{A,B\}$	$BC=3$	least edge crossing the boundary
$\{A,B,C\}$	$CD=1$	a new cheap edge is now eligible
$\{A,B,C,D\}$	$DE=2$	least connection to $E$

W=2+3+1+2=8 \qquad\text{sum selected weights}

Why this step? $CD$ cannot be selected at the start: neither endpoint belongs to the growing tree then.

Answer. $AB,BC,CD,DE$ , with total weight $8$ .

Check. All five vertices appear, four edges are selected, and there is no cycle.

Change only the starting vertex. Prim's choices can come in a different order while the minimum weight stays the same.

Worked example 2: growing from E

Question. Use Prim's algorithm on the same network, starting at $E$ .

Plan. Again choose the least edge crossing the current boundary.

\begin{aligned} \{E\}&\longrightarrow DE=2 &&\text{include }D\\ \{D,E\}&\longrightarrow DC=1 &&\text{include }C\\ \{C,D,E\}&\longrightarrow CB=3 &&\text{include }B\\ \{B,C,D,E\}&\longrightarrow BA=2 &&\text{include }A \end{aligned}

Why this step? Once $D$ has been included, the comparison is across all of $\{D,E\}$ , not just from $D$ .

Answer. $DE,DC,CB,BA$ , with total weight $2+1+3+2=8$ .

Check. This is the same tree as example 1, obtained in reverse order.

The cheapest edge in the whole network is not necessarily eligible at the next Prim step.

Watch out

Wrong: choose $CD=1$ immediately after starting at $A$ . Right: choose the least edge with exactly one endpoint already included. Choosing any globally cheap edge is Kruskal's idea, not Prim's rule.

Use the included set to keep the next choice unambiguous.

Prim's tabular algorithm

In a weight matrix, the same growing boundary can be tracked by crossing rows and marking columns.

For the symmetric matrices here, row and column labels name the same vertices. A dash means no usable entry, including the diagonal. It is not a zero cost edge. Cross the starting row and mark its column. Only entries in marked columns and uncrossed rows are eligible: their column endpoint is inside, and their row endpoint is outside.

Prim's tabular algorithm

Start by crossing one row and marking the matching column. Choose a minimum eligible entry in an uncrossed row and a marked column. Circle it, cross its row, and mark the matching column. Continue until every row is crossed.
In the formula booklet.

Crossing the chosen row prevents a vertex being added twice. Marking its column makes its connections available for the next comparison. The table of choices below is a readable record of those operations.

Worked example 3: reading the eligible entries

Question. Apply tabular Prim starting at $A$ to this matrix.

	$A$	$B$	$C$	$D$
$A$	–	$4$	$2$	$7$
$B$	$4$	–	$3$	$5$
$C$	$2$	$3$	–	$6$
$D$	$7$	$5$	$6$	–

Plan. At each stage choose from the marked columns after excluding crossed rows.

Crossed rows	Marked columns	Entry circled next
$A$	$A$	row $C$ , column $A$ : $2$
$A,C$	$A,C$	row $B$ , column $C$ : $3$
$A,C,B$	$A,C,B$	row $D$ , column $B$ : $5$

W=2+3+5=10 \qquad\text{one circled entry per added vertex}

Why this step? After $C$ is included, row $B$ , column $C$ is eligible; row $C$ , column $A$ is already crossed out.

Answer. $AC,CB,BD$ , in that order, with total weight $10$ .

Check. The three edges connect all four vertices with no cycle.

Change just $BC$ from $3$ to $2$ , in both symmetric entries. The new equality is between weights, not between two copies of an edge you should count twice.

Worked example 4: a changed matrix entry

Question. Apply tabular Prim from $A$ after this change to example 3.

Plan. Keep the row and column eligibility rule while recalculating each choice.

\begin{aligned} \text{cross }A,\ \text{mark }A&:\quad CA=2 &&\text{circle and include }C\\ \text{cross }C,\ \text{mark }C&:\quad BC=2 &&\text{circle and include }B\\ \text{cross }B,\ \text{mark }B&:\quad DB=5 &&\text{circle and include }D\\ W&=2+2+5=9 &&\text{sum once per chosen edge} \end{aligned}

Why this step? The symmetric entry $CB=2$ is in a crossed row by the time $B$ is added. It is not a second edge.

Answer. $AC,CB,BD$ , with total weight $9$ .

Check. Only the selected edge $BC$ changed, by $-1$ , matching the change from $10$ to $9$ .

Tabular Prim is graphical Prim written in matrix form. The eligibility rule, rather than the page layout, does the mathematics.

Kruskal's algorithm

Kruskal starts with separate vertices and joins components cheaply, rather than growing one component from a chosen start.

Kruskal's algorithm

For a connected undirected weighted network, list the edges in increasing weight. Add each next least edge if it creates no cycle; otherwise reject it. Stop after selecting a spanning tree.
In the formula booklet.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

	$A$	$B$	$C$	$D$
$A$	–	$4$	$2$	$7$
$B$	$4$	–	$3$	$5$
$C$	$2$	$3$	–	$6$
$D$	$7$	$5$	$6$	–

	$A$	$B$	$C$	$D$
$A$	–	$4$	$2$	$7$
$B$	$4$	–	$3$	$5$
$C$	$2$	$3$	–	$6$
$D$	$7$	$5$	$6$	–

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.04b - Minimum spanning trees

Prim's graphical algorithm

Prim's tabular algorithm

Kruskal's algorithm

Continue this lesson.

Learn faster with Nova

	$A$	$B$	$C$	$D$
$A$	–	$4$	$2$	$7$
$B$	$4$	–	$3$	$5$
$C$	$2$	$3$	–	$6$
$D$	$7$	$5$	$6$	–