Let G = (V, E) be a connected, undirected graph. (In this course we follow the u

Question

Let G = (V, E) be a connected, undirected graph. (In this course we follow the usual convention that, unless indicated otherwise, an undirected graph does not have loops or multiple edges.) As usual n = |V| and m = |E|. An articulation point of G is a vertex whose removal disconnects G. As we saw in class, if you run DFS on G, then (because G is connected) the outer routine will have to make only one call Explore(G, r) for some vertex r, after which all vertices will be visited. The "tree" edges created in this process form a spanning tree T of G rooted at r. Prove that r is an articulation point if and only if it has at least two children in T. Let v notequalto r. The ancestors of v are the vertices on the simple path in T from v to r, inclusive. Proper ancestors exclude v. The descendants of v are those which have v as an ancestor. Prove that v is an articulation point if and only if there is a child s of v in T, such that no descendant of s has a back edge to a proper ancestor of v. Let low(v) = min{pre(w): exist descendant u of v such that (u, w) is a back edge}. Show how to compute all low(v) in time O(m). Show how to compute all articulation points in time O(m). Runtimes in this problem are in the word model (basic arithmetic etc. is in unit time).

Explanation / Answer

a) r has at least two children. Let u be the child of r whose discovery time is the earliest, and v be another child of r. Then u must be discovered right after r, so that at time d(u), all other nodes apart from r, are still undiscovered. Since v does not become u’s descendant, by white-path theorem, there must not be a path between u and v without passing r. In other words, removing r must disconnect u and v, so that r is an articulation point.

b) Consider the subtree of the DFS tree rooted at s. For each edge with an endpoint w in this subtree, its other end-point, say x, must either be v or within the subtree. (The reason is that: If (w, x) is a tree edge, x must be in the subtree; otherwise, (w, x) is a back edge, and by the given condition, w cannot link to a proper ancestor of v, so that it must link to v or a node in the subtree). In this case, we see that if we remove v, w and p must be disconnected. This implies v must be an articulation point.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.