📑 Table of Contents▼

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

edit

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

edit
  • A biconnected graph on four vertices and four edges
    A biconnected graph on four vertices and four edges
  • A graph that is not biconnected. The removal of vertex x would disconnect the graph.
    A graph that is not biconnected. The removal of vertex x would disconnect the graph.
  • A biconnected graph on five vertices and six edges
    A biconnected graph on five vertices and six edges
  • A graph that is not biconnected. The removal of vertex x would disconnect the graph.
    A graph that is not biconnected. The removal of vertex x would disconnect the graph.
Nonseparable (or 2-connected) graphs (or blocks) with n nodes (sequence A002218 in the OEIS)
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

Structure of 2-connected graphs

edit

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

See also

edit

References

edit
  • 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 [online], 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
  • Diestel, Reinhard (2016), Graph Theory (5th ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-662-53621-6.
edit

📚 Artikel Terkait di Wikipedia

Biconnected component

In graph theory, a biconnected component or block (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes

Block graph

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component

Hamiltonian path

Hamiltonian graphs are biconnected, but a biconnected graph need not be Hamiltonian (see, for example, the Petersen graph). An Eulerian graph G (a connected

Cyclic graph

(graph theory), a cycle in a graph Forest (graph theory), an undirected graph with no cycles Biconnected graph, an undirected graph in which every edge belongs

Outerplanar graph

a cycle graph). As they showed, when the base graph is biconnected, a graph constructed in this way is planar if and only if its base graph is outerplanar

Dual graph

mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each

Perfect graph

perfect line graph L ( G ) {\displaystyle L(G)} is a line perfect graph. These are the graphs whose biconnected components are bipartite graphs, the complete

Glossary of graph theory

size. biclique Synonym for complete bipartite graph or complete bipartite subgraph; see complete. biconnected Usually a synonym for 2-vertex-connected, but