stringtranslate.com

Biconnected graph

In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.

The property of being 2-connected is equivalent to biconnectivity, except that the complete graph of two vertices is usually not regarded as 2-connected.

This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection).

The use of biconnected graphs is very important in the field of networking (see Network flow), because of this property of redundancy.

Definition

A biconnected undirected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and its incident edges).

A biconnected directed graph is one such that for any two vertices v and w there are two directed paths from v to w which have no vertices in common other than v and w.

Examples

Structure of 2-connected graphs

Every 2-connected graph can be constructed inductively by adding paths to a cycle(Diestel 2016, p. 59).

See also

References

External links