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

For a finite connected graph $G=(V,E)$ with undirected edges and edge weights $w$, a spanning tree is a connected, acyclic subgraph containing all vertices. It has $|V|-1$ edges. A minimum spanning tree is one minimizing the sum of its edge weights:It minimizes total weight, rather than the distance of every route from a chosen root. Equal edge weights may permit more than one minimum spanning tree; negative weights do not invalidate the definition.

A precise safe-extension form of the cut lemma for minimum spanning trees is as follows. Let $F\subseteq E$ be contained in some minimum spanning tree. Let $S$ be a nonempty proper subset of $V$, and suppose no edge of $F$ crosses the cut of a graph $(S,V\setminus S)$. If $e$ is any least-weight crossing edge, thenTo prove it, choose a minimum spanning tree $T$ containing $F$. If $e\in T$, it already certifies the claim. Otherwise inserting $e$ creates a graph cycle. The other part of that graph cycle must cross the cut of a graph, so choose a crossing edge $f\in T$. It does not belong to $F$, and $w(e)\le w(f)$. Then $T-f+e$ is a spanning tree containing $F\cup \{e\}$, of weight no greater than the optimum. It is therefore also optimal.

With $F=\varnothing$, a lightest crossing edge belongs to at least one minimum spanning tree. If that edge is uniquely lightest, it belongs to every minimum spanning tree, the strict version of the minimum spanning tree cut property. With ties, “every” would be false: in an equal-weight triangle either crossing edge can be omitted from some optimum.

Run Kruskal's algorithm in nonincreasing order of edge weight, accepting an edge exactly when its endpoints belong to different current connected components. Use a disjoint-set data structure to test and merge those components. Stop after accepting $|V|-1$ edges.

Equivalently, apply ordinary Kruskal's algorithm to $w^{\prime }(e)=-w(e)$. For every spanning tree,so minimizing transformed total weight is exactly maximizing original total weight. Thus the output is a maximum spanning tree. Equal weights may be processed in any fixed order. Sorting dominates the time complexity, giving $O(|E|\log |E|+|V|)$ with the usual efficient disjoint-set data structure.

Build a maximum spanning tree $T$ by the decreasing-weight version of Kruskal's algorithm. For the specified distinct endpoints $s,t$, find their unique graph path $P_T$ in $T$ by depth-first search, retaining predecessors to reconstruct it. Return that path and its minimum edge weight $b$.

For correctness, choose an edge $e$ of weight $b$ on $P_T$. Deleting it splits $T$ into two connected components, separating $s$ from $t$. No edge $f$ across this cut of a graph can have $w(f)>b$: replacing $e$ by $f$ would give a spanning tree of greater total weight, contradicting maximality of $T$.

Every $s$–$t$ graph path $P$ must cross the same cut of a graph, so it contains a crossing edge $f$ with $w(f)\le b$. Therefore its minimum edge weight is at most $b$. The tree route attains $b$, provingThis is precisely the widest path problem. The proof allows tied, zero and negative edge weights. It depends on maximizing the total tree weight, not on a shortest-distance algorithm.

Let $v=|V|$ and $e=|E|$. Sorting and Kruskal's algorithm take $O(e\log e+v)$ time; the tree search adds $O(v)$. HenceFor a connected simple graph with at least two vertices, $v-1\le e\le v(v-1)/2$, so the time is also $O(e\log v)$. The $O(e\log e+v)$ expression remains valid when parallel edges are permitted. If the two endpoints coincide, the empty path is returned, with bottleneck $+\infty$ under the usual empty-minimum convention; otherwise connectedness guarantees a nonempty route.