Discrete Math › Section C · Graph theory › Topic C.3
Spanning trees
Given a network, which links can you drop and still reach every point? A spanning tree keeps every vertex connected with as few edges as possible, and when edges have costs, two simple greedy algorithms find the cheapest one.
Keeping everything connected, cheaply
A spanning tree of a connected graph \(G\) is a subgraph that is a tree and includes every vertex of \(G\). Think of a company that must connect six offices by leased lines. Any set of lines that links all offices with no redundant loop is a spanning tree. From the previous topic, a tree on \(n\) vertices has \(n - 1\) edges, so every spanning tree of a graph with \(n\) vertices uses exactly \(n - 1\) of its edges, however many edges the graph has. Spanning trees are the skeletons that keep a network in one piece.
Every connected graph has one
There are two natural ways to find a spanning tree. Pruning: while the graph still contains a cycle, delete any one edge of that cycle. The graph stays connected, because the rest of the cycle still joins the two ends of the deleted edge, and it stops when no cycle is left. Growing: start with all the vertices and no edges, then add edges of \(G\) one at a time, skipping any edge that would create a cycle, until \(n - 1\) edges are in. Either way the result depends on your choices, so a graph usually has many spanning trees.
Worked example: counting spanning trees
Take the square \(a\)-\(b\)-\(c\)-\(d\)-\(a\) with one diagonal, \(ac\): 4 vertices and 5 edges. 1. A spanning tree needs \(4 - 1 = 3\) edges, so choose 3 of the 5 edges: \(\binom{5}{3} = 10\) choices. 2. Three edges on four vertices form a tree unless they contain a cycle. The only cycles that 3 edges can make are the triangles \(ab, bc, ac\) and \(ac, cd, da\). 3. So \(10 - 2 = 8\) spanning trees. Simpler counts follow the same way: the cycle \(C_n\) has exactly \(n\) spanning trees, one for each edge you delete, and by Cayley's formula \(K_n\) has \(n^{n-2}\).
Spanning trees from searching
Exploring a graph from one vertex also builds a spanning tree, if you record the edge used to reach each new vertex. Breadth-first search (BFS) visits the start, then all its neighbours, then all their unvisited neighbours, layer by layer, so its tree reaches each vertex by a path with the fewest possible edges. Depth-first search (DFS) follows one route as far as it can before backing up to try another branch. Both reach every vertex of a connected graph exactly once, so both produce spanning trees, usually different ones. Networks use such trees to send broadcast messages without loops.
Minimum spanning trees
In a weighted graph every edge carries a number, such as a distance, a cost or a time. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. It answers questions like: what is the cheapest set of cables, pipes or roads that links every site? Checking every spanning tree is hopeless, because there can be astronomically many, \(n^{n-2}\) in a complete graph. Fortunately, a greedy approach, always taking the cheapest choice that is still allowed, is guaranteed to find a minimum spanning tree.
Kruskal's algorithm
1. List the edges in order of increasing weight. 2. Work down the list, adding each edge to the forest you are building unless it would join two vertices that are already connected, which would create a cycle. 3. Stop when \(n - 1\) edges have been added. Early on, the chosen edges are scattered in several pieces, and the algorithm gradually merges these pieces into one tree. If two edges have the same weight, either may go first; the total weight of the result is the same.
Worked example: Kruskal step by step
Six offices A to F have these link costs, in thousands of dollars: AB 4, AC 3, BC 2, BD 5, CD 6, CE 7, DE 1, DF 9, EF 8. 1. Take DE (1). 2. Take BC (2). 3. Take AC (3); now A, B, C are joined. 4. Skip AB (4): A and B are already connected through C. 5. Take BD (5), merging {A, B, C} with {D, E}. 6. Skip CD (6) and CE (7), which would close cycles. 7. Take EF (8), bringing in F. Five edges for six vertices, so stop. The minimum spanning tree is DE, BC, AC, BD, EF, with total cost 19, or $19,000.
Prim's algorithm
Prim's algorithm grows a single tree. Start at any vertex. At each step, look only at edges with one end in the tree and one end outside, and add the cheapest of them. On the office network, starting from A: the edges leaving A are AB 4 and AC 3, so add AC. From {A, C}, the cheapest edge out is BC 2. From {A, B, C}, it is BD 5. From D, add DE 1, and finally EF 8 beats DF 9. The result is the same tree as Kruskal's, total 19. With a priority queue, Prim's algorithm runs in about \(O(E \log V)\) time.
Why being greedy is safe
Split the vertices into any two non-empty groups. The cut property says that a cheapest edge crossing between the groups belongs to some minimum spanning tree. Prim's algorithm uses it directly: the tree so far is one group and everything else is the other. Kruskal's uses it too: an edge it accepts is the cheapest edge leaving one of the pieces built so far. So neither algorithm ever makes a choice it needs to undo. When all the edge weights are different, the minimum spanning tree is unique, so both algorithms must return the same tree.
Common mistakes to avoid
First, adding an edge in Kruskal's algorithm that closes a cycle; always check whether its two ends are already connected. Second, in Prim's algorithm, picking the cheapest edge anywhere instead of the cheapest edge leaving the current tree. Third, stopping too early or too late: a spanning tree on \(n\) vertices has exactly \(n - 1\) edges. Fourth, treating the MST as a map of shortest routes. In the office network, the tree route from C to D is C-B-D, costing 7, but the direct link CD costs only 6.
Key takeaways
A spanning tree includes every vertex, contains no cycle and has \(n - 1\) edges. Every connected graph has one, found by pruning cycle edges, growing without cycles, or by BFS or DFS. A minimum spanning tree has the least total weight. Kruskal's algorithm adds the cheapest edges overall, skipping any that close a cycle; Prim's algorithm grows one tree by its cheapest outgoing edge. The cut property explains why both greedy methods are correct, and an MST minimises total cost, not individual distances.
Flashcards
Flashcard
A subgraph that is a tree and contains every vertex
Test your understanding
Question 1 of 5
A connected graph has 15 vertices and 30 edges. How many edges does each of its spanning trees have?
Question 2 of 5
A weighted graph has edges PQ 1, QR 2, PR 3, RS 4 and QS 5. What is the total weight of its minimum spanning tree?
Question 3 of 5
In the same graph (PQ 1, QR 2, PR 3, RS 4, QS 5), Prim's algorithm starts at S. Which edge does it add first?
Question 4 of 5
How many different spanning trees does the cycle C₇ have?
Question 5 of 5
In a connected weighted graph, what is true of the route between two vertices u and v inside a minimum spanning tree?
