알고리즘 - 단절점 (Articulation Points / Cut Vertices)

알고리즘 - 단절점 (Articulation Points / Cut Vertices)

1. 단절점이란?

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

예를 들어 5에 있는 간선들을 모두 제거해도 그래프가 두 개로 나누어지지 않기 때문에 5는 단절점이 아니다. 그러나 4에 있는 간선들을 모두 제거할 경우 두 개의 연결 그래프로 나뉘어지기 때문에 단절점이다.

 

2. 단절점 찾기

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

 

orderV : 정점 V의 방문순서

lowV : 정점 V의 low (V 이후에 방문하는 정점들 중 V를 거치지 않고 방문 가능한 정점들의 order 중 가장 작은 값이며, 초기 값은 자신의 order이다.)

child V : 정점 V의 자식 트리 수

 

정점 A와 A에 연결된 정점 B에 대해서

- A가 시작정점이 아닌 경우

• orderA <= lowB => A는 단절점
• orderA > lowB => A는 단절점이 아님

- A가 시작정점인 경우

• 2 <= childA => A는 단절점
• 2 > childA => A는 단절점이 아님