강한 연결 요소(Strongly Connected Component)

1. 개념

위 그래프는 큰 그래프를 3개의 SCC(Strongly Connected Component)로 분할한 것을 보여준다.

SCC는 일종의 서브그래프로, 하나의 SCC안에 있는 어떤 두 정점 u,v를 고르면

SCC 내부에서 u에서 v로 가는 직/간접적인 경로가 존재하는 것을 뜻한다.

또한, SCC는 maximal한 성질을 가져서 가능한 SCC가 커야한다.

위 그래프에서 오른쪽의 SCC인 {c,d,h}의 하위 집합 중 {c, d} 또한 SCC의 첫번째 성질은 만족하지만,

정점 h를 추가해도 여전히 성질이 만족하므로 h는 반드시 추가되어야한다는 뜻이다.

즉, 유향 그래프에서는 항상 파티션을 분할해 SCC를 만들 수 있고, O(n)안에 모든 SCC를 분리하는 것이 가능하다.

*출처 : http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220802519976

[강한 연결 요소 예제 : http://gyutts.tistory.com/79]