AN5 - Minimum connectors by Kruskal and Prim | OCR A-Level Further Mathematics B (MEI)

Connect every vertex for the least total weight using Kruskal's or Prim's algorithm. Learn which arcs are eligible at each step, record ties and rejected cycles clearly, and apply Prim's algorithm to both a diagram and a table.

Decide what a minimum connector minimises

Would the cheapest cable system linking every room also give the shortest route between any two rooms? These are different objectives: a minimum connector saves on the entire system, even if one journey through it is longer.

You already know

A network has weighted arcs. A tree is connected and has no cycle; a tree on $n$ vertices has $n-1$ arcs. A path connects a particular pair of vertices without repeating vertices.

Imagine paying once to install each cable. Every room must be connected, directly or indirectly, but no particular room has to be the centre. In a model with positive installation costs, removing an arc from a cycle preserves connectivity and reduces cost. An economical connector therefore needs no cycle.

Minimum connector

A spanning tree includes every vertex of a connected undirected network. A minimum connector, or minimum spanning tree, is a spanning tree whose sum of arc weights is as small as possible. It need not be unique when weights tie.

Both algorithms here produce a minimum connector. Kruskal scans arcs globally in weight order and may build separate pieces before joining them. Prim grows one connected tree from a specified starting vertex. Neither algorithm adds an arc joining two vertices already connected within its current tree component.

The procedures are not printed in the formula booklet: learn their selection rules. Their complexity is covered after Dijkstra's algorithm in the next lesson.

Key idea

A minimum connector minimises the sum of the chosen installation weights across the whole network. It is not a collection of shortest journeys from one starting point.

Use that objective to distinguish the problems.

Use Kruskal's global arc order

List arcs in increasing weight order. Consider the next arc and include it unless it creates a cycle with arcs already chosen. Stop as soon as all vertices are connected, after $n-1$ accepted arcs.

If equal weights occur, either tied arc may be considered first unless a tie rule is specified. Test the cycle condition after each selection; accepting every tied arc automatically can create a cycle. The total optimum is unchanged, although the final tree may differ.

Kruskal's selection rule

For a connected undirected network, repeatedly consider the smallest remaining arc and accept it if its endpoints lie in different current components. Reject it if its endpoints are already connected by chosen arcs.

Stop after $n-1$ accepted arcs for $n$ vertices.

Not in the formula booklet: learn it.

The following network has weights $BC=1$ , $AC=2$ , $DE=3$ , $AB=4$ , $BD=5$ , $CD=6$ , $CE=7$ , $BE=8$ . Arcs are undirected.

[DIAGRAM: asset_name: Kruskal connectors before and after a weight change; asset_slug: connectors_kruskal_variation; caption: Kruskal rejects AB because it closes a cycle, then chooses the cheapest arc joining the remaining components; description: Two panels show vertices A, B, C, D, E with arcs BC 1, AC 2, DE 3, AB 4, CD 6, CE 7, BE 8 and BD. In the first panel BD is 5 and the highlighted connector is BC, AC, DE, BD. In the second BD is 9 and the highlighted connector is BC, AC, DE, CD. Weight labels sit apart from unmarked arc crossings.]
Kruskal rejects AB because it closes a cycle, then chooses the cheapest arc joining the remaining components

Worked example 1: reject a cheap cycle

Question. Apply Kruskal's algorithm to the network above and find its minimum connector weight.

Plan. Consider arcs in weight order, recording accept or reject until four arcs have been accepted.

Arc considered	Weight	Decision and reason
$BC$	$1$	Accept: joins two separate vertices.
$AC$	$2$	Accept: joins $A$ to the $BC$ component.
$DE$	$3$	Accept: joins a separate pair.
$AB$	$4$	Reject: $A\!C\!B\!A$ would be a cycle.
$BD$	$5$	Accept: joins the two components; stop.

\begin{aligned} \text{accepted arcs}&=\{BC,AC,DE,BD\} &&\text{four for five vertices}\\ \text{total weight}&=1+2+3+5=11 &&\text{add accepted weights only} \end{aligned}

Why this step? The rejected arc has a lower weight than $BD$ , but it adds no new connection between components.

Answer. A minimum connector has arcs $BC,AC,DE,BD$ and total weight $11$ .

Check. Every vertex is included, the four chosen arcs form no cycle, and the final selection joins the last two components.

Change only the weight of $BD$ from $5$ to $9$ . Re-sort the arcs rather than keeping the old selection order.

Worked example 2: a changed joining arc

Question. Apply Kruskal's algorithm after this weight change and find the new minimum connector.

Plan. Retain the early selections and rejection, then choose the next eligible arc in the revised order.

Arc considered	Weight	Decision and reason
$BC$	$1$	Accept.
$AC$	$2$	Accept.
$DE$	$3$	Accept.
$AB$	$4$	Reject: cycle in the $ABC$ component.
$CD$	$6$	Accept: joins $ABC$ to $DE$ ; stop.

\begin{aligned} \text{accepted arcs}&=\{BC,AC,DE,CD\} &&\text{new component-joining choice}\\ \text{total weight}&=1+2+3+6=12 &&\text{sum the new tree} \end{aligned}

Why this step? The increased weight moves $BD$ behind a cheaper way of joining the same two components.

Answer. Arcs $BC,AC,DE,CD$ , total weight $12$ .

Check. The optimum rises by only one, although one arc rose by four: the algorithm switches to an alternative.

Record Kruskal's construction on the graph, supported by a clear ordered arc list. A final tree alone does not show that the requested algorithm was used.

Watch out

Wrong: accept $AB$ after $BC,AC,DE$ because its weight $4$ is next smallest. Its endpoints are already connected through $C$ , so it creates a cycle. Correct: reject $AB$ and continue to the next eligible arc in weight order.

Check the cycle condition after each selection in the next connector.

Grow one tree with Prim's algorithm

Start at the stated vertex. At every step, choose a minimum-weight arc joining a vertex already in the tree to a vertex outside it. Add that arc and its new vertex. An arc between two outside vertices is not eligible, however light it is.

Continue this lesson.

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

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AN5 - Minimum connectors by Kruskal and Prim

Decide what a minimum connector minimises

Use Kruskal's global arc order

Grow one tree with Prim's algorithm

Continue this lesson.

Learn faster with Nova