Biconnected Component¶
Definition¶
Definition 1
Biconnected graph는 2개 이상의 정점을 갖고 있으며, 1개의 정점을 제거하여도 연결되어 있는 무방향 그래프이다.
즉, 2개 이상의 정점을 갖고 있는 단절점이 없는 무방향 연결그래프이다.
Definition 2
Biconnected component는 maximal biconnected subgraph이다.
즉, 주어진 그래프의 biconnected subgraph 중, 포함되지 않은 어떤 정점 혹은 간선을 하나라도 추가하면 biconnected subgraph가 아니게 되는 subgraph를 의미한다.
일반적으로 그래프
Equivalence Relation¶
같은 biconnected component에 포함되는 간선들의 성질을 확인하기 위하여 다음과 같은 equivalence relation을 정의한다.
Definition 3
간선 집합
Proof
Definition 3의 relation
- (Reflexivity) 정의에 의해
가 성립한다. - (Symmetricity)
라면, 또한 자명하게 성립한다. - (Transitiviy) 서로 다른
에 대하여 , 라면, 가 성립함을 보이자.
즉, , 를 동시에 포함하는 단순 사이클 가 존재하고, , 를 동시에 포함하는 단순 사이클 가 존재할 때, 과 를 포함하는 단순 사이클 가 존재함을 보이면 된다.
만약 에 가 포함된다면, 에 , , 가 모두 존재하니 성립한다. 포함되지 않는 경우, 아래 그림처럼 에 속하는 정점들을 일렬로 나열하면, 수열 상의 어떤 정점 , 를 끝 정점으로 하며 를 포함하는, 과는 간선을 공유하지 않는 경로가 존재한다. 이제, 과 의 간선들만을 이용하여 , 의 간선을 모두 포함하는 단순 사이클 를 생성할 수 있다.
이제, Definition 2로 정의된 biconnected component와 Definition 3의 equivalence relation에서 정의된 equivalence class가 사실 같음을 보인다.
Property 1
Definition 2로 정의된 biconnected component들로 쪼개진 간선 집합들과, Definition 3의 equivalence relation에서 정의된 equivalence class로 쪼개진 간선 집합들은 같다.
모든 간선
Proof
(equivalence class
Equivalence class
(equivalence class
Menger's theorem에 의하면 biconnected component (2-vertex connected subgraph)의 인접하지 않은 임의의 두 정점
Biconnected component
Property 1에 의하여, biconnected component를 정의할 때, maximal biconnected subgraph로 정의하기보다는 위와 같이 정의된 equivalence class로 정의하는 것이 편리할 때가 많다.
Property¶
Property 2
Biconnected graph에는 단절점이 존재하지 않는다.
Biconnected graph에는 단절선이 존재하지 않는다.
단, 정점이 2개인 연결된 그래프는 예외이다.
Proof
Biconnected graph에 단절점이 없음은 정의에 의해 자명하다.
Biconnected graph에 단절선
Property 3
같은 biconnected component에 포함되는 두 정점
단, 정점이 2개인 연결된 그래프는 예외이다.
같은 biconnected component에 포함되는 두 간선
단, 정점이 2개인 연결된 그래프는 예외이다.
Proof
만약
두 간선
Property 4
원래 그래프에서 단절점이 아닌 정점
Proof
Property 5
원래 그래프에서 단절점
같은 컴포넌트에 속하는 정점과 연결된 간선들은 모두 같은 biconnected component에 포함되고, 다른 컴포넌트에 속하는 정점과 연결된 간선들은 모두 다른 biconnected component에 포함된다.
Proof
같은
다른