Homework Assignment #10

To answer questions about reachability / connectedness in undirected graphs.

Show all work. i.e., justify your answers.

Question 1. 3.31 a-d in the textbook

• When the problem says “show”, it means prove for a general undirected graph (not just for the example shown in the problem. Use good proof style (two columns, justify your steps, etc.)
• A simple cycle never includes the same vertex more than once.
• Biconnectedness (the ~ relation in the problem) is a relation on edges. A biconnected component is a collection of edges not vertices.
• The text defines biconnected components in terms of equivalence classes. While that definition works, it may not be clear to everyone. Here's an equivalent definition: A biconnected component is the largest (maximal) set of edges in which there is a simple cycle containing every pair of edges.
• A bridge is just a biconnected component that consists of a single edge.
• To help you verify your understanding of the problem, the separating vertices in the problem are B, D and L.
• Question: Does a biconnected component itself consist of a single simple cycle? Answer: No.
• Example:

Question Extra. (Not Required): 3.31 e-h in the textbook

• In part (e), you are doing a DFS on the original graph, not the meta-graph defined in part (d).
• In part (f), a proper ancestor of v is a vertex that is an ancestor of v in the DFS but which is not v itself. Make sure you understand how to answer this question because it will matter for part (h).
• For part (g), a plain-English definition of low(u): it’s the lowest pre() number seen on any ancestor (reachable by a back-edge) of any descendant of u (including u itself).
• In part (g), the descendants of a vertex include that vertex itself.
• In parts (g) and (h), pay careful attention to what you store on the DFS stack for a vertex u:
  • Your stack entry for u can contain the name/index of the parent vertex.
  • The stack entry for h can also contain the name/index of the most recent child explored, so that you know which child to explore next when the entry for u is on top of the stack again.
  • In part (g), you might want to add “LowestLowSeenSoFar” to the stack entry for u.
    • This suggestion allows you to track LowestLowSeenSoFar for vertex u across visits to u's children. Before you pop a stack entry for a child v of u, you can update LowestLowSeenSoFar(u) if the low() of the child v is lower.
    • Once you have finished exploring all children of vertex u and you're ready to pop the entry for u off the stack, LowestLowSeenSoFar(u) can be used to set low(u) once and for all.
    • It's just a suggested way of keeping track of what you're trying to compute (namely the low(u)) before you're actually done computing low(u).
    • If you'd rather just keep track of low(u) and update it as you encounter new children with lower lows, that is fine, too.
  • Keep in mind that when you explore a vertex (call it v), v may have neighbors that are currently in the search stack and marked visited. Call such a neighbor w. So if v has a (back-)edge to w and w is on the stack, then it may be the case that pre(w) < LowestLowSeenSoFar(v) and LowestLowSeenSoFar(v) should be set to pre(w) even though w is marked visited.
• In part (h), it's the argument you make in part (f) that gives you the insight you need to use low() to identify separating vertices.
  • The algorithm involves two stacks during DFS (per the hint in the text for part (h)). One stack contains edges and is used to identify biconnected components. The other stack is the normal DFS stack of vertices discussed above.