SSC

SSC : Strongly Connected Component

• SCC : Maximul Subset of Nodes s.t., all Nodes are Reachable from Each Other
• How do you find them?

Strongly Connected라는건, 양쪽 방향으로 가는 길이 있다는 것이다.

어디서 잡든 다른 노드로 가는 길이 있고, 다시 돌아오는 길이 있다. 

SSC의 간단한 예시는 cycle

 

한 노드가 여려 곳에 속하지는 않음

만약, 두개의 SCC가 한 노드를 공유한다고 생각하자. -> 그러면 결국 이 두개는 한개의 SCC이다. 

따라서 두 컴포넌트가 그냥 합쳐지기 때문에 한 노드를 공유하는 순간 하나의 SCC가 된다. 

 

Let's DFS

• DFS를 해서 Tree 가 여러개 나왔다고 가정하자
• 하나의 SCC가 두개의 tree에 나눠져있을 수 있는지 생각해보자
• 불가능하다
• DFS 하다가 처음으로 한 SCC에 도착하면, 무조건 남은 노드에 가게 된다 
• 하지만 Cross Edge가 있을 수는 있다. 
• 왼쪽이 먼저 간거라고 가정하면, 오른쪽에서 왼쪽으로 가는 edge는 존재할 수 있지만, 왼쪽 tree에서 오른쪽 tree로 갈 수는 없음
• 즉, 한쪽 방향으로 갈 수 있는 edge만 있는 것이다 (SCC는 아니라는 것)
• 하나의 Tree가 여러개의 SCC를 포함할 수는 있다. 

-> 운이 좋으면 하나의 Tree에 한개의 SCC가 존재할 수 있다

하지만, 이게 모든 그래프에서 가능한 것인지, 방법이 있는지에 대해 아직은 알 수 없다 

 

The Algorithm 

• Run DFS, set Post() Numbers
• Reverse All Links
• Run DFS : Starting Every Round at the Maximum Post() Number Possible
• This Results in Each Tree Being One SCC
• WHY??

Supergraph

입력 그래프가 있다면

• One SCC becomes one SuperNode : SCC하나를 super node로 보자 (그냥 하나의 노드로 보자는 뜻)
• There is an Edge from Super Node A to Super Node B if a Node in A has an edge to a Node in B : 한쪽에서 한쪽으로 가는 노드가 있다는 것
• Subergraph is a DAG : 사이클이 존재한다면 supernode의 정의가 어긋나기 때문이다. 
• DAG : 방향이 있는 사이클이 없는 그래프
• Why?

supernode를 기준으로 생각해서 toplogical sort에 reverse order를 하면 tree가 뜯어질 것 같다는 생각이 든다. 

 

Directed Graph DFS Tree

트리가 존재한다고 가정하자

Back edge가 있을 수 있다 -> 사이클을 만듦

forward edge는 큰 의미가 없다. 

cross edge는 뒤에서 앞으로(오른쪽에서 왼쪽으로) 올 수 있다. 

 

하나의 트리에 여러개의 SCC가 있는 경우를 생각해보자

이 한 구역이 SCC라고 생각하면, x 친 edge는 존재할 수가 없다. 

 

=> Pre() and Post() 번호를 붙였을 때 어떻게 되는지 생각해보자

 

Pre()를 설정하는 경우

왼쪽의 경우, 맞게 사이클이 분리되지만, 지금 오른쪽 경우로 보면 섞여있다는 것을 알 수 있다. 

 

Post()를 설정하는 경우 

post도 똑같이 섞여있다는 것을 확인할 수 있다 

즉, Pre()번호는 일단 사용할 수 없다

Minimum Pre() within SCC is Mixed 

제일 작은 것만 생각한다고 해도, 왼쪽 오른쪽에 작은 번호가 달라지므로 mixed 된다고 생각할 수 있다

 

Maximum Post() within SCC not Mixed

 

어디서 시작하든 super graph에서 toplogical sort의 order가 항상 같다

Post()로 한 다음, 한 그룹 안에서 maximum을 보면 섞여있지 않다.

SCC의 max post를 abcd라고 하면 a>d>c>b가 성립한다.

모든 edge가 왼쪽에서 오른쪽으로만 가고, 한 트리 안에서만 back edge가 존재한다. 

즉, root아래에 더 큰 번호가 존재할 수 없다 

 

그룹을 구별할 수 있는 경우는 post번호가 가장 큰 것이다.

만약, c 쪽에 post 번호가 가장 작으면, bc는 같은 트리가 된다. 

=> 이를 해결하기 위해 모든 edge를 뒤집는다. 

그러면 이러한 그래프처럼 나오게 된다.

우리는 한 그룹을 알고 있지 않다. 

따라서 edge를 다 뒤집어도 SCC는 바뀌지 않지만, 반대로 보이기 때문에 SCC의 그룹을 찾을 수 있다. 

 

Shortest and Longest Paths on DAG

shortest : Dijkstra

Longest : NP-Complete

 

Single-source shortest paths in DAGs

 

노드를 하나씩 옮겨가면서 생각

DAG에서는 -가 있어도 된다

 

즉 O(m+n)이 된다

 

THE shortest path in a DAG

들어오는게 없는 노드에서 나가는게 없는 노드까지 가는 길

Set 0 to indegree = 0 Nodes, Select the Minimum for others

ex) maximum flow : 교통량 등등

 

나가는게 없는 노드는 5

 

THE Longest path in a DAG

Set 0 to indegree = 0 Nodes, Select the Maximum for Others