단절점(articulation point)

단절점(articulation point)

1. 그래프, 연결요소(connected component), 단절점

- 1개 이상의 노드와 각 노드 사이를 잇는 1개 이상의 간선으로 구성돼있는 노드 사이 연결 관계를 그래프라 하며, 어떤 그래프의 부분그래프로서 이를 구성하는 모든 노드가 서로 연결(=노드와 노드 사이에 1개 이상의 간선으로 이루어진 경로가 존재)되어 있는 부분그래프를 연결요소라 한다. 하나의 그래프는 서로 이어지지 않은 수개의 연결요소로 이루어진다.

- 그래프의 어떤 노드를 그 노드와 연결된 간선들과 함께 제거하는 경우 그 그래프의 연결요소 개수가 증가하게 될 때, 그 노드를 단절점이라 한다. 그래프에 있는 간선이 상대적으로 적은 경우에 그래프가 많은 단절점을 갖게 되며, 그래프에 간선이 상대적으로 많은 경우에는 그래프가 적은 단절점을 갖게 된다. (그래프에 간선이 많아지면 노드 하나와 그와 연결된 간선을 제거하더라도 연결요소가 증가하지 않게 된다.)

2. 깊이 우선 신장 트리(depth-first spanning tree)와 백 간선(back edge)

- 그래프의 임의의 한 노드에서 시작해 DFS 순회를 할 때, 그 순회 과정에서 지나친 노드와 간선으로 이루어진 트리를 깊이 우선 신장 트리라 하고, 이때 깊이 우선 신장 트리에 포함되지 않은 간선을 백 간선이라 한다.

3. 그래프의 모든 노드가 각각 단절점인지 아닌지를 판별하는 알고리즘

- 그래프의 어느 한 노드가 단절점인지 아닌지는 그 노드와 연결돼있던 다른 노드들에서부터 각각 DFS 탐색을 수행하여 확인할 수 있다. 이와 같은 방법으로 단절점 여부를 검사할 경우 그래프의 모든 노드가 단절점인지 아닌지를 판별하는 데 걸리는 시간복잡도는 $O(V(V+E))$이다.

- 다음 알고리즘을 통해 $O(V+E)$의 시간복잡도로 그래프의 모든 노드가 각각 단절점인지 아닌지를 판별할 수 있다.

1) 임의의 한 노드에서 시작해 깊이 우선 신장 트리를 만든다.

- 이때, DFS 순회를 하면서 각 노드에 그 노드에 방문하게 된 순서를 기록한다. 노드번호 $u$에 대해 그 노드의 방문 순서를 dfn($u$)라 하기로 하자.

- 또, 각 노드에 다음과 같이 정의되는 함수값 low($u$)를 기록한다.

low($u$) = min[ dfn($u$), min( 정점 $u$와 백간선으로 연결된 조상노드들이 갖는 dfn ), min( 정점 $u$의 깊이 우선 신장 트리에서의 자식노드들이 갖는 low ) ]

- 즉 low($u$)는 (1)정점 $u$가 바로 백간선으로 연결된 조상노드를 갖는다면 그 조상노드들 중 dfn 최솟값이고 (2)백간선으로 연결된 조상노드를 갖지 않아도 그러한 조상노드를 갖는 후손노드를 갖는다면 그 후손노드들 중 dfn 최솟값이다.

2) 이처럼 모든 노드의 low($u$) 값을 구하면서 깊이 우선 신장 트리를 만들었다면, 다음과 같은 방법을 통해 각 노드가 단절점인지 아닌지를 판단할 수 있다.

(1) 깊이 우선 신장 트리의 루트노드의 경우, 그 노드가 백간선을 제외하고 둘 이상의 자식노드를 갖는다면 이 노드는 단절점이다.

(2) 루트노드가 아닌 경우, 백간선을 포함해 이 노드와 바로 연결된 자식 중에 그 자식노드의 low($u$) 값이 이 노드의 dfn보다 크거나 같은 자식노드가 있다면, 이 노드는 단절점이다.

from http://lkwks.tistory.com/23 by ccl(A) rewrite - 2021-09-25 01:27:00