[CS] 단절점

단절점

무향 연결 그래프에서 하나의 정점과 연결된 간선들을 모두 제거했을 때 두 개의 연결 그래프로 나눠진다면 해당 정점은 단절점이다.

출처 : https://www.crocus.co.kr/1164

위의 그림에서 주황색 정점들이 단절점이다.

2번 정점을 기준으로 { 1 } 과 { 3, 4, 5, 6, 7, 8 } 으로 나뉘어진다. 

4번 정점을 기준으로 { 1, 2, 3 } 과 { 5, 6, 7, 8 } 으로 나뉘어진다. 

6번 정점을 기준으로 { 1, 2, 3, 4, 5, 8 } 과 { 7 } 으로 나뉘어진다. 

 

단절점 찾기

무향 연결 그래프에서 어떤 정점 A에 연결된 정점들에 대해서 우회경로(정점 A를 거치지 않는 경로)가 없는 경우가 존재한다면 A는 단절점이다.

 

어떤 정점 A와 해당 정점에 연결된 정점 B에 대해서,

A가 시작 정점이 아닌 경우 : \(order_A \leq low_B\) 이면 A는 단절점이다.

A가 시작 정점인 경우 : \(2 \leq child_A\) 이면 A는 단절점이다.

\(order_V\) : 정점 V의 방문 순서
\(low_V\) : 정점 V를 거치지 않고 방문 가능한 정점들의 order 중 가장 작은 값
\(child_V\) : 정점 V의 자식 트리 수