Algorithms (1st Edition)


Chapter 3, Problem 31

Biconnected components. Let G = (V, E) be an undirected graph. For any two edges e, e′ ∈ E, we’ll say e ~ e′ if either e = e′ or 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 vertex is 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 also 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 backedge to a proper ancestor of v.


(g) For each vertex u define:

Show that the entire array of low values can be computed in linear time.


(h) Show how to compute all separating vertices, bridges, and biconnected components of a graph in linear time. (Hint: Use low to identify separating vertices, and run another DFS with an extra stack of edges to remove biconnected components one at a time.)


Solution

Step 1 of 11

Consider an undirected graph.

Let and be two edges and. The edge is said to be congruent to for the following conditions:

• If there is a cycle containing both and.

Step 2 of 11

(a)

Equivalence relation on edges:

Reflexivity:

Consider two edges . Since , by the definition of the given relation, .

Thus, the given relation is obviously reflexive.

Symmetry:

Consider . Thus either or there is a cycle contains and .

Since the given graph is undirected, either or there is a cycle contains and is also true. That is, .

Thus, the given relation is also obviously symmetric.

Transitivity:

Consider and are present in cycle. Also, consider and are present in cycle.

if either and contains all three edges, and , then proof is over as .

If not then neither nor can be common to both cycles and.

Also, andmust share some edges along with .

Starting from, move in both directions on the cycle, until a vertex(and) in is reached.

Picture 2

• Now there are two simple paths(one is green and another one is red) in .

• Remove the path that does not contains edge (i.e, red path)

Picture 4

• On removing the red path, it results in a simple cycle containing both and . Hence.

Thus, the given relation is transitive.

Therefore, the relation is an equivalence relation.

Step 3 of 11

(b)

Biconnected components:

The equivalence relation(proved in part a) helps to partition the edges of the given graph as biconnected components.

Thus, the following are the biconnected components of the given graph:

Bridges:

• By the definition, a biconnected component by itself is a bridge. In the given graph ,and are the biconnected components by itself.

Thus, the bridges for the graph are , and .

Separating vertices:

Comments (1)

Step 4 of 11

If a graph become disconnected on removing a vertex, then that vertex is called separating vertex.

Therefore, B , D and L are the separating vertices, because on removing these vertices from the graph, the graph becomes disconnected.

Step 5 of 11

(c)

It is required to prove that, any two biconnected components share only one vertex or none. If two biconnected components does not share any vertex, then the biconnected components are disjoint.

First, prove that two bi-connected components share at most one vertex(i.e. either one or none), by contradiction.

• By contradiction, assume that two biconnected components and share two vertices and .

• So, there must be a path from to in both and because in each component there is a simple cycle containing one edge incident on and one edge incident on .

• The union of these two paths results in a cycle containing some edges from and some edges from .

• It implies that an edge in is related to an edge in . Since, is a bi connected component, an edge in must be related to itself or must be related to another edge in . Thus, it is a contradiction.

Therefore, it is proved that two bi-connected components share at most one vertex.

Now it is required to prove that if two bi-connected components share a vertex, that should be a separating vertex.

• Assume that two biconnected components and share a common vertex u.

• Also, assume and be the edges corresponding to u in two components and respectively.

• On removing the vertex u , if the graph becomes disconnected, the proof is over that the common vertex is separating vertex.

• If graph does not become disconnected on removing common vertex, then there must be a path between and that does not pass through .

• Then ,the union of that path , and forms a simple cycle that contains one edge from and another edge from . This means an edge in is related to another edge in and an edge in is related to another edge in . This is a contraction.

Therefore, it is proved that two biconnected components share single separating vertex or none.

Step 6 of 11

(d)

By definition, a tree is a graph without cycles.

If each biconnected component in the graph is replaced with a single meta-node, then the resulting graph will be a tree, because each biconnected component represents a cycle and each cycle is replaced by a single node.

Prove this by contradiction.

• Assume, after replacing each bi-connected component with a single meta-node there is a cycle in the resulting graph.

• This means that this cycle contains edges from two biconnected components. But it is impossible, because by definition, edges in one component does not related to edges in another component.

• Thus, it is a contraction.

Therefore, it is proved that the resulting graph does not contains a cycle and thus the resulting graph is a tree.

Step 7 of 11

(e)

• Assume the root of the DFS tree has only one child. This means that the root is a leaf in the graph. Removing the root still leaves the tree connected.

Thus, the root is not a separating vertex if DFS tree has only one child.

• Now assume, the root of the DFS tree has more than one child. The DFS (Depth First Search) from the first child(root) explores every reachable vertex along a path, which is not passing through the root.

Picture 5

• As the graph is undirected graph, there will be no edges subtree of first child to that of any other child.

Step 8 of 11

That is, a path from any vertex in the subtree of first child to any other vertex in the other sub trees of other children must pass through the root only.

Therefore, removing the root disconnects the tree, if the root contains more than one child.

Step 9 of 11

(f)

A back edge is an edge drawn from a child to its ancestor.

• Assume v is a non-root vertex and is its descendent. Also assume there is a back edge from descendant of to an ancestor of . This means, each child v can reach the entire tree above the vertex , even though v is removed.

• That is graph is still connected after removing vertex .

• Now, assume v has a child and none of its descendent have a back edge to an ancestor of . That means, there exists no path between ancestor of and .

• So, the graph will be disconnected after removing vertex .

Therefore, it is proved that v is a separating vertex, if and only if descendants of v has a back edge to a proper ancestor of v .

Step 10 of 11

(g)

Run DFS algorithm on the given graph.

• While exploring each vertex u, DFS looks at the edges like (u,v). where v is the neighbour of u. Save the pre(v) value for all neighbours of u at vertex u.

• Also, allow each child v of u pass its low value to the parent u when it is popped from the stack.

• Now low(u) will be the minimum of pre(u) and all low(v).

Since, DFS explores all the nodes, in a single pass of DFS the whole array can be computed. Also, it is known that DFS runs in O(|V|+|E|) time, which is linear.

Step 11 of 11

(h)

Run DFS on the given graph as discussed in the part g and computer entire array low.

Separating vertex:

If u is a separating vertex, then it satisfies the following condition:

pre(u) < low(v) where v is the child of u.

Thus, separating vertices can be identified while computing the low array.

Biconnected components and bridges:

If u is a separating vertex (i.e. pre(u) < low(v)), then the sub tree with v as the root must be in a new biconnected components.

• Maintain an extra stack of edges to store all the edges.

• While exploring a child v of separating vertex u, push an extra “mark” (to identify the subtree with root v).

• While exploring vertex v, push the edges of sub tree of v into extra stack.

• When DFS returns to vertex v and popped v from the stack, pop the edges (sub tree) stored in the extra space, till the “mark”. All these popped edges will be a new biconnected component.

• Also, it is known that if the biconnected components contains only single edge, that single edge will the bridge.