강한 결합 요소

강한 결합 요소(Strongly Connected Component, SCC)는 방향 그래프에서 모든 정점이 서로 도달 가능한 최대 부분 그래프를 의미한다. 즉, 강한 결합 요소 내부에서는 임의의 두 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재해야 한다.

• 즉 쉽게 말해, 직접 가든 다른 곳을 거치든 서로 갈 수 있는 정점의 집합이라고 보면 된다.
  • 만약, A, B, C, D가 서로 갈 수 있는 길이 있는데, E는 A, B, C, D로 모두 갈 수 있는 반면, E에서 D로 가는 길만 없다면, E는 강한 결합 요소가 아니게 된다.
• 사이클이 있다면 그 사이클의 구성요소는 무조건 강한 결합 요소이다.

1 개요

방향 그래프(Directed Graph)에서 강한 결합 요소는 다음과 같은 성질을 만족하는 최대 부분 그래프이다.

• SCC 내부의 모든 정점 쌍 (u, v)에 대해 u → v, v → u인 경로가 존재한다.
• SCC를 정점으로 축소하면 DAG(방향 비순환 그래프, Directed Acyclic Graph)를 형성한다.

예를 들어, 다음 방향 그래프를 고려하자.

1 → 2 → 3
↑   ↓   ↓
4 ← 5 → 6 ↔ 7

이 그래프의 강한 결합 요소는 다음과 같다.

• {1, 2, 4, 5} - 서로 왕복 가능한 경로가 존재
• {6, 7} - 서로 직접 왕복 가능
• 나머지는 모두 강한 결합 요소가 아니다. 만약 7이 3으로 가는 경로가 존재했다면 {3, 6, 7}이은 강한 결합요소였을 것이다.

2 강한 결합 요소 찾기 알고리즘

강한 결합 요소를 찾는 대표적인 알고리즘으로는 코사라주 알고리즘(Kosaraju's Algorithm)과 타잔 알고리즘(Tarjan's Algorithm)이 있다. 각 구현 코드는 각 문서를 참고하자.

2.1 코사라주 알고리즘(Kosaraju's Algorithm)

코사라주 알고리즘은 DFS(깊이 우선 탐색)을 두 번 수행하여 SCC를 찾는다.

1. 방향 그래프에서 DFS를 수행하여 탐색 완료 순서(탐색 종료 시간이 큰 순서)를 기록한다.
2. 그래프의 방향을 반전(reverse)하여 모든 간선을 뒤집는다.
3. 반전된 그래프에서 DFS를 수행하되, 탐색 종료 순서의 역순으로 시작하여 SCC를 찾는다.

2.2 타잔 알고리즘(Tarjan's Algorithm)

타잔 알고리즘은 **한 번의 DFS 탐색으로 SCC를 찾는 알고리즘**으로, 각 정점의 DFS 방문 순서(low-link 값)를 활용한다.

1. DFS를 수행하며 각 노드의 방문 순서를 기록한다.
2. DFS 탐색 중 가장 작은 도달 가능한 노드(low-link 값)를 갱신한다.
3. DFS가 백트래킹할 때, 현재 노드의 low-link 값이 자신의 방문 순서와 같다면 SCC의 루트임을 확인하고 해당 SCC를 추출한다.

3 강한 결합 요소와 DAG

SCC를 하나의 노드로 축소하면 방향 비순환 그래프(DAG)가 형성된다. 이는 그래프에서 사이클을 제거하고 위상 정렬을 수행할 때 유용하다.

예를 들어, 아래 방향 그래프에서 SCC를 찾고 축소하면:

1 → 2 → 3
↑   ↓   ↓ ↖
4 ← 5 → 6 ↔ 7

강한 결합 요소:

• {1, 2, 4, 5}
• {3, 6, 7}

SCC를 하나의 노드로 압축하면 DAG가 된다.

{1, 2, 4, 5} → {3, 6, 7} 

4 강한 결합 요소의 활용

1. 그래프 압축 - 강한 결합 요소를 노드로 변환하여 DAG로 단순화 가능.
2. 위상 정렬 - SCC를 DAG로 변환 후 정렬하여 순서를 분석.
3. 2-SAT 문제 해결 - 논리식에서 강한 결합 요소를 이용해 만족 가능성을 판별.
4. 인터넷 네트워크 분석 - 통신망에서 강한 결합된 컴포넌트를 찾는 데 활용.

5 같이 보기

• 깊이 우선 탐색
• 위상 정렬
• DAG (방향 비순환 그래프)
• 코사라주 알고리즘
• 타잔 알고리즘