[알고리즘] 14. Cut Vertex

[알고리즘] 14. Cut Vertex

1. Cut Vertex 알고리즘

Cut Vertex (절단점)는 제거할 경우 그래프가 끊어지게 되는 노드를 의미한다. 각 노드마다 노드를 지우고 그래프가 끊어졌는지를 확인하면 $O(mn)$의 시간이 걸리게 된다. 하지만 DFS를 돌리고 DFS Tree를 생성하면 $O(m+n)$만에 절단점을 찾을 수 있다.

Root Cut Vertex

DFS Tree의 루트가 2개 이상의 자식을 가지면 Cut Vertex임을 보이자. 루트에 연결된 서브트리들 중 두개를 각각 S1, S2라 하자. S1에 포함된 노드 중 하나를 x, S2에 포함된 노드 중 하나를 y라 하자. x에서 y로 가기 위해서 x는 S1을 벗어나야 한다.

Tree Edge만 사용할 경우: 이 경우 Root를 반드시 거칠 수 밖에 없다.

Tree Edge와 Back Edge도 사용할 경우: S1을 벗어나기 위해서는 S1보다 높은 조상으로 가야 하는데 가장 위의 조상이 루트이므로 반드시 Root를 거치게 된다.

따라서 루트는 Cut Vertex이다.

Non-Root Cut Vertex

DFS Tree에서 루트가 아닌 어떤 노드 $t$가 Cut Vertex인지 확인하는 알고리즘을 알아보자. 모든 노드마다 $l(t)$를 계산하는데, $l(t)$는 아래 세가지 값들 중 minimum 값을 의미한다.

$Pre(t)$: DFS 방문 순서 번호 (Pre 번호로 조상-자손 관계만 따질 용도, 위로 갈수록 번호가 작다.)

t와 연결된 Back Edge의 반대쪽 노드들의 $Pre()$ 값들 중 최솟값 (가장 높은 위치)

t의 자손들의 $Pre()$ 값들 중 최솟값

쉽게 말해서, $l(t)$는 $t$의 서브트리 내에서 Back Edge를 한번 타서 올라갈 수 있는 가장 높은 위치의 노드 번호를 의미한다. 노드 $t$의 자식 $u$가 존재하고, $l(u) \ge Pre(t)$ 이면 $u$가 $t$의 조상으로 가는 Back Edge가 없는 경우이므로, $t$는 Cut Vertex이다.

Proof of $l(u) \ge Pre(t)$

$t$의 자식 노드 $u$의 서브트리를 S1, $t$보다 조상인 어떤 노드를 $y$라 하자. $u\rightarrow y$로 가려면 S1을 벗어나야 한다.

Tree Edge만 사용할 경우: 이 경우 $u-t$ 엣지를 반드시 거치게 된다.

Back Edge도 사용할 경우: $l(u) \ge Pre(t)$ 이므로 S1을 벗어나봤자 $t$보다 아래에 있다. ($u$에 $t$의 조상으로 가는 Back Edge가 없다는 뜻)

2. Cut Vertex 알고리즘의 시간 복잡도

먼저 처음에 DFS Tree 생성하는데 $O(m+n)$이 걸린다.

$Pre(t)$: 처음에 DFS Tree 생성하면서 계산되어 있음

t와 연결된 Back Edge의 반대쪽 노드들의 $Pre()$ 값들: 금방 계산 가능 (?)

t의 자손들의 $Pre()$ 값들 중 최솟값: DFS를 Postorder 순으로 계산해서 한번 더 돌리면 된다.

이 과정에서 DFS를 한번 더 돌리기만 하므로 전체 시간 복잡도는 $O(m+n)$이다.

3. Cut Edge

Cut Edge는 제거했을때 그래프가 끊어지는 엣지를 말한다. 그래프 $G(m, n)$에서 모든 edge 마다 노드를 하나 추가한 그래프를 $G'(m+n, 2n)$ 이라 하자. 이 그래프에서 Cut Vertex 를 찾으면 그 노드를 추가한 edge가 Cut Edge이다. $G'$에서 Cut vertex를 돌리는 것은 $O(m+n)$으로 동일하다.

4. BCC (Biconnected Component)

무향 그래프에서 정의되는 개념으로, Cut Vertex에 의해 끊어진 그래프들의 각 부분을 의미한다. BCC 내의 임의의 두 노드는 완전히 다른 (edge도 node도 겹치지 않는) 2개의 경로만 존재한다. \par

BCC를 찾기 위해서는 Cut Vertex 알고리즘을 사용하면 된다. Cut Vertex 알고리즘에서 아무리 올라가도 노드 $t$까지밖에 못 가는 Subtree가 있으면 $t$가 Cut vertex이였다. 이때 이 Subtree가 BCC이다.

from http://pongkijoa.tistory.com/21 by ccl(A) rewrite - 2021-12-27 12:00:35