Past exam of the short options course of the University of Oxford / 2023 / 7 (Graph theory)

A spanning tree of the connected graph $G$ is a subgraph containing every vertex, connected and without cycles in a graph. Equivalently, between every pair of vertices it has exactly one graph path. For a finite graph with $v$ vertices, it has $v-1$ edges.

A shortest-path tree rooted at $x$ is a spanning tree $T$ such that, for every vertex $v$, the unique $xv$ graph path in $T$ has minimum total edge length among all $xv$ graph paths in $G$. The objective is the sum of the lengths along each route, not the sum of all the tree's edge lengths.

For Dijkstra's algorithm, initialize $d(x)=0$ and $d(v)=\infty$ for other vertices, with no predecessor initially. Repeatedly select an unfinalized vertex $u$ of least tentative distance, finalize it, and relax each edge $uv$: if $d(u)+\ell (uv)<d(v)$, replace $d(v)$ by that value and set the predecessor of $v$ to $u$. Continue until all vertices are finalized. The predecessor edges form the shortest-path tree.

To justify finalization, consider a supposedly shorter route to the next selected vertex. Its first unfinalized vertex is preceded by a finalized one, whose relaxation would already have offered a tentative distance no greater than the length of that route's prefix. Nonnegative remaining lengths would contradict the selected vertex's minimal tentative label. Thus final labels are the true shortest distances. Strictly positive lengths also make predecessors have smaller distances, ruling out predecessor cycles in a graph.

Starting from $3$, the initial tentative distances to $0,1,2,4$ are $5,7,9,13$. Finalize $0$ next. Its edges improve these to $d(1)=5+1=6$, $d(2)=5+3=8$, and $d(4)=5+7=12$. No subsequent relaxation improves them. Hence one shortest-path tree isThese values follow either by completing Dijkstra's algorithm in the order $3,0,1,2,4$, or by observing that any internal vertex $w$ on a simple route adds $4w-1$ to the direct-edge cost: only the internal vertex $0$ can reduce it.

There is an index slip in the source: starting with $G_1$ and performing steps $1,\dots ,n$ produces the final graph $G_{n+1}$. Write $H$ for that final graph. The literal assertion for $G_n$ can fail: take a triangle with $\ell (xz)=3$, $\ell (xy)=2$, $\ell (yz)=1$. Before the final step the extra edge $yz$ remains; only the final deletion removes it.

The invariant is that $x$ and $y$ remain connected. Choose a simple $xy$ graph path $P$ in $H$. If an edge of $H$ did not lie in $P$, then at its processing time $P$ was still present and avoided that edge. The algorithm would therefore have deleted it, a contradiction. Thus every edge of $H$ lies in $P$. The final graph is precisely an $xy$ path and possibly isolated vertices.

Let $b_{\ast }$ be the smallest threshold for which the edges of length at most $b_{\ast }$ connect $x$ to $y$. This is exactly the optimum value of the bottleneck shortest path problem. While any edge longer than $b_{\ast }$ is being processed, every edge of some threshold-$b_{\ast }$ route is still present, because shorter edges have not yet been processed. Thus all edges longer than $b_{\ast }$ are deleted. The final path from part (i) consequently has maximum edge length at most $b_{\ast }$. It cannot have a smaller maximum by the definition of $b_{\ast }$, proving optimality. Ties in edge ordering do not affect this argument.

Take a minimum spanning tree $T$, for example one constructed by Kruskal's algorithm. Fix $v$ and let $e$ be a longest edge of the tree's unique $xv$ path. Deleting $e$ partitions $T$ into two components separating $x$ and $v$. Any alternative $xv$ path crosses this graph cut. If all of its edges were shorter than $e$, a crossing edge $f$ would let us replace $e$ by $f$, producing a spanning tree of smaller total length. This contradicts minimality of $T$.

Therefore every competing path has an edge at least as long as $e$, and the tree path solves the bottleneck shortest path problem. The same minimum spanning tree works simultaneously for every $v$; this is the minimax path property of a minimum spanning tree.