Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 8

Start Prim's algorithm at vertex $1$, since the source does not specify a starting vertex. Write every undirected edge with its smaller endpoint first. With lexicographic tie-breaking, the accepted edges are $(1,2),(1,3),(2,4),(4,6),(4,5)$, of total weight 9.

Initially $(1,2)$ is the cheapest crossing edge. The next minimum is a weight-two tie between $(1,3)$ and $(2,4)$, so choose $(1,3)$. Then the weight-two tie between $(2,4)$ and $(3,4)$ is resolved in favour of $(2,4)$. Adding vertex $4$ exposes the weight-one edge $(4,6)$, which is selected next. Finally $(4,5)$ precedes $(5,6)$ among the weight-three choices. Every accepted edge crosses from the existing tree to a new vertex, as required by the minimum spanning tree cut property. A different starting vertex can produce a different accepted-edge order; the displayed answer fixes that unspecified choice. The algorithm is named for Robert C. Prim.

Sort edges by weight and then lexicographically. Kruskal's algorithm accepts $(1,2),(4,6),(1,3),(2,4),(4,5)$, again of total weight 9.

The two weight-one edges $(1,2),(4,6)$ join different components. Among weight-two edges, $(1,3)$ is accepted, then $(2,4)$ joins the two larger components; $(3,4)$ would now create a cycle and is rejected. Among weight-three edges, $(1,4)$ is rejected for the same reason, and $(4,5)$ joins the remaining vertex. Five accepted edges connect all six vertices, so the algorithm can stop. The disjoint-set data structure implements precisely these component tests. The eponym is Joseph Kruskal.

To find a minimum-weight acyclic subgraph, filter to the subgraph $G_{-}$ containing only strictly negative-weight edges, and run Kruskal's algorithm on those edges, accepting an edge exactly when it joins different current components. Return the resulting forest, with any omitted vertices regarded as isolated. Zero-weight edges may be omitted without worsening the objective.

To prove correctness, first remove all nonnegative edges from any feasible acyclic graph; removing them preserves acyclicity and cannot increase weight. Thus an optimum using only negative edges exists. Inside a connected component of $G_{-}$, any forest not yet connected can be extended by a negative crossing edge: some such edge exists because the original component is connected. Adding it preserves acyclicity and strictly reduces total weight. Consequently an optimum must span each component of $G_{-}$, and its restriction there must be a minimum spanning tree. Kruskal's algorithm finds exactly the resulting minimum spanning forest of $G_{-}$. This proves optimality among all acyclic subgraphs, including disconnected ones.

With $m_{-}$ negative edges, filtering costs $O(|V|+|E|)$, sorting costs $O(m_{-}\log (m_{-}+1))$, and the union-find operations take $O((|V|+m_{-})\alpha (|V|))$ time. A standard overall bound is $O(|V|+|E|\log (|E|+1))$ time. If there are no negative edges, the empty edge set is optimal.

Assume the graph is connected so that a minimum spanning tree exists, and let $T$ be the output of Kruskal's algorithm. With distinct weights there is a strict total edge ordering. Suppose another minimum spanning tree $T^{\prime }\ne T$ existed. Choose $e\in T\setminus T^{\prime }$ and increase only $w(e)$ by a positive $\epsilon$ so small that the strict ordering of all edge weights remains unchanged. For a finite graph such an $\epsilon$ exists, using less than the gap to the next larger weight; if $e$ is largest, any sufficiently small positive increase works.

Running Kruskal's algorithm again examines exactly the same order and makes exactly the same component decisions. It therefore still returns $T$, which must remain optimal for the perturbed weights. But $T$ has become more expensive by $\epsilon$, while $T^{\prime }$ is unchanged. They had equal original weight, so now $T^{\prime }$ is cheaper, a contradiction. This proves that distinct weights imply a unique minimum spanning tree.

The converse is false. A triangle with edge weights $1,1,2$ has a unique minimum spanning tree, consisting of its two weight-one edges. Its total is $2$, while either other spanning tree has total $3$. Thus equal edge weights permit, but do not force, multiple optimum trees. The same perturbation proof applies componentwise to a minimum spanning forest.