Three Algorithms on Graphs

Construct a minimum spanning tree for the undirected graph $\mathfrak {G}=(V, E)$ with vertex set $V=\left\{ v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}, v_{8}, v_{9}\right\}$ and edge set $E=\left\{ \left(v_{1}, v_{2} ; 18\right),\left(v_{1}, v_{3} ; 2\right),\left(v_{3}, v_{2} ; 4\right),\left(v_{3}, v_{4} ; 6\right),\left(v_{3}, v_{5} ; 8\right),\left(v_{4}, v_{6} ; 5\right),\left(v_{5}, v_{4} ; 4\right),\left(v_{6}, v_{1} ; 7\right),\left(v_{6}, v_{8} ; 4\right),\left(v_{6}, v_{7} ; 3\right),\left(v_{7}, v_{5} ; 1\right),\left(v_{7}, v_{8} ; 7\right),\left(v_{8}, v_{1} ; 5\right),\left(v_{8}, v_{9} ; 3\right),\left(v_{9}, v_{1} ; 1\right)\right\}$. The third parameter in brackets is the edge weight.

Let $e$ be an edge of maximum weight in some simple cycle $C$ of the graph $\mathfrak {G}=(V, E)$. Prove that

Let $\mathfrak {T}=(V, T)$ be a minimum spanning tree for a weighted undirected graph $\mathfrak {G}=(V, E)$ with $n$ vertices, $c$ an edge labeling. Let $(e_{1}, e_{2}, \ldots , e_{n-1})$ be the sequence of edges of $T$, ordered by increasing $c\left(e_{i}\right)$. Let $\mathfrak {T}^{\prime }$ be an arbitrary spanning tree for $\mathfrak {G}$ with edges $\left(d_{1}, d_{2}, \ldots , d_{n-1}\right)$, ordered by increasing $c\left(d_{i}\right)$. Show that $c\left(e_{i}\right) \leqslant c\left(d_{i}\right)$ for all $i=1, \ldots , n-1$. Hint. Consider the forest of trees $\mathfrak {T}_{i, m}$ consisting of edges $e_{j}, j<i$, and edges $d_{\ell }, \ell \leqslant i$.

A drawback of Kruskal's algorithm is the need to check for the presence of cycles at each step, which is itself a fairly difficult task. The following algorithm was independently proposed by V. Jarník, R. Prim, and E. Dijkstra.

1. Choose an arbitrary vertex $a$; it is itself a tree (without edges).

2. At each step, add to the existing tree the edge of least weight, one of whose vertices belongs to the tree and the other does not. Prove the correctness of this algorithm for connected graphs, by analogy with Theorem 80 (Correctness of Kruskal’s algorithm): the result of running Kruskal’s algorithm is a minimum spanning tree of the input graph $\mathfrak {G}=(V, E)$ with edge-labeling function $c$.

Let $\mathfrak {T}=(V, T)$ be a depth-first spanning tree constructed by the depth-first search algorithm for the graph $\mathfrak {G}=(V, E)$. Prove that for every back edge $(u, v) \in E \backslash T$, either $u$ is an ancestor of $v$ in $\mathfrak {T}$, or $v$ is an ancestor of $u$ in $\mathfrak {T}$.

Modify the depth-first search algorithm so that it computes $\operatorname {Up}[v]$ and prints the list of all bridges of the graph.

Starting from vertex $v_{1}$, traverse (number) the vertices of the given undirected graph $\mathfrak {G}=(V, E)$ using the depth-first search algorithm and construct the tree of this traversal. $V=\left\{ v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}, v_{8}, v_{9}, v_{10}\right\} , E=\left\{ \left(v_{1}, v_{2}\right),\left(v_{1}, v_{4}\right),\left(v_{1}, v_{8}\right),\left(v_{7}, v_{8}\right),\left(v_{2}, v_{9}\right),\left(v_{9}, v_{5}\right),\left(v_{3}, v_{8}\right),\left(v_{6}, v_{3}\right),\left(v_{3}, v_{7}\right),\left(v_{6}, v_{7}\right),\left(v_{10}, v_{9}\right),\left(v_{10}, v_{5}\right)\right\}$. Which back edge $e \in E \backslash T$ and cycle in $\mathfrak {G}$ were discovered first in this traversal? Compute the value $\operatorname {Up}[v]$ for each vertex $v$ and determine all bridges of the graph $\mathfrak {G}$. Assume that all adjacency lists are ordered by increasing vertex number, and the vertex with the smallest number is chosen.

Modify the depth-first search algorithm so that it allows listing all connected components of an undirected graph.

If in a directed graph $\mathfrak {G}=(V, E)$ there exists a vertex $r$ from which all other vertices are reachable, then for it too one can define the notion of a spanning (now directed) tree: a tree $\mathfrak {T}=(V, T)$ with root $r$. Determine which of the spanning tree construction algorithms can be adapted for constructing a spanning tree in a directed graph: Kruskal's algorithm, the Jarník-Prim-Dijkstra algorithm, the depth-first search algorithm.

For the following weighted graph $\mathfrak {G}=(V, E)$ and vertex $a \in V$, determine the lengths of the shortest paths from $a$ to the other vertices of $\mathfrak {G}$ and construct the tree of these paths. Here $V=\left\{ a, b, c, d, e, f\right\} , E=\left\{ (a, b ; 154),(a, c ; 17),(a, d ; 214), (a, e; 63), (b, d; 25), (c, e; 33), (c, d; 192), (c, b; 123), (d, f; 5), (e, f; 140), (d, e; 10)\right\}$.

Where in the proof of correctness of Dijkstra's algorithm is the nonnegativity of edge weights used? Give an example of a graph (with negative weights) for which Dijkstra's algorithm gives an incorrect answer.

Theorem 83 (Correctness of Dijkstra's algorithm): Dijkstra's algorithm constructs the shortest-path tree from vertex $a$ to every vertex reachable from it, and for each such vertex $v$ determines the length $D[v]$ of the shortest path to it from $a$. In the proof, by induction on $k$: let $R_{k}$, $D_{k}$, $F_{k}$ denote the value of $R$ and the contents of the arrays $D$, $F$ after $k$ iterations of the algorithm's main loop, and let $w_{k}$ be the vertex chosen at step $k+1$.

Show that in the proof of the induction step of Theorem 83 on p. 248, the vertex $w_{k}$ can only be second-to-last on the shortest path from $a$ to $u \in V \backslash \left(R_{k} \cup \left\{ w_{k}\right\} \right)$.

How many times can the value $D[v]$ change for a single vertex $v$ during the execution of Dijkstra's algorithm on a graph with six vertices? Give an example for each possible case.

Let a vertex $a$ be chosen in a graph $\mathfrak {G}$, and suppose that for every vertex $v \in V$ reachable from $a$ there is a unique shortest path from $a$ to $v$. Prove that the edges of all these paths form a directed tree rooted at $a$.