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

A cut of a graph is a partition $(S,V\setminus S)$ into two nonempty vertex sets. An edge crosses it when its endpoints lie on opposite sides. An edge set respecting a cut contains no crossing edge. A light edge crossing a cut has minimum weight among all crossing edges; there can be several tied light edges. These definitions concern the graph's weighted edges, independently of any particular spanning tree.

The minimum spanning tree cut property, in its safe-edge form, says: if an edge set $A$ is contained in some minimum spanning tree, a cut of a graph respects $A$, and $e$ is a light edge crossing a cut, then $A\cup \{e\}$ is contained in some minimum spanning tree.

Choose an MST $T$ containing $A$. If $e\in T$, nothing changes. Otherwise adding $e$ creates its unique fundamental cycle. The path in $T$ between the endpoints of $e$ must cross the chosen cut; take such an edge $f$. Since the cut respects $A$, $f\notin A$. Since $e$ is light, $w(e)\le w(f)$. The exchange $T-f+e$ is a spanning tree containing $A\cup \{e\}$, with total weight no greater than that of $T$. Minimality of $T$ forces equal optimum weight, proving the claim. Equal edge weights cause no difficulty: “safe” means belonging to some compatible optimum, not to every optimum.

True. A tree has exactly one path between any two vertices. For $e\notin T$, that path between the endpoints of $e$, together with $e$, is a fundamental cycle. Every cycle in $T\cup \{e\}$ must contain $e$, since $T$ itself is acyclic; deleting $e$ from such a cycle leaves that same unique path. Therefore the cycle is unique. Minimality of the spanning tree's weight is not needed for this assertion.

True. Delete $e\in T$; the resulting two connected components define a cut of a graph. If a crossing edge $f$ had $w(f)<w(e)$, the exchange $T-e+f$ would be a spanning tree of smaller total weight, contradicting the minimum spanning tree assumption. Thus $e$ is a light edge crossing a cut for this fundamental cut. It need not be uniquely light.

The displayed reference to index $n+1$ makes the nontrivial case $0\le n<k$; at $n=k$ the trees already agree and no further edge exists. Write $F=\{e_1,\dots ,e_n\}$ and $e=e_{n+1}$. If $e\in T^{\prime }$, its weight is at least the first nonprefix weight $w(e_{n+1}^{\prime })$ and at most that weight by hypothesis. Thus it ties for the next position, and simply ordering this tie with $e$ first gives the result.

Otherwise add $e$ to $T^{\prime }$. The resulting fundamental cycle contains an edge $f\notin F$: if its whole path lay in $F$, then $F\cup \{e\}\subseteq T$ would already contain a cycle. Every edge of $T^{\prime }\setminus F$, including $f$, has weight at least $w(e_{n+1}^{\prime })\ge w(e)$. Set $\tilde{T}=T^{\prime }-f+e$.

This is a spanning tree and still contains $F$. Its sorted order can begin with the specified prefix and then $e$, because all remaining edges have weight at least $w(e)$ and each prefix weight is at most $w(e)$. Replacing one entry of a multiset by a no-larger entry cannot increase any sorted order statistic: for every threshold, the number of entries below or equal to it cannot decrease. Hence $w({\tilde{e}}_j)\le w(e_j^{\prime })$ for every $j$. Ties may be ordered as needed; the paper prescribes nondecreasing weights, not an immutable global tie-break rule. This is spanning-tree prefix exchange.

Maintain two spanning trees $U,U^{\prime }$ whose sorted edge sequences share a prefix, initially of length zero. At the next position, select whichever next edge has smaller weight, breaking equal-weight ties arbitrarily. Keep that tree unchanged and apply spanning-tree prefix exchange from part (i) to the other tree. Both trees now have a common prefix one edge longer; one tree's sorted weight vector is unchanged and the other's cannot increase coordinatewise.

Repeat for $k$ positions. The final trees have all their edges in common, so they are one tree $\tilde{T}$. Throughout, the sorted weight vector of $U$ never exceeds its original vector from $T$, and that of $U^{\prime }$ never exceeds its original vector from $T^{\prime }$. Consequently their common final vector satisfies $w({\tilde{e}}_i)\le \min \{w(e_i),w(e_i^{\prime })\}$ at every position.

This proves the required existence without assuming either original tree was minimum. More generally, a minimum spanning tree has a coordinatewise minimum spanning-tree weight vector: after restricting the graph to edges of weight at most any threshold, a maximum forest contains at least as many edges as the corresponding portion of every other spanning tree. This threshold viewpoint explains why an optimum can simultaneously dominate every sorted coordinate, rather than merely having a smaller total weight.