(
graph theory,
algorithms:)
A
component of a
graph (undirected!) given by a stronger
connectivity than plain
connected components.
Definition
Given a graph
G,
define an
equivalence relation on the
edges: we say e~f
iff edges e,f are on some
simple cycle. The
biconnected components of
G are the
equivalence classes of
G/~. Naturally, every biconnected component is
connected, but biconnected components may split connected components.
The same vertex of the graph may participate in multiple biconnected components -- see articulation point.
The biconnected components of the following (connected!) graph:
*--* *--*
|\/ /|
|/\ / |
*--*--*
are these:
*--* * *--*
|\/ /|
|/\ / |
*--* *--*
Note the
duplication of the articulation points in the above diagrams.
Algorithmic considerations
An
online algorithm for dealing with connected components is
Tarjan's
union find with path compression. Tarjan also has another (more complex) algorithm, which does the same for biconnected components, and has the same
amortized time complexity. This second algorithm uses union find with path compression as a
subroutine.