Past exam of the short options course of the University of Oxford / 2021 / 7 / a

For a finite connected graph, a spanning tree contains every graph vertex and is connected and acyclic. A minimum spanning tree minimizes ${\sum }_{e\in E(T)}w(e)$ over all such trees. A shortest-path tree rooted at $v$ is a spanning tree whose unique $v$-to-$u$ graph path has length $d_G(v,u)$ for every graph vertex $u$. Here the weighted path length is the sum of its edge weights. The two optimizations generally differ, as (b) shows. Connectedness is needed for either spanning-tree object to exist.

For the grid, Kruskal's algorithm examines edges in nondecreasing order of weight and accepts an edge exactly when it joins two different components of the current forest. The weights are encountered in the orderThe horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produceThere are $(n-1)(n+2)/2$ horizontal and $n(n-1)/2$ vertical edges, totaling $n^2-1$. Every accepted edge attaches a previously isolated graph vertex to the component already built, so the result is connected and acyclic. The correctness theorem for Kruskal's algorithm, which follows from the minimum spanning tree cut property, proves minimality. Its total cost isFor $n=1$ the tree has one graph vertex, no edges and cost zero. The source's numbered items specify the two edge types; the following subanswers record their contributions to the algorithm.

At weight $y$ the edges considered are precisely the horizontal edges in row $y$. For $y=1$ all $n$ graph vertices in that row are isolated, so all $n-1$ edges are accepted. For $y\ge 2$, the first $y-1$ graph vertices in that row already belong to the one component built by earlier stages, because vertical columns $1,\dots ,y-1$ have already been processed. The other graph vertices are isolated. Thus the edges with $x<y-1$ would create a graph cycle, and all the edges with $x\ge y-1$ are accepted, successively attaching the remaining graph vertices. The rule isThe selected edges of equal weight have no cycles after the existing component is contracted, so tie ordering does not affect this conclusion. Their combined contribution to the minimum spanning tree cost is

At weight $x+1/2$, column $x$ is considered just after horizontal row $x$. At this point its first $x$ graph vertices already lie in the component built so far, while graph vertices above them in that column are isolated. Consequently vertical edges with $y<x$ create a graph cycle, while those with $y\ge x$ attach the isolated graph vertices in a chain:Together with the horizontal rule this gives an induction on the alternating row and column stages and justifies the component description used in both numbered answers. The vertical contribution to the minimum spanning tree cost is