이중 결합 요소(Biconnected Components)

[2023-1R 고려대학교 최수경 교수님 Cose 213 자료구조 수강 중 내용 정리하는 글입니다.]

이중 결합 그래프(Biconnected Graph)

- 단절점(articulation point)가 없는 연결 그래프를 의미한다.

단절점(articulation point)

- 무방향 연결 그래프에서 어떠한 정점을 제거했을 때 그래프의 연결이 끊어지면 그 정점을 단절점이라고 한다.

 

Biconnected Components(이중 결합 요소)

- 단절점을 기준으로 연결된 그래프들로 분리해주면 하나하나가 Biconnected Components이다.

Biconnected Components 구하기 알고리즘

-Depth first spanning tree를 이용하여 구현함.

3에서 출발을 했다면 아래 순서대로 방문을 하게 되게 각각 dfn(depth first number)을 갖게 됨.

vertex	3	4	2	1	0	5	6	7	8	9
dfn	0	1	2	3	4	5	6	7	8	9

그래프를 다시 나타나게 되면 

다음과 같다. 

 

단절점을 구하기 위해서는

low(u)= min{ dfn(u), min{low(w)|w는 u의 child},min{dfn(w)|(u,w)는 nontree edge)}

다음을 이용하여 표를 채워야 한다.

그 결과는 다음과 같다.

그 중 dfn(u) =<low(w)이면 단절점이 된다.