Elementary Graph Algorithms2

Strongly Connected Components: 강한 연결 성분, SCC

주어진 방향 그래프 G = (V, E)에서, 

SCC는 그래프 G의 최대 정점 집합 C⊆⊆V로, 모든 정점 u, v ∈ C에 대해 u에서 v로의 경로와 v에서 u로의 경로가 모두 존재하는 집합이다.

 

말이 좀 어렵게 느껴질 수 있는데 그림으로 설명해보자면,

정점들을 묶어놓은 것이 부분 집합 C이고, 이 C내의 모든 정점들은 역방향이든 정방향이든 경로가 모두 존재한다는 것이다.

타임스탬프 14를 가진 정점과 13을 가진 정점을 보자. 14에서 13으로 향하는 경로도 존재하고, 13에서 14로 향하는 경로도 존재하는 것을 볼 수 있다.

경로가 존재하는 정점이 따로 없다면, 타임스탬프 10을 가진 정점처럼 혼자 묶인다.

 

알고리즘은 $G^T$그래프를 사용하는데, 이는 그래프 G의 모든 간선을 반전시킨 그래프이다.

$G^T = (V, E^T)$ 로, $E^T = {(u, v) : (v, u) ∈ E}$이다.

인접 리스트를 사용할 경우, $G^T$는 $O(V + E)$의 시간에 생성할 수 있으며, G와 $G^T$는 같은 SCC를 가진다. G에서 u와 v가 서로 도달할 수 있다면, $G^T$에서도 서로 도달할 수 있음을 보장하는 것이다.

SCC 과정

 

(a)는 DFS를 완료한 그래프이다. 따라서 각 정점에 타임스탬프가 찍혀있는 것을 볼 수 있다.

(b)는 $G^T$그래프에 대해 DFS를 완료한 모습이다. (a)그림과는 방향이 반전되어있다. 타임스탬프 값이 제일 큰 정점부터 DFS를 시작하므로, f(b) = 16의 값을 가진 정점 b부터 시작한다.

(a)와 (b)의 과정을 거치면 SCC를 찾을 수 있고, 부분집합 C를 한 정점으로 나타내 표현한 그래프이다. 이는 축약한 그래프라고 하며, $G^{SCC} = (V^{SCC}, E^{SCC})$로 표현한다.

---

정리와 증명

 

Lemma. $G^{SCC}$는 비순환 방향 그래프(DAG)이다. G에서 서로 다른 SCC의 C와 C'이 있다고 할 때, (u,v) ∈ C와 (u', v') ∈ C' 가 있으며, G의 u에서 v'으로 가는 경로가 있다고 가정한다. 이때, v'에서 u로 가는 경로는 존재할 수 없다는 것이다.

Proof. 만약 경로가 존재한다면, C와 C'은 하나의 컴포넌트로 합쳐져야하기 때문이다.

 

 

DFS

 

SSC(G)알고리즘의 작동방식에 대해 좀 더 알아보자면,

먼저, 그래프 G에서 DFS를 호출하여 모든 정점 u에 대해 종료시간 f[u]를 계산한다.

그 다음, 간선을 반전하여 G의 전치 그래프 $G^T$를 계산한다. $G^T$ 에서도 DFS를 호출하여 첫번째 DFS에서 계산된 f[u]의 내림차순으로 정점을 처리한다.

두 번째 DFS에서 생성된 깊이 우선 포레스트의 각 트리의 정점을 SCC로 출력한다. 이러면 SCC가 계산된다.

 

SCC의 시간 복잡도는 $\Theta(V+E)$이다.

첫 번째 DFS에서 계산된 종료 시간 f[u]의 내림차순으로 두 번째 DFS를 시행함으로써, 컴포넌트 그래프의 정점들을 위상 정렬 순서로 방문하게 된다. 위상 정렬이란, 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 그 순서를 결정하는 알고리즘이다.

일단 이 방법이 작동하는지 증명하기 위해, 먼저 두 가지 표기법 문제를 다뤄야한다. 여기서 SCC는 항상 첫 번째 DFS에서 계산된 d[u]와 f[u]를 참조한다는 것을 잊지 말아야 한다.

• 정점집합 U⊆V에 대한 d와 f의 표기는 다음과 같이 확장된다. 
• d(U) = min u∈U {d[u]} , U에 속한 정점들 중 가장 먼저 발견된 시간이다.
• f(U) = max u∈U {f[u]}, U에 속한 정점들 중 가장 나중에 종료된 시간이다.

 

Lemma. 위 그림처럼 $G = (V, E)$ 에서 서로 다른 SCC인 C와 C'이 있다고 가정하자. C에는 정점 u가 있고, C'에는 정점 v가 있고, 이를 이어주는 간선 (u, v)가 존재한다. 이 경우, $f(C) > f(C')$이 성립한다.

Proof. 어느 SCC가 먼저 발견되었는지에 따라 두 가지 경우로 나눌 수 있다.

• $d(C)<d(C')$인 경우, C에서 처음 발견된 정점을 x라고 한다면, d[x]의 시점에서는 C와 C'의 모든 정점이 WHITE인 상태이다. 따라서 x로부터 C와 C'의 모든 정점까지 연결된 백색 경로가 존재한다. White-path 정리에 따라, C와 C'의 모든 정점은 깊이 우선 트리에서 x의 자손이다. 따라서 Parenthesis 정리에 따라, $f[x] = f(C)>f(C')$이 성립한다.
• $d(C)>d(C')$인 경우, C'에서 처음 발견된 정점을 y라고 한다면, d[y]의 시점에서는 C'의 모든 정점이 WHITE 상태이며, y로부터 C'의 모든 정점까지 연결된 백색 경로가 존재한다. 따라서 C'의 모든 정점은 y의 자손이 된다. 이로 인해, $f[y] = f(C')$이 된다. 하지만 여전히 d[y]의 시점에서는 C의 모든 정점이 WHITE 상태이다. 그러나 C'에서 C로 갈 수 있는 경로는 존재하지 않고, y로부터 C의 정점에 도달할 방법은 없다. 따라서 C의 모든 정점 w에 대해 $f[w]>f[y]$가 성립하며, $f(C)>f(C')$도 성립하게 된다.

Collary. 서로 다른 SCC인 C와 C'이 있는 그래프 $G=(V, E)$에서, 만약 $E^T$에 간선 (u,v)가 존재하고, u ∈ C, v ∈C'이라면, $f(C)<f(C')$가 성립한다.

내가 그린 기린 그림

 

Proof. (u, v) ∈$E^T$라면, (v, c)∈E 라는 의미이다. SCC는 G와 $G^T$에서 똑같으므로, $f(C)<f(C')$이다.

 

Corollary. 서로 다른 SCC인 C와 C'이 있는 그래프 $G=(V,E)$에서, $f(C)<f(C')$라고 가정하면, C에서 C'으로 가는 간선은 존재할 수 없다.

 

Proof. 이 명제는 이전 정리의 대우(contrapositive)라고 한다. 이전 정리에서 C에서 C'으로 가는 간선이 존재한다면, $f(C)>f(C')$이어야 한다고 했다. 따라서 C에서 C'으로 가는 간선은 존재할 수 없는 것이다.

---

SCC 알고리즘

 

여태껏 설명했던 SCC 내용들을 정리해보자면,

• 전치 그래프 $G^T$에서 두 번째 DFS를 수행할 때, 최대 종료 시간 f(C)를 가진 SCC $C$부터 시작한다.
• 두 번째 DFS는 C의 정점 x부터 시작하여 C의 모든 정점을 방문한다.
• collary에 따르면, 서로 다른 SCC $C$와 $C'$에 대해 $f(C)>f(C')$이므로, $G^T$에서는 C에서 C'로 가는 간선이 존재하지 않는다. 따라서, 이 DFS는 C의 정점들만 방문하게 된다.
• 즉, x를 루트로 하는 깊이 우선 트리는 정확히 C의 정점들로만 이루어진다.
• 두 번째 DFS에서 x다음으로 선택되는 루트는 C를 제외한 모든 SCC 중에서 최대 $f(C')$ 값을 가지는 SCC $C'$에 있다.
• 이 DFS는 C'의 모든 정점들을 방문하지만, C'에서 나가는 간선은 이미 방문된 C로만 연결된다. 따라서, 이 경우에도 트리 간선은 C'의 정점들로만 연결된다.
• 이 과정을 반복할 때마다 새로운 루트로 선정된 SCC의 정점들만 방문하게 되며, 이전에 방문된 SCC로의 간선은 트리 간선이 되지 않는다. 결과적으로, $G^T$의 SCC를 위상 정렬의 역순으로 방문하게 된다.

SCC 그래프 예시

---

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **