Biconnected componentsLet G=(V,E) be an undirected graph. For any two edges, we’ll sayif eitheror there is a (simple) cycle containing both e and e'.
a. Show that : is an equivalence relation (recall Exercise 3.29) on the edges.
The equivalence classes into which this relation partitions the edges are called the biconnected components of G . A bridge is an edge which is in a biconnected component all by itself.
A separating vertexis a vertex whose removal disconnects the graph.
b. Partition the edges of the graph below into biconnected components, and identify the bridges and separating vertices.
Not only do biconnected components partition the edges of the graph, they almost partition the vertices in the following sense.
c. Associate with each biconnected component all the vertices that are endpoints of its edges. Show that the vertices corresponding to two different biconnected components are either disjoint or intersect in a single separating vertex.
d. Collapse each biconnected component into a single meta-node, and retain individual nodes for each separating vertex. (So there are edges between each component node and its separating vertices.) Show that the resulting graph is a tree.
DFS can be used to identify the biconnected components, bridges, and separating vertices of a graph in linear time.
e. Show that the root of the DFS tree is a separating vertex if and only if it has more than one child in the tree.
f. Show that a non-root vertex v of the DFS tree is a separating vertex if and only if it has a child v' none of whose descendants (including itself) has a back edge to a proper ancestor of v .
g. For each vertex u define:
Where (v,w) is a back edge for some descendant v of u.
(h) Show how to compute all separating vertices, bridges, and biconnected components of a graph in linear time.
