강한연결요소(SCC ; Strongly Connected Component)

강한연결요소 SCC (Strongly Connected Component) 란?

 

[SCC가 될 수 있는 조건]

동일 집합 X 내에 있는 두 정점 A, B 사이 경로

① A → B

② B → A

경로 ①② 가 모두 존재할 때 SCC라 함.

 

[다른 SCC인 조건]

이는 서로 다른 SCC 집합 X, Y에서

집합 X 내 정점 중 A라는 정점을 선택,

집합 Y 내 정점 중 B라는 정점을 선택함.

 

뽑은 두 정점 A(X), B(Y)는

① A → B

② B → A

경로 ①② 가 함께 존재 할 수는 없다.

즉, 다른 SCC 임을 뜻한다.

 

경로 ①만 존재하거나,

경로 ②만 존재하거나,

경로 ①② 둘 다 존재하지 않거나,

위 3가지 경우 중 하나라면 같은 SCC 이 아니다.

 

그렇다면 같은 SCC 내에 있는 임의의 정점 A 을 택했을 때,

같은 SCC 내 A를 제외한 정점 B 를 선택할 때

서로 갈 수 있는 경로가 항상 존재함을 의미한다. 

 

	① A → B	② B → A
SCC	O	O
SCC X	O	X
	X	O
	X	X

 

그림으로 예를 들어보면,

 

[예 1]

 

정점 1,2,3 이 존재하고

경로는 1 → 2 , 2 → 1 이 존재한다. [ SCC 가 될 수 있는 조건 ] 에 속하므로 정점 1, 2 는 같은 집합 SCC 임.

그러나 정점 3은 [ 다른 SCC인 조건 ] 에 속하므로

총 2개의 SCC로 구성되어 있다.

 

 

[예 2]

[예 1]과 같이 정점 1,2,3이 존재한다.

하지만 정점 1,2 사이에 경로는 1 → 2 만 존재한다. 이는 [다른 SCC 인 조건] 이므로 같은 SCC 가 아니다.

다른 정점 3 도 정점 1,2와 [다른 SCC인 조건] 이 성립하므로 이 경우 총 3개의 SCC로 구성되어 있다.

 

[예 3]

위 예시의 경우에는 약간 복잡하게 되어 있다.

정점 6과 나머지 정점 1,2,3,4,5 와 [다른 SCC인 조건] 이 성립한다.

 

이제 정점 1부터 SCC를 확인해보자.

경로 1→2 , 2→3 , 3→1 인 경로가 존재한다. 이는 같은 SCC 이다.

경로 1→4 , 4→5 , 5→3 인 경로가 존재한다. 이는 같은 SCC 이다.

SCC는 항상 최대로 묶이며, 정점 1,2,3,4,5는 같은 SCC가 된다.

즉, 정점 1,2,3,4,5 는 5개 정점 중 어떤 두 정점을 택해도 서로 도달할 수 있는 경로가 존재한다.

 

그러므로 위의 경우에는 총 2개의 SCC 로 구성되어 있다.

 

다음에 정리.

 

SCC를 구하는 알고리즘으로 2가지가 있다.

1) 코사라주 (Korasaju's Algorithm) == http://wondy1128.tistory.com/130

2) 타잔 (Tarjan's Algorithm)