From Surf Wiki (app.surf) — the open knowledge base
Biconnected graph
Type of graph
Type of 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
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.
| Vertices | Number of Possibilities | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | ||||||||||||||||||||
| 1 | ||||||||||||||||||||
| 1 | ||||||||||||||||||||
| 3 | ||||||||||||||||||||
| 10 | ||||||||||||||||||||
| 56 | ||||||||||||||||||||
| 468 | ||||||||||||||||||||
| 7123 | ||||||||||||||||||||
| 194066 | ||||||||||||||||||||
| 9743542 | ||||||||||||||||||||
| 900969091 | ||||||||||||||||||||
| 153620333545 | ||||||||||||||||||||
| 48432939150704 | ||||||||||||||||||||
| 28361824488394169 | ||||||||||||||||||||
| 30995890806033380784 | ||||||||||||||||||||
| 63501635429109597504951 | ||||||||||||||||||||
| 244852079292073376010411280 | ||||||||||||||||||||
| 1783160594069429925952824734641 | ||||||||||||||||||||
| 24603887051350945867492816663958981 |
Structure of 2-connected graphs
Every 2-connected graph can be constructed inductively by adding paths to a cycle .
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 [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
- {{citation
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Biconnected graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report