쌍접합 그래프

Biconnected graph
관련 토픽
그래프 연결

그래프 이론에서, 쌍접합 그래프는 연결된 "분리할 수 없는" 그래프이며, 어떤 정점이 제거되더라도 그래프는 연결된 상태로 유지된다는 것을 의미합니다.따라서 쌍접합 그래프에는 꼭지점이 없습니다.

2개의 정점의 완전한 그래프가 보통 2개의 연결로 간주되지 않는다는 점을 제외하고 2개의 연결 속성은 2개의 연결성과 동일합니다.

이 속성은 단일 가장자리(또는 연결)를 제거할 때 연결이 끊어지지 않도록 이중 이중으로 그래프를 유지하는 데 특히 유용합니다.

네트워크 분야(「네트워크 플로우」를 참조)에서는, 쌍접속 그래프의 사용이 매우 중요합니다.이는 용장성이라는 속성 때문입니다.

정의.

쌍방향 무방향 그래프는 단일 정점(및 사고 가장자리)을 삭제하여 절단되지 않은 연결된 그래프입니다.

쌍접합 방향 그래프는 임의의 2개의 정점 v와 w에 대해 v와 w 이외의 공통의 정점이 없는 v에서 w로의 2개의 방향 경로가 있는 그래프입니다.

n개의 노드를 가진 분리할 수 없는(또는 2개의 접속된) 그래프(또는 블록) (OEIS의 시퀀스 A002218)
꼭지점 가능성 수
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

예

  • A biconnected graph on four vertices and four edges

    4개의 정점과 4개의 모서리에 연결된 그래프

  • A graph that is not biconnected. The removal of vertex x would disconnect the graph.

    연결되지 않은 그래프입니다.정점 x를 제거하면 그래프의 연결이 끊어집니다.

  • A biconnected graph on five vertices and six edges

    5개의 정점과 6개의 모서리에 연결된 그래프

  • A graph that is not biconnected. The removal of vertex x would disconnect the graph.

    연결되지 않은 그래프입니다.정점 x를 제거하면 그래프의 연결이 끊어집니다.

「 」를 참조해 주세요.

레퍼런스

  • 에릭 W. 와이스틴"연결된 그래프"From Math World: 울프램 웹 리소스.http://mathworld.wolfram.com/BiconnectedGraph.html
  • Paul E. Black, "연결 그래프", 알고리즘 및 데이터 구조 사전 [온라인]에서 Paul E.미국 국립표준기술연구소 검정색2004년 12월 17일 (오늘 갱신)제공처: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html

외부 링크