[알고리즘] Graph (4) - Biconnected Components(BCC)

[4. Biconnected components, 이중연결 구성요소]

1. Articulation point, 분절점

   → 어느 무방향그래프의 한 vertex를 제거했을 때, 그 vertex를 제거함으로써 적어도 두 개의 connected components가 생긴다면, 그 제거된 vertex는 분절점이다.

Ex)

   (1) vertex C 제거

   => 두 개의 connected components

   => 따라서 C는 분절점

   (2) vertex G 제거

   => 두 개의 connected components

   => 따라서 G는 분절점

 

2. Biconnected graph

   → 분절점이 없는 무방향그래프

 

3. Biconnected component

   → Biconnected graph의 최대 서브 그래프 (각각의 서브그래프에서 어느 노드를 제거해도 두 개의 연결 그래프가 생기지 않음)

4. BCC찾는법

   → DFS 사용하되, Depth first number 사용 (pre, post number 아님)

   → previsit number와 dfn은 방문순서가 같으나 그 값은 다를 수 있다.

Ex)

   → 주어진 그래프의 spanning tree를 만들었을 때, vertex v의 후손노드 중 v의 조상노드로 가는 back edge가 있다면 그 back edge와 연결된 vertex는 분절점이다.

Ex) 위 그래프의 분절점은 B, D, F, H

   → spanning tree의 뿌리노드가 최소 두 개의 자식 노드를 가지고 있다면, 그 뿌리노드는 분절점이다.

   → low(u) : vertex u의 후손 노드 중 back edge를 가지는 후손 노드를 통해 도달할 수 있는 가장 낮은 dfn

   → low(u) = min{dfn(u),

                            min{low(w) | w is a child of u},

                            min{dfn(v) | (u,v) is a back edge}}

   → 만약 vertex u가 spanning tree의 자식 노드를 두 개 이상 가지는 뿌리노드이거나, low(w)>=dfn(u)인 vertex w를 자식 노드로 가진다면 u는 분절점이다.