1. 그래프 관련 용어들

  • 그래프: 1개 이상의 노드와 각 노드 사이를 잇는 1개 이상의 간선으로 구성돼있는 노드 사이 연결 관계

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

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

    • 네트워크 설계 및 분석 문제에서 단절점의 개념은 중요한데, 단절점이 제거될 경우 그 네트워크에서는 각 노드 사이 통신이 중단되는 경우가 많아지기 때문이다. 즉, 네트워크에 어떤 노드가 단절점인지를 파악하는 문제는 네트워크의 안정성을 파악하는 데 있어 매우 중요한 문제라 할 수 있다.

  • 깊이 우선 신장 트리: 그래프의 임의의 한 노드에서 시작해 DFS 순회를 할 때, 그 순회 과정에서 지나친 노드와 간선으로 이루어진 트리.

  • 백 간선(back edge): DFS 순회 후 깊이 우선 신장 트리를 만들었을 때, 그 트리에 포함되지 않은 간선.

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

- 그래프의 어느 한 노드가 단절점인지 아닌지는 그 노드와 연결돼있던 다른 노드들에서부터 각각 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보다 크거나 같은 자식노드가 있다면, 이 노드는 단절점이다.