Low-link and components

Questions 1 to 5 of 8

1. 1. A DFS gives each vertex v a low value, low[v]. Vertex p is the parent of v, and tin[p] is p's entry time. Which test marks the tree edge from p to v as a bridge?

   low[v] >= tin[p]low[v] > tin[p]low[p] > tin[v]low[v] > tin[v]
2. 2. For a vertex p that is not the DFS root, which test says p is an articulation point because of its child v?

   low[v] > tin[p]low[v] == tin[v]low[v] >= tin[p]low[p] >= tin[v]
3. 3. The DFS root has exactly one child in the DFS tree. Is the root an articulation point?

   Yes, because the root always has the smallest entry time.No, because removing the root leaves one subtree, so it is not a cut vertex.Yes, if the root has any back edge.Only when the graph has parallel edges.
4. 4. Vertices 0 and 1 are joined by two parallel edges, A and B. The DFS starts at 0, goes along A to 1, and skips every edge that leads back to the parent vertex 0. What is the result?

   No bridges, because parallel edges cancel out.Edge A is reported as a bridge, even though removing A still leaves 0 and 1 joined by B.Both A and B are reported as bridges.Edge B is reported as a bridge, because the DFS never looks at it.
5. 5. Why is the graph you get by shrinking each strongly connected component a DAG, meaning it has no directed cycles?

   Shrinking removes every edge, so no cycle can remain.Any directed cycle puts all its vertices in one component, so no cycle can run between two different components.Tarjan's method deletes the back edges before it shrinks the components.Each component has exactly one outgoing edge.