Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 7

A spanning tree is a connected acyclic subgraph containing every vertex of the original undirected graph. For a graph with $|V|$ vertices it has $|V|-1$ edges. A minimum spanning tree minimizes the sum of its edge weights over all spanning trees:Connectedness guarantees existence for a finite graph; equal weights can permit several minimizers.

Kruskal's algorithm sorts the edges and accepts an edge precisely when it joins two currently different connected components of a graph. A disjoint-set data structure maintains those components:

Kruskal(V, E, w):
    A = empty set
    make one disjoint set for each vertex in V
    for (u,v) in E sorted by nondecreasing w:
        if find(u) != find(v):
            add (u,v) to A
            union(u,v)
            if size(A) == size(V) - 1:
                break
    return A

An accepted edge merges two trees of the current forest. An edge within one component would complete a graph cycle and is skipped. On connected input, after $|V|-1$ acceptances the forest is a spanning tree. For a one-vertex graph the empty set is already the answer.

It is a greedy algorithm because it commits at every step to the cheapest remaining edge that can be added without creating a graph cycle, without revising earlier choices. The minimum spanning tree cut property explains why these locally cheapest admissible choices can be extended to an optimal spanning tree.

Processing by increasing weight, Kruskal's algorithm accepts $df$ of weight one and $cf$ of weight two, then rejects $cd$ of weight three because its endpoints are already connected. It accepts $ac$, $eh$, $fh$, skips $de$, accepts $be$, skips $bc$, and accepts $eg$. Seven accepted edges now connect all eight vertices.

The resulting minimum spanning tree isThe remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.

The procedure is Borůvka's algorithm. In the first round, visiting singleton components in the order $a,b,c,d,e,f,g,h$, the chosen edges are respectivelyThe set of new edges is $\{ac,be,cf,df,eh,eg\}$: repeated selections of $df$ and $eh$ insert no extra copy. The resulting two components are $\{a,c,d,f\}$ and $\{b,e,g,h\}$. Each chooses $fh$ in round two, producing the weight-36 tree from part (d). The within-round order of distinct insertions can therefore be $ac,be,cf,df,eh,eg$, followed by $fh$ in the next round; it need not be the globally sorted Kruskal order.

The required minimum spanning tree cut property says: for every nonempty proper subset $C\subset V$, the unique minimum-weight edge crossing the cut $(C,V\setminus C)$ belongs to every minimum spanning tree. Indeed, add this edge to a tree that lacks it. The resulting cycle contains another edge crossing the cut, which is strictly heavier; replacing that edge decreases the total weight.

For the general proof, assume all edge weights are distinct. Fix the components at the beginning of a round, as the given procedure does. Each selected edge is the unique lightest edge across one of their cuts, so belongs to every minimum spanning tree. Inductively, the entire selected set is contained in such a tree and is therefore acyclic. While there is more than one component, connectedness supplies an outgoing edge for each, so at least two components merge. The finite process terminates connected. A connected subgraph of a spanning tree must be that whole tree, proving that the returned set is a minimum spanning tree.