A connected component of a graph G is a maximal connected induced subgraph, that is, a connected induced subgraph that is not itself a proper subgraph of any other connected subgraph of G

**CONNECTED COMPONENT**

A
connected component of a graph G is a maximal connected induced subgraph, that
is, a connected induced subgraph that is not itself a proper subgraph of any
other connected subgraph of G

*A graph and one of its subgraphs.*

The above
Figure is a connected graph. It has only one connected component, namely
itself. Following figure is a graph with two connected components.

**1. BICONNECTED COMPONENTS**

An
articulation point of a graph is a vertex v such that when we remove v and all
edges incident upon v , we break a connected component of the graph into two or
more pieces.

A
connected graph with no articulation points is said to be biconnected.
Depth-first search is particularly useful in finding the biconnected components
of a graph.

The
problem of finding articulation points is the simplest of many important
problems concerning the connectivity of graphs. As an example of applications
of connectivity algorithms, we may represent a communication network as a graph
in which the vertices are sites to be kept in communication with one another.

A graph
has connectivity k if the deletion of any k-1 vertices fails to disconnect the
graph. For example, a graph has connectivity two or more if and only if it has
no articulation points, that is, if and only if it is biconnected.

The
higher the connectivity of a graph, the more likely the graph is to survive the
failure of some of its vertices, whether by failure of the processing units at
the vertices or external attack.

We shall
here give a simple depth-first search algorithm to find all the articulation
points of a connected graph, and thereby test by their absence whether the
graph is biconnected.

1.
Perform a depth-first search of the graph, computing dfnumber [v] for each
vertex v. In essence, dfnumber orders the vertices as in a preorder traversal
of the depth-first spanning tree.

2. For
each vertex v, compute low [v], which is the smallest dfnumber of v or of any
vertex w reachable from v by following down zero or more tree edges to a
descendant x of v (x may be v) and then following a back edge (x, w). We
compute low [v] for all vertices v by visiting the vertices in a postorder
traversal. When we process v, we have computed low [y] for every child y of v.
We take low [v] to be the minimum of a. dfnumber [v],b. dfnumber [z] for any
vertex z for which there is a back edge (v, z) and c. low [y] for any child y
of v.

Now we
find the articulation points as follows.

a. The root
is an articulation point if and only if it has two or more children. Since
there are no cross edges, deletion of the root must disconnect the subtrees
rooted at its children, as a disconnects {b, d, e} from {c, f, g} in Fig..

b. A vertex
v other than the root is an articulation point if and only if there is some
child w of v such that low [w] â‰¥ dfnumber [v]. In this case, v disconnects w
and its descendants from the rest of the graph. Conversely, if low [w] <
dfnumber [v], then there must be a way to get from w down the tree and back to
a proper ancestor of v (the vertex whose dfnumber is low [w]), and therefore
deletion of v does not disconnect w or its descendants from the rest of the
graph.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Analysis and Design of Algorithm : Traversals, Branch and Bound : Connected Component and Biconnected Components |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.