[Lecture] SCC

SCC : Strongly Connected Component

 

Connecte Component는 undirected graph에서 존재한다

SCC는 directed graph에서 임의의 두 정점에 대해 양방향으로 가는 경로가 모두 있을 때, 존재한다

즉, 모든 노드가 양방향으로 reachable한 노드의 최대한 키운(Maximal Subset) 집합이다

//SCC는 사이클이 한 개 이상 겹쳐진 형태를 띤다. 하나의 정점도 SCC가 될 수 있다

SCC의 가장 간단한 형태가 사이클(한개)이다

 

[참고]

Directed graph : 문제를 해결한 알고리즘이 나왔을 때, 같은 방향으로 undirected graph에도 적용시켜 해결할 수 있다

Undirected graph : undirected graph에서 해결한다고 해서 directed graph가 해결되는건 아니므로, undirected graph일 때 문제를 해결하는 것이 더 어렵다.

 

Foward edge : 그래프의 간선 중, dfs트리 상에서 조상에서 자손으로 연결되지만 트리 간선이 아닌 간선

Back edge : 그래프의 간선 중, dfs트리 상에서 자손에서 조상으로 연결된 간선

Cross edge : 트리에서 조상과 자손관계가 아닌 정점들간에 연결된 간선

Pre Number : DFS 알고리즘이 노드에 처음 진입했을 때 부여되는 번호

Post Number : DFS 알고리즘이 리턴될 때 부여되는 번호 

 

SCC를 찾는법

 

1. DFS를 한다

2. 트리들과 Cross, Foward, Back edge를 본다

- 시작지점에 따라 , 전진할 수 있는 곳이 여러개 있을 때 어디로 전진할지에 따라 DFS트리가 다르게 나온다.

 

트리를 만드는 전제가 왼쪽 먼저 전진하는 것으로 가정하면

cross edge는 <= 이 방향만 허용이 된다

'=>' 방향을 허용하지 않는 이유

왼쪽 먼저 전진하기 때문에 => 이 cross edge가 나오기 전 해당 서브트리 내에서 이미 방문한 상태가 된다

3. 하나의 트리는 SCC 몇개를 포함하지만, 한 SCC가 여러 트리에 나눠져있지 않다(한 SCC는 하나의 트리에 들어있다)

- 한번 SCC에 들어오면 SCC에 포함된 정점을 다 방문하기 때문에 다른 트리로 나눠질 수 없다

 

밖에서 들어오는 edge가 다 차단되었다고 가정한다

해당 트리에서 SCC를 분리해야하기 때문에 DFS를 또 진행한다

 

빨간선 : SCC

DFS를 SCC 1번의 한 정점부터 시작하면, SCC 1번이 분리된다

DFS를 SCC 2번의 한 정점부터 시작하면, SCC 2번이 분리된다

DFS를 SCC 3번의 한 정점부터 시작하면, SCC 2번을 포함한 SCC 3번이 분리된다

DFS를 4번 정점부터 시작하면?? edge를 다 뒤집고 다시 dfs를 시작하면 SCC가 아닌 부분 하나는 뗄 수 있다

나머진 ??

따라서 이렇게 진행하게 되면 잘 안된다

 

The Algorithm

1. DFS를 돌리면서 Post Numbers를 붙인다

2. 모든 link를 반대방향으로 뒤집는다

3. Post Numbers가 가장 큰 곳부터 시작한다

= 트리 하나에 SCC가 한개씩 들어있게 된다

 

증명

Super graph를 생각해보자

Super graph는 하나의 SCC가 Super graph의 한 노드가 된다

한 SCC에서 다른 SCC로 가는 link가 하나라도 있으면 edge를 추가한다

Super graph = DAG

//DAG가 되는 이유

 

pre와 post는 한 SCC안에서도 섞여있다(어디로 전진하는지에 따라 다르다)

 

1. Min pre

무조건 Min pre는 있다 link를 뒤집고 Min pre에서 시작하면 하나는 뗄 수 있지만,

다음으로 제일 작은 pre가 무엇인지 알 수 없다

2. Max pre

맨 오른쪽 위부터 가면 가능하지만, 맨 왼쪽에서부터 시작하는 경우 어디로 전진할지 모르기 때문에 알 수 없다

 

3. Min post

Max pre와 유사하다

 

4. Max post

먼저 link를 뒤집는다

빨간색으로 갈 경우(빨간색에서 시작할 경우)

파란색으로 갈 경우(파란색에서 시작할 경우) 리턴하고 다시 빨간색부분으로 오기 때문에 빨간색 부분에 가장 큰 post number가 있다는 것을 알 수 있다

 

즉, 전체에서 post가 가장 큰건 indegree가 0인 곳에 있다

 

among Trees

전체에서 post가 제일 큰 부분부터 해도, 저절로 트리가 분리되기(나눠지기) 때문에 트리들을 먼저 분리하고 진행하지 않아도 된다