20. Elementary Graph Algorithms

Exercises

20.1-1

Available in the latest revision of the IM.

20.1-2

Available in the latest revision of the IM.

20.1-3

Available in the latest revision of the IM.

20.1-4

Available in the latest revision of the IM.

20.1-5

Available in the latest revision of the IM.

20.1-6 🌟

Demonstrates an effective algorithm design technique similar to that employed in the Boyer–Moore majority vote algorithm. The first pass, which takes $O(V)$ time, identifies a sole candidate, if any. The second pass checks (in linear time) whether the candidate is indeed a universal sink.

Available in the latest revision of the IM.

20.1-7

Available in the latest revision of the IM.

20.1-8

Available in the latest revision of the IM.

The IM contains the following incorrect claim: "One way to reduce the worst-case search time is to sort each linked list in a hash-table slot. Then, by using binary search, the worst-case search time for a neighbor of vertex $u$ is $\Theta(\lg \text{degree($u$)})$."

As explained in Exercise 11.2-3, binary search cannot be used with linked lists.

20.2-1

Available in the latest revision of the IM.

20.2-2

Available in the latest revision of the IM.

20.2-3

Available in the latest revision of the IM.

20.2-4

Available in the latest revision of the IM.

20.2-5

Available in the latest revision of the IM.

The example described in the IM is incorrect. Suppose that $v$ is discovered first as a neighbor of $s$. If $w$ preceedes $y$ in $Adj[v]$ then we get an edge $(w,x)$, otherwise we get an edge $(y,x)$.

20.2-6

Available in the latest revision of the IM.

20.2-7

Available in the latest revision of the IM.

★ 20.2-8

Available in the latest revision of the IM.

20.3-1

Available in the latest revision of the IM.

20.3-2

Available in the latest revision of the IM.

20.3-3

Available in the latest revision of the IM.

20.3-4

Available in the latest revision of the IM.

20.3-5

Available in the latest revision of the IM.

20.3-6

Available in the latest revision of the IM.

20.3-7 🌟

Explains why the white-path theorem considers paths consisting entirely of white vertices.

Available in the latest revision of the IM.

20.3-8

Available in the latest revision of the IM.

20.3-9

Available in the latest revision of the IM.

20.3-10

Available in the latest revision of the IM.

20.3-11

Available in the latest revision of the IM.

20.3-12

Available in the latest revision of the IM.

★ 20.3-13

Available in the latest revision of the IM.

20.4-1

Available in the latest revision of the IM.

20.4-2 🌟

Illustrates how to apply topological sorting as a preprocessing step to enable a bottom-up dynamic programming approach for counting all simple paths.

Available in the latest revision of the IM.

20.4-3

Available in the latest revision of the IM.

20.4-4

Available in the latest revision of the IM.

20.4-5

Available in the latest revision of the IM.

20.5-1

Available in the latest revision of the IM.

20.5-2

Available in the latest revision of the IM.

20.5-3

Available in the latest revision of the IM.

20.5-4

Available in the latest revision of the IM.

20.5-5

Available in the latest revision of the IM.

20.5-6

Available in the latest revision of the IM.

20.5-7

Available in the latest revision of the IM.

20.5-8

Available in the latest revision of the IM.

Problems

20-1 Classifying edges by breadth-first search

Available in the latest revision of the IM.

20-2 Articulation points, bridges, and biconnected components

Theorem 20.10 says that in a DFS tree of an undirected graph, there are no cross edges (edges between two subtrees that do not have an ancestor-descendant relationship). We use this fact throughout this exercise.

a.

If the root of $G_\pi$ has only one child, all other nodes are descendants of this single child. Removing the root simply removes the root itself, leaving the rest of the tree completely connected through that single child. Therefore, it cannot be an articulation point of $G$. Of course, if $G$ has only a single vertex, removing it creates an empty graph, which is assumed to be connected.

If the root of $G_\pi$ has two or more children, these children are roots of disconnected subtrees in the DFS forest. The only path between these subtrees is through the root. Therefore, removing the root disconnects the graph, making it an articulation point.

Proving the other direction is virtually the same.

b.

Suppose there is a child $s$ of $v$ whose subtree has no back edges reaching above $v$. This means the only way to reach the rest of the graph from $s$'s subtree is by traveling up the tree edges, which inevitably passes through $v$. If you remove $v$, you isolate $s$s subtree from the rest of the graph, proving $v$ is an articulation point.

Proving the other direction is virtually the same.

c.

We can compute $v.low$ during the DFS traversal in $O(E)$ time.

1. Initialize $v.low = v.d$ (discovery time) when a vertex is first visited.

2. For every adjacent vertex $w$ of $v$:

   1. If $w$ is not visited (it becomes a child in the DFS tree), recursively call DFS on $w$. After the recursive call returns, update $v.low = \min(v.low, w.low)$.

   2. If $w$ is visited and is not the parent of $v$ (meaning $(v, w)$ is a back edge), update $v.low = \min(v.low, w.d)$.

d.

Run the modified DFS from part (c).

• Track the number of children for the root. If children > 1, mark the root as an articulation point (using part (a)).

• For any non-root vertex $v$, examine the $low$ values of its children. Based on part (b), $v$ is an articulation point if it has a child $s$ such that $s.low \ge v.d$. This mathematically represents that no node in $s$'s subtree has a back edge jumping strictly higher than $v$.

These checks add $O(1)$ time per edge, maintaining the $O(E)$ time complexity.

e.

If an edge $e=(u,v)$ is a bridge, its removal disconnects the graph. If it were on a simple cycle, removing it would just force the path between $u$ and $v$ to go the "long way" around the rest of the cycle, meaning the graph would stay connected. Hence, a bridge cannot be on a simple cycle.

If $e=(u,v)$ does not lie on any simple cycle, then it is the only simple path between $u$ and $v$. Removing this edge eliminates all paths between $u$ and $v$, disconnecting the graph. Thus, it is a bridge.

f.

In a DFS tree, back edges always form cycles with the tree edges. Therefore, a back edge is never a bridge. We only need to check tree edges.

A tree edge $(v, s)$, where $s$ is a child of $v$, is a bridge if and only if there is no back edge from $s$'s subtree pointing to $v$ or any ancestor of $v$. Mathematically, this means $s.low > v.d$. By simply checking this condition during our DFS traversal, we can flag all bridges.

g.

The definition states a BCC is a maximal set of edges where any two edges lie on a common simple cycle. "Lying on a common simple cycle" is an equivalence relation for nonbridge edges (it is reflexive, symmetric, and transitive).

Because it is an equivalence relation, it naturally divides the set of all nonbridge edges into disjoint equivalence classes. These maximal equivalence classes are exactly the biconnected components. Because bridges don't lie on simple cycles (from part (e)), they are excluded from this partition.

h.

The main part executes as follows:

1. Maintain a stack of edges during the DFS.

2. When you traverse an edge (either a tree edge or a back edge), push it onto the stack.

3. When you finish processing a child $s$ of node $v$ and discover that $s.low \ge v.d$ (meaning $v$ is an articulation point separating $s$'s BCC), pop edges from the stack until you hit the tree edge $(v, s)$. Assign a new, unique $bcc$ positive integer label to all the edges you just popped. These edges form one complete biconnected component.

   1. When the popped group consists of exactly one edge, we identify it as a bridge and simply discard it from the stack without assigning it a BCC label.

After the main DFS traversal concludes, the algorithm must simply execute one last step:

1. While the stack is not empty, pop the remaining edges. They form the final biconnected component.

Because each edge is pushed onto the stack exactly once and popped exactly once, the entire labeling process runs in $O(E)$ time.

20-3 Euler tour

Available in the latest revision of the IM.

20-4 Reachability

Available in the latest revision of the IM.

20-5 Inserting and querying vertices in planar graphs

Available in the latest revision of the IM.

The IM's implementation of Newest-Neighbor returns the internal handle of a vertex instead of the vertex itself. By letting v.newest point to the vertex with a maximum handle Newest-Neighbor would properly return the corresponding object.