Question

Biconnected componentsLet G=(V,E) be an undirected graph. For any two edges$\mathit{e}\mathbf{,}\mathit{e}\mathbf{\text{'}}\mathbf{}\mathbf{\in }\mathit{E}\mathbf{,}$, we’ll say$\mathit{e}\mathbf{:}\mathbf{}\mathbf{}\mathit{e}\mathbf{\text{'}}\mathbf{}$if either$\mathit{e}\mathbf{=}\mathit{e}\mathbf{\text{'}}\mathbf{}$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 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:

$Iow\left(u\right)=min\left\{\begin{array}{l}pre\left(u\right)\\ pre\left(w\right)\end{array}\right.$

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.

Short answer

(a) The relation e: e' is an equivalence relation since, it is reflexive, symmetric, and Transitive.

(b) The bridges are (B,D),(D,C) , (D,M) and the separating vertices are B, D, L

(c) The vertices corresponding to two different biconnected components are either disjoint or intersect in a single separating vertex can be proved by considering the biconnected branches.

(d) The resulting graph is a tree that has been proved.

(e) It can be proved by the connectivities of the DFS.

(f) It can be shown that a non-root vertex of e DFS tree is a separating vertex if and only if it has a child none of whose descendants (including themselves) has a back edge to a proper ancestor of v.

(g) The entire array of low values can be computed in linear time by the following expression $low\left(f\right)=min\left(low\left(f\right),low\left(v\right),t\right)$

(h) Separating vertices, bridges, and biconnected components of a graph can be found in $O\left(V+E\right)$time.

Step-by-step solution

Explain Biconnected components

Let G=(V,E) be an undirected graph. For any two edges $\mathit{e}\mathbf{,}\mathit{e}\mathbf{\text{'}}\mathbf{\in }\mathit{E}$, the relation is an equivalence relation. The equivalence classes into which this relation partitions the edges are called the biconnected components of G

Step 1: Show that :  is an equivalence relation (recall Exercise 3.29) on the edges.

(a)

Consider the undirected graph G(V,E) , that has two edges$e,e\text{'}\in E$. There exists that a simple cycle containing both e and e' or e: e' .

Since the edges are considered to be in an undirected graph ,so$\left(e,e\right)\in E$for all .

Hence e: e' is reflexive.

The edges exist in a simple cycle, which infers that$\left(e,e\text{'}\right)\in E$thenlocalid="1658918626972" $\left(e\text{'}e\right)\in E$.

Hence e: e' is symmetric.

Since the edges present in a simple cycle, if $\left(e,e\text{'}\right)\in E$and $\left(e\text{'},e\text{'}\text{'}\right)\in E$then .

$\left(e,e\text{'}\text{'}\right)\in E$

Hence e: e' is transitive.

Since e: e' is reflexive, symmetric and transitive , It is said be an equivalence relation on the edges.

Therefore, The relation e: e' is an equivalence relation

Step 3: Identify the bridges and separating vertices.

(b)

A bridge is an edge that is in a biconnected component all by itself. A biconnected component is a subgraph that cannot be broken by deleting any single node.

A separating vertex is a vertex whose removal disconnects the graph.

Consider the given undirected graph,

The bridges in the graph are, $\left(B,D\right),\left(D,C\right),\left(D,M\right),$because these edges are biconnected component all by themselves.

The separating vertices that disconnects the graph are, B , D , L

Therefore, The bridges are $\left(B,D\right),\left(D,C\right),\left(D,M\right)$and the separating vertices are $B,D,L.$

Step 4: Show that the vertices corresponding to two different biconnected components are either disjoint or intersect in a single separating vertex.

(c)

Consider the two biconnected branches $C_1$and $C_2$, that has more than two common vertices. Take any two of the vertices $u,v$, that u and v are connected in $C_1$and $C_2$.

The path between u and v in $C_1$is $C_2$and the path between and in is .The paths form a ring that shows that and are biconnected. This is a contradiction.

Therefore, it is impossible for two biconnected branches to have a same vertex.

Therefore, it has been proved that the vertices corresponding to two different biconnected components are either disjoint or intersect in a single separating vertex.

Step 5: Show that the resulting graph is tree

(d)

Consider the information:

Each biconnected component is collapsed into a single meta-node, and retain individual nodes for each separating vertex.

There is no edge between any biconnected branch and any other vertex that its cut point can reach. So after collapsing all biconnected components , there will be no loop. This forms a tree, if the original graph is connected.

There, it is shown that the resulting graph is tree.

Step 6: Show that the root of DFS is a separating vertex in a given condition.

(e)

Consider the DFS tree with root node r. For the root node r , all paths between all its subtree will pass through r. If there are two subtrees in r, that are not empty after removing the root, the subtrees will be disconnected. So, r is the cut point.

If r has no more than one subtree, then removing r doesnot affect connectivity.

Therefore, it has been shown that the root of the DFS is a separating vertex if and only if it has more than one child in the tree

Step 7: Show that a non-root of DFS is a separating vertex in a given condition.

(f)

Consider that the subtrees of the vertex v that have an edge pointing to an ancestor of v. All vertices in its subtree will be reachable after falling .

If v has subtree with no edge pointing to ancestor, then if is removed the subtree will be replaced by the disconnected. Hence, v is the cut point.

Therefore, it has been shown that the non-root of the DFS is a separating vertex if and only if it has more than one child in the tree.

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

(g)

Consider that each vertex define

$low\left(u\right)=min\left\{\begin{array}{l}pre\left(u\right)\\ pre\left(w\right)\end{array}\right.$

Where (v,w) is a back edge for some descendant v of u .

In the previsit process, initialize low (v) and pre (v) .

If v has back edge, let t be the minimum value of pre (w) among the edges evw .

In post visit , the parent of v is considered, and the low value of parent f is set as:

role="math" localid="1658917377942" $low\left(f\right)=min\left(low\left(f\right),low\left(v\right),t\right)$

Therefore, The entire array of low values can be computed in linear time by the following expression, $low\left(f\right)=min\left(low\left(f\right),low\left(v\right),t\right)$.

Step 9: Show the computing od separating veritices, bridges, and biconnected components in linear time.

(h)

For vertex v in the DFS tree, if it has more than one child or one parent u, then the child makes $low\left(u\right)\ge prev\left(v\right)$. Then is a cut point.

Process for biconnected branches:

Select edge in the graph and push it into the stack. If stack is not empty, set the top element as e(a,b). If not a is a cut point, push all unvisited edges onto the stack. If b is not a cut point push all the unvisited edges onto the stack. If a and b are cutpoints, access e(a,b), is popped off the stack.Thus the biconnected branches are computed.

Therefore, Separating vertices, bridges, and biconnected components of a graph can be found in O(V+E) time.