|
|
| (같은 사용자의 중간 판 2개는 보이지 않습니다) |
| 1번째 줄: |
1번째 줄: |
| [[파일:강한 결합 요소.png|섬네일|강한 결합 요소 예시]]
| | #넘겨주기 [[강한 연결 요소]] |
| 강한 결합 요소(Strongly Connected Component, SCC)는 방향 그래프에서 모든 정점이 서로 도달 가능한 최대 부분 그래프를 의미한다. 즉, 강한 결합 요소 내부에서는 임의의 두 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재해야 한다.
| |
| | |
| * 즉 쉽게 말해, 직접 가든 다른 곳을 거치든 서로 갈 수 있는 정점의 집합이라고 보면 된다.
| |
| ** 만약, A, B, C, D가 서로 갈 수 있는 길이 있는데, E는 A, B, C, D로 모두 갈 수 있는 반면, E에서 D로 가는 길만 없다면, E는 강한 결합 요소가 아니게 된다.
| |
| * 사이클이 있다면 그 사이클의 구성요소는 무조건 강한 결합 요소이다.
| |
| | |
| ==개요==
| |
| 방향 그래프(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}이은 강한 결합요소였을 것이다.
| |
| ==강한 결합 요소 찾기 알고리즘==
| |
| 강한 결합 요소를 찾는 대표적인 알고리즘으로는 '''코사라주 알고리즘(Kosaraju's Algorithm)'''과 '''타잔 알고리즘(Tarjan's Algorithm)'''이 있다. 각 구현 코드는 각 문서를 참고하자.
| |
| ===[[코사라주 알고리즘|코사라주 알고리즘(Kosaraju's Algorithm)]]===
| |
| 코사라주 알고리즘은 '''DFS(깊이 우선 탐색)'''을 두 번 수행하여 SCC를 찾는다.
| |
| #방향 그래프에서 '''DFS'''를 수행하여 탐색 완료 순서(탐색 종료 시간이 큰 순서)를 기록한다. | |
| #그래프의 방향을 '''반전(reverse)'''하여 모든 간선을 뒤집는다.
| |
| #반전된 그래프에서 '''DFS'''를 수행하되, '''탐색 종료 순서의 역순'''으로 시작하여 SCC를 찾는다.
| |
| ===[[타잔 알고리즘|타잔 알고리즘(Tarjan's Algorithm)]]===
| |
| 타잔 알고리즘은 **한 번의 DFS 탐색으로 SCC를 찾는 알고리즘**으로, 각 정점의 '''DFS 방문 순서(low-link 값)'''를 활용한다.
| |
| #'''DFS'''를 수행하며 각 노드의 방문 순서를 기록한다.
| |
| #'''DFS''' 탐색 중 가장 작은 도달 가능한 노드(low-link 값)를 갱신한다.
| |
| #'''DFS'''가 백트래킹할 때, 현재 노드의 low-link 값이 자신의 방문 순서와 같다면 SCC의 루트임을 확인하고 해당 SCC를 추출한다.
| |
| ==강한 결합 요소와 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}
| |
| | |
| ==강한 결합 요소의 활용==
| |
| #'''그래프 압축''' - 강한 결합 요소를 노드로 변환하여 DAG로 단순화 가능.
| |
| #'''위상 정렬''' - SCC를 DAG로 변환 후 정렬하여 순서를 분석.
| |
| #'''2-SAT 문제 해결''' - 논리식에서 강한 결합 요소를 이용해 만족 가능성을 판별.
| |
| #'''인터넷 네트워크 분석''' - 통신망에서 강한 결합된 컴포넌트를 찾는 데 활용.
| |
| ==같이 보기==
| |
| *[[깊이 우선 탐색]]
| |
| *[[위상 정렬]]
| |
| *[[방향 비순환 그래프|DAG (방향 비순환 그래프)]]
| |
| *[[코사라주 알고리즘]]
| |
| *[[타잔 알고리즘]]
| |
