Let G = (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G. A bridge of G is an edge whose removal disconnects G. A biconnected component of G is a maximal set of edges such that any two edges in the set lie on a common simple cycle. Figure 22.10 illustrates

Figure 22.10?

The articulation points, bridges, and biconnected components of a connected, undirected graph for use in Problem 22-2. The articulation points are the heavily shaded vertices, the bridges are the heavily shaded edges, and the biconnected components are the edges in the shaded regions, with a bcc numbering shown.

These definitions. We can determine articulation points, bridges, and biconnected components using depth-first search. Let G_? = (V. E_?)?be a depth-first tree of?G.

a.?Prove that the root of?G_? is an articulation point of G if and only if it has at least two children in G_?.

b.?Let???be a nonroot vertex of?G_?. Prove that ? is an articulation point of G if and only if ? has a child s such that there is no back edge from s or any descendant of s to a proper ancestor of ?. ? ?

c.?Let

Show how to compute??:low?for all vertices?????V?in?O(E)?time.

d.?Show how to compute all articulation points in?O(E)?time.

e.?Prove that an edge of?G?is a bridge if and only if it does not lie on any simple cycle of?G.

f.?Show how to compute all the bridges of?G?in?O(E)?time.

g.?Prove that the biconnected components of?G?partition the nonbridge edges of?G.

h. Give an O(E)-time algorithm to label each edge e of G with a positive integer e.bcc such that e.bcc = e?.bcc if and only if e and e0 are in the same biconnected component.

Transcribed Image Text:

Sv.d, min w.d : (u, w) is a back edge for some descendant u of v . v.low