= Solution
{c}
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 order
$$
1,\ \frac32,\ 2,\ \frac52,\ 3,\ \frac72,\ldots.
$$
The horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produce
$$
\boxed{\begin{aligned}
E(T)={}&\{(x,y)(x+1,y):1\le x<n,\ 1\le y\le n,\ x\ge y-1\}\\
&\cup\{(x,y)(x,y+1):1\le x\le n,\ 1\le y<n,\ y\ge x\}.
\end{aligned}}
$$
There 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 is
$$
\boxed{w(T)=\left[\frac{n(n+1)(n+2)}6-1\right]+\frac{n(n-1)(2n+5)}{12}=\frac{(n-1)(4n^2+13n+12)}{12}.}
$$
For $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.
\Image[/past-exam-of-the-short-options-course-of-the-university-of-oxford/2021-grid-spanning-tree.png]
{title=Kruskal spanning tree of the weighted grid, with accepted horizontal and vertical edges highlighted}
Back to article page
