34. biconnected componet [13 1주차]

34. Biconnected Componet [13-1주차]

2024년 1월 14일 일요일

오후 5:02

<BCC (Biconnected Component)>

Biconnected Graph : 임의의 한 노드를 제거해도 나머지 모든 노드들이 연결되어 있는 그래프. 따라서 biconnected graph에는 cut vertex가 존재하지 않는다.

Biconnected graph는 몇 개의 사이클이 겹쳐져 있는 형태를 띤다. (두 개의 노드로 구성된 경우도 있다)

(그림 출처 : https://commons.wikimedia.org/wiki/File:Graph-Biconnected-Components.svg)

그래프 G의 Biconnected Component란, G내의 Biconnected인 부분 그래프를 의미한다. 그래프 내에 여러 BCC가 존재할 수 있으며, 각각의 BCC는 최대 크기여야 한다.

BCC는 cut vertex와 관련해 다음 특징을 가진다.

• cut vertex는 여러 BCC에 걸쳐 있다.
• cut vertex가 아닌 노드는 하나의 BCC에만 포함된다.

위 특징을 이용해 그래프의 BCC를 찾을 수 있다.

<BCC를 찾는 방법>

먼저 DFS를 통해 cut vertex를 찾는다.

다음으로, 임의의 노드 v에 대해 다음을 수행한다.

• v가 루트 노드인 경우

루트 노드가 자식을 하나만 가지면 그대로 둔다. 루트 노드가 자식을 두 개 이상 가지면, 즉 루트 노드가 cut vertex이면, 루트 노드를 자식 노드 수만큼 복사해 각각의 자식 노드와 연결한다. 분리된 DFS 트리 각각에 대해 다시 BCC를 찾는다.

• v가 루트 노드가 아닌 경우

v가 cut vertex가 아니면, 하나의 BCC에만 포함되는 것이므로, 그대로 둔다. 해당 노드가 cut vertex이면, v를 cut vertex로 만드는 자식 노드 개수만큼 노드 v를 복사한다. v를 cut vertex로 만드는 자식 노드를 루트로 하는 서브트리를 분리한 뒤, 그 서브트리의 최상단에 복사한 노드 v를 잇는다.

분리된 DFS트리 각각에 대해 다시 BCC를 찾는다.