36. strongly connected component [13 2주차]

36. Strongly Connected Component [13-2주차]

2024년 1월 14일 일요일

오후 5:05

<SCC : Strongly Connected Component>

어떤 그래프의 SCC는 노드들의 부분집합으로, SCC내의 임의의 두 노드 a, b에 대해 a에서 b로 가는 경로도 있고 b에서 a로 가는 경로도 있도록 하는 최대 크기의 집합이다.

SCC는 사이클이 한 개 이상 겹쳐진 형태를 띤다.

하나의 정점도 SCC가 될 수 있다.

 

SCC가 존재하는 그래프는 DAG는 아니지만, SCC를 찾는 알고리즘은 Topological Sort와 유사하다.

 

 

<Supergraph>

SCC를 찾는 알고리즘을 구하기 위해, 그래프 G.SCC를 다음과 같이 정의한다.

그래프 G의 SCC가 C1, C2, …, Ck 라 한다.

G.SCC 는 노드 집합 V.SCC = {v1, v2, …, vk} 와 간선 집합 E.SCC로 구성된다.

x∈Ci, y∈Cj 에 대해 G에 방향 간선 (x, y)가 있으면 (vi, vj)∈E.SCC 가 성립한다.

(방향 그래프에서 간선(x, y)는 x->y방향의 간선을 의미한다)

 

즉, G.SCC는 그래프 G의 각 SCC를 하나의 노드로 축소시킨 그래프이다.

 

G.SCC는 항상 DAG가 된다.

 

• 증명 : C와 C'이 G의 서로 다른 SCC라 하자. u, v∈C이고 u', v'∈C' 이라 한다. 또한 G는 경로 u~>u'을 포함한다고 한다. 이때 G가 경로 v'~>v를 포함한다면,

경로u~>u'~>v' 과 v'~>v~>u 가 존재하므로 u와 v'이 다른 SCC에 있다는 것에 모순이 발생한다.

따라서 G에 경로 u~>u'이 존재하면, 경로 v~>v'은 존재할 수 없다. 즉 C~>C'으로의 경로가 존재하면, C'~>C로의 경로는 존재할 수 없고, G.SCC는 사이클이 존재하지 않아 DAG가 된다.

 

G.SCC를 Supergraph라 부른다. Supergraph의 노드(하나의 SCC)들은 Supernode라 부른다.

 

 

<post 번호의 특성>

SCC를 구하기 위해서는 DFS를 하여 각 노드의 post번호를 구해야 한다. 이때, 어떤 SCC C에 대하여, post(C)를 다음과 같이 정의한다.

post(C) = max_u∈C{u.post}

즉 post(C)는 C에 있는 노드의 post번호 최댓값이다.

이때 다음이 성립한다.

 

두 SCC C, C'에서, C의 어떤 노드 v와 C'의 어떤 노드 v'에 대해, 간선(v, v')이 존재하면, post(C)>post(C') 이다.

• 증명

• DFS가 C의 노드부터 방문하는 경우

C의 노드 중 가장 먼저 방문되는 노드를 x라 한다. 간선 (v, v')이 존재하므로, C와 C'의 노드들은 하나의 DFS트리에 포함되게 된다. 또한 x를 가장 먼저 방문했으므로, DFS 트리에서 C와 C'의 나머지 노드들은 x의 자손이 된다. 따라서 C와 C'의 노드들 중 x의 post번호가 가장 크고, post(C)>post(C')이 성립한다.

• DFS가 C'의 노드부터 방문하는 경우

요소 그래프가 DAG가 되므로, C'에서 C로의 경로는 존재하지 않는다. 따라서 C'의 노드들의 DFS가 완전히 끝난 다음 C의 노드들이 방문되므로,

post(C)>post(C')이 성립한다.

 

 

<SCC 알고리즘과 증명>

위에서 알아낸 성질들을 이용하면, 그래프 G의 SCC를 찾는 알고리즘은 다음과 같다.

 

SCC(graph G) {

• DFS(G)를 호출하여 노드의 post번호를 구함
• G의 모든 간선 방향을 거꾸로 뒤집은 그래프 G^T를 만듬
• DFS(G^T)를 호출하여 DFS트리를 구함. 이때, 각 라운드마다 post번호가 가장 큰 노드부터 DFS 시작.

}

 

알고리즘 3행에서, DFS트리 각각이 하나의 SCC가 된다.

 

알고리즘의 정확성 증명은 다음과 같다.

 

모든 간선의 방향을 뒤집으면 SCC는 변하지 않는다. 따라서 G와 G^T의 SCC는 같다.

또한 위에서 증명한 post번호의 특성에 의해 다음이 성립한다.

• 두 SCC C, C'에서, C의 어떤 노드 v와 C'의 어떤 노드 v'에 대해, 간선(v', v)이 존재하면, post(C)>post(C') 이다.

(post번호는 G^T가 아니라 G를 기준으로 매긴다)

 

마지막으로, 수학적 귀납법을 통해 알고리즘을 증명해 보자.

• Base : post값이 최대인 노드를 x라 하고, x가 포함된 SCC를 C라 하자. 위 증명에 의해, C로부터 다른 SCC로 향하는 간선은 G^T에 존재하지 않는다. 따라서 노드 x에서 DFS를 시작하면, x를 루트로 가지는 DFS트리의 노드 집합은 C가 된다.
• Step : DFS(G^T)로부터 만들어진 첫 k개의 트리가 각각 SCC라고 하자.

k+1번째로 만들어진 트리의 루트가 u일 때, u가 SCC C에 속한다고 가정한다. 알고리즘은 post값이 가장 큰 노드를 DFS의 시작점으로 선택하므로, 아직 방문되지 않은 임의의 SCC C'에 대해 u.post = post(C) > post(C')이 성립한다. 따라서 G^T에서 C를 나가는 방향의 간선은 모두 이미 방문한 SCC를 향하고, k+1번째 DFS 트리는 하나의 SCC가 된다.