DB1, DB2 - Minimum spanning trees
How can five buildings share a cable network at the smallest total cost? DB1 introduces the language of weighted networks; DB2 uses minimum spanning trees to connect every node efficiently. You will use Prim's and Kruskal's algorithms, handle ties and decide whether the mathematical answer meets the practical need.
Nodes, arcs and weights
What is the least cable needed to connect buildings A, B, C, D and E if the possible cable lengths are AB 2, AC 3, BC 1, BD 4, CD 5, CE 6 and DE 2 metres? A building may connect indirectly through other buildings. These are the only available links.
The picture records possibilities, rather than insisting that every cable is installed. Its positions are schematic: use the numbers, not the drawn lengths.
[DIAGRAM: asset_name: Five buildings and a minimum cable network; asset_slug: aqa7367-spanning-network; caption: The original seven possible links and a minimum spanning tree of total weight 9; description: Two panels contain nodes A B C D E with undirected weighted arcs AB 2 AC 3 BC 1 BD 4 CD 5 CE 6 DE 2. The left panel shows all possible links. The right panel highlights BC AB DE BD and shows the other links faintly. The highlighted links connect all five nodes without a cycle and total 9.]
Network language
A network is a graph with numerical information attached. A node represents an object or location; an arc represents a connection; its weight is a number such as distance, time or cost. Here arcs are undirected: each connection works both ways with the same weight.
A spanning tree uses every node, remains connected and has no cycle. A tree on nodes has arcs. Starting from one node, each new arc can attach one new node; attaching all the others needs arcs. Conversely, removing any arc from a tree disconnects it.
A minimum spanning tree (MST) has the smallest sum of arc weights among all spanning trees. “Minimum” describes the total weight, not the number of arcs: every spanning tree on these five nodes has four arcs. It need not give the shortest route between each pair of nodes, or a tour returning to the start.
Key idea
The requirement is connection, directly or indirectly. With nonnegative installation costs, a cycle is unnecessary for basic connection: remove an arc from the cycle and the network stays connected without increasing cost.
Distinguish the number of nodes from the number of links needed.
Prim's and Kruskal's algorithms
Two greedy algorithms build an MST by making safe choices of light arcs. Both apply to a finite connected undirected network; neither procedure is printed in the formula booklet.
Prim's algorithm grows one connected tree. Start at any node. Among arcs with exactly one endpoint in the tree, select an arc of least weight and add its other endpoint. Repeat until every node is included. An arc between two unvisited nodes is not yet eligible; an arc between two visited nodes creates a cycle.
Kruskal's algorithm starts with all nodes separate. Inspect all arcs in nondecreasing weight order, accepting an arc unless it creates a cycle with accepted arcs. Stop after accepted arcs. Separate small trees are allowed during this procedure. In either algorithm, tied eligible arcs may be chosen in either order.
Worked example 1: Prim from A
Question. Use Prim's algorithm, starting at A, on the network with arcs AB 2, AC 3, BC 1, BD 4, CD 5, CE 6, DE 2. Find an MST and its weight.
Plan. At each step choose the lightest link from the included nodes to an excluded node.
| Included nodes before the step | Least eligible arc | Reason |
|---|---|---|
| A | AB, weight 2 | AB is lighter than AC |
| A, B | BC, weight 1 | BC now reaches C; DE is still ineligible |
| A, B, C | BD, weight 4 | BD is lighter than CD and CE |
| A, B, C, D | DE, weight 2 | DE is lighter than CE |
Answer. AB, BC, BD, DE, with total .
Check. The four selected arcs connect all five nodes without a cycle. Kruskal's sorted scan accepts BC 1, AB 2 and DE 2, rejects AC 3 because A–B–C already connects its endpoints, then accepts BD 4: independently, the total is 9.
Change just the algorithm, keeping the network fixed. Kruskal can accept DE before that component is connected to A.
Worked example 2: Kruskal on the same network
Question. Use Kruskal's algorithm on arcs AB 2, AC 3, BC 1, BD 4, CD 5, CE 6, DE 2.
Plan. Sort globally, and test for a cycle before accepting each arc.
Accept BC and AB: they form the path A–B–C. Accept DE: it joins two previously separate nodes. Reject AC: together with AB and BC it would close a triangle. Accept BD: it joins the two components. Four arcs are now accepted, so stop.
Answer. BC, AB, DE, BD; total weight 9.
Check. Removing BD separates ABC from DE. The available links between those groups are BD 4, CD 5 and CE 6, so BD is the cheapest possible bridge between them. Prim's independent construction above reaches the same tree.
The same local-looking choice has a different eligibility rule in each algorithm.
Watch out
Wrong in Prim: “DE has weight 2, so choose it immediately after AB.” Neither D nor E is yet included. Wrong in Kruskal: “Choose AC because 3 is next.” Its endpoints are already connected, so it must be rejected.
Practise the global cycle check with a fresh network.
Connectedness, ties and optimality
A greedy choice needs a reason why it cannot trap you in an unnecessarily expensive tree. Split the nodes into two groups. Any spanning tree must cross between the groups. A least-weight crossing arc is safe: if an MST does not use it, add it to create a cycle, then remove another crossing arc on that cycle. The removed arc is no lighter, so the new spanning tree costs no more.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account