Jump to content
 







Main menu
   


Navigation  



Main page
Contents
Current events
Random article
About Wikipedia
Contact us
Donate
 




Contribute  



Help
Learn to edit
Community portal
Recent changes
Upload file
 








Search  

































Create account

Log in
 









Create account
 Log in
 




Pages for logged out editors learn more  



Contributions
Talk
 



















Contents

   



(Top)
 


1 Definition  





2 Examples  





3 Structure of 2-connected graphs  





4 See also  





5 References  





6 External links  














Biconnected graph






فارسی
Magyar

Русский
Українська

 

Edit links
 









Article
Talk
 

















Read
Edit
View history
 








Tools
   


Actions  



Read
Edit
View history
 




General  



What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Cite this page
Get shortened URL
Download QR code
Wikidata item
 




Print/export  



Download as PDF
Printable version
 
















Appearance
   

 






From Wikipedia, the free encyclopedia
 


Ingraph 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]

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

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

Examples

[edit]
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]
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Biconnected_graph&oldid=1227407199"

Categories: 
Graph families
Graph connectivity
Hidden categories: 
Articles with short description
Short description matches Wikidata
 



This page was last edited on 5 June 2024, at 15:02 (UTC).

Text is available under the Creative Commons Attribution-ShareAlike License 4.0; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.



Privacy policy

About Wikipedia

Disclaimers

Contact Wikipedia

Code of Conduct

Developers

Statistics

Cookie statement

Mobile view



Wikimedia Foundation
Powered by MediaWiki