In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a biconnected graph is a connected and "nonseparable"
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
, meaning that if any one
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
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
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
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
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed ...
(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
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and its incident edges).
A biconnected
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
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''.
{, class="wikitable" style="text-align:center"
, +Nonseparable (or 2-connected) graphs (or blocks) with n nodes {{OEIS, id=A002218
, -
! Vertices !! Number of Possibilities
, -
! 1
, 0
, -
! 2
, 1
, -
! 3
, 1
, -
! 4
, 3
, -
! 5
, 10
, -
! 6
, 56
, -
! 7
, 468
, -
! 8
, 7123
, -
! 9
, 194066
, -
! 10
, 9743542
, -
! 11
, 900969091
, -
! 12
, 153620333545
, -
! 13
, 48432939150704
, -
! 14
, 28361824488394169
, -
! 15
, 30995890806033380784
, -
! 16
, 63501635429109597504951
, -
! 17
, 244852079292073376010411280
, -
! 18
, 1783160594069429925952824734641
, -
! 19
, 24603887051350945867492816663958981
Examples
File:4 Node Biconnected.svg, A biconnected graph on four vertices and four edges
File:4 Node Not-Biconnected.svg, A graph that is not biconnected. The removal of vertex x would disconnect the graph.
File:5 Node Biconnected.svg, A biconnected graph on five vertices and six edges
File:5 Node Not-Biconnected.svg, A graph that is not biconnected. The removal of vertex x would disconnect the graph.
See also
*
Biconnected component
In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...
References
* Eric W. Weisstein. "Biconnected Graph." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/BiconnectedGraph.html
* Paul E. Black, "biconnected graph", in Dictionary of Algorithms and Data Structures
nline Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html
External links
The tree of the biconnected components Java implementationin the jBPT library (see BCTree class).
Graph families
Graph connectivity