강한 연결 요소
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
강한 연결 요소는 유향 그래프에서 모든 정점 쌍 사이에 양방향 경로가 존재하는 경우를 의미하며, 이러한 관계는 동치 관계를 형성한다. 강하게 연결된 요소들은 그래프의 정점 집합을 분할하며, 각 강한 연결 요소들을 단일 정점으로 축약하면 유향 비순환 그래프가 된다. 강한 연결 요소를 찾는 알고리즘으로는 깊이 우선 탐색 기반의 코사라주 알고리즘, 타잔의 알고리즘, 경로기반 알고리즘 등이 있으며, 도달 가능성 쿼리를 이용한 알고리즘도 존재한다. 강한 연결 요소는 2-충족 가능성 문제 해결, 이분 그래프의 둘메이지-멘델슨 분해 계산 등에 활용된다. 또한, 유향 그래프가 강하게 연결되어 있다는 것은 그래프가 이어 분해를 가질 때와 같으며, 무향 그래프는 2-변 연결 그래프일 때 강하게 연결되도록 방향을 설정할 수 있다.
더 읽어볼만한 페이지
- 유향 그래프 - 위상정렬
위상 정렬은 방향 그래프의 정점들을 간선 방향에 따라 정렬하는 알고리즘으로, 작업 스케줄링, 의존성 분석 등에 활용되며 방향 비순환 그래프에서만 수행 가능하고, Kahn 알고리즘, 깊이 우선 탐색 등의 구현 방법이 존재하며 스케줄링 문제 해결에 중요한 선행 그래프 분석에 사용됩니다. - 유향 그래프 - 유향 비순환 그래프
유향 비순환 그래프(DAG)는 순환이 없는 유향 그래프로, 정점과 방향을 갖는 변으로 구성되어 도달 가능성 관계로 부분 순서를 표현하고, 위상 정렬을 통해 정점들을 선형으로 정렬할 수 있으며, 데이터 처리, 인과 구조 분석, 버전 관리 등 다양한 분야에서 활용된다.
| 강한 연결 요소 | |
|---|---|
| 정의 | |
| 설명 | 방향 그래프에서 모든 꼭짓점이 서로 도달 가능한 꼭짓점들로 이루어진 부분 그래프 |
| 속성 | |
| 관련 그래프 종류 | 방향 그래프 |
| 관련 개념 | 도달 가능성 연결 요소 응축 그래프 |
| 포함 관계 | 모든 꼭짓점은 고립점이거나, 어떤 강한 연결 요소에 속함. |
| 특징 | 방향 그래프의 정점 분할을 형성함. 위상 정렬을 통해 찾을 수 있음. |
| 활용 | 응축 그래프 구성 그래프 알고리즘 설계 |
| 알고리즘 | |
| 탐색 알고리즘 | 깊이 우선 탐색 너비 우선 탐색 |
| 대표적인 알고리즘 | 타잔의 강한 연결 요소 찾기 알고리즘 코사라주 알고리즘 파스칼 알고리즘 |
2. 정의
유향 그래프에서 그래프 상의 각 정점 쌍 사이에 경로가 양방향으로 존재하는 경우, 즉, 쌍의 첫 번째 정점에서 두 번째 정점으로의 경로가 존재하고, 두 번째 정점에서 첫 번째 정점으로의 다른 경로가 존재하는 경우, 그래프는 '''강하게 연결되었다'''라고 한다. 자체적으로 강하게 연결되지 않을 수 있는 유향 그래프 ''G''에서, 두 정점 ''u''와 ''v'' 사이에 양방향 경로가 존재하면 서로 강하게 연결되었다고 한다.
깊이 우선 탐색(DFS)을 기반으로 하는 알고리즘과 도달 가능성 기반 알고리즘을 통해 강한 연결 요소를 선형 시간 안에 계산할 수 있다.
강하게 연결되는 이진 관계는 동치 관계이며, 그 동치류의 유도된 부분 그래프를 '''강하게 연결된 성분'''(Strongly Connected Component, SCC)이라고 한다.[1] 동등하게, 유향 그래프 ''G''의 강하게 연결된 성분은 강하게 연결된 부분 그래프이며, 이 속성을 깨뜨리지 않고 ''G''의 추가적인 간선이나 정점을 부분 그래프에 포함할 수 없는 극대 원소이다. 강하게 연결된 성분의 모음은 ''G''의 정점 집합의 분할을 형성한다. 강하게 연결된 성분 ''C''는 ''C''가 간선으로 자체적으로 연결되지 않은 단일 정점으로 구성되어 있고, 그렇지 않은 경우 '비자명'인 경우 '자명'이라고 한다.[1]
각 강하게 연결된 성분이 단일 정점으로 정점 축약되면, 결과 그래프는 ''G''의 '''축약 그래프'''인 유향 비순환 그래프이다. 유향 사이클이 강하게 연결되어 있고 모든 비자명 강하게 연결된 성분은 적어도 하나의 유향 사이클을 포함하기 때문에, 유향 그래프는 한 개 이상의 정점을 가진 강하게 연결된 부분 그래프가 없는 경우에만 비순환적이다.
3. 알고리즘
DFS 기반 알고리즘에는 코사라주 알고리즘, 타잔의 강한 연결 요소 알고리즘, 경로 기반 강한 연결 요소 알고리즘 등이 있다. 코사라주 알고리즘은 DFS를 두 번 사용하는 반면, 타잔 알고리즘과 경로 기반 알고리즘은 한 번만 사용하므로 더 효율적이다.
도달 가능성 기반 알고리즘은 분할 정복 알고리즘 방식을 사용하며, 임의의 정점에서 도달 가능한 정점들을 기준으로 그래프를 분할하여 강한 연결 요소를 찾는다. 이 알고리즘들은 DFS 기반 알고리즘보다 병렬화에 유리하다는 장점이 있다.
3. 1. DFS 기반 선형 시간 알고리즘
깊이 우선 탐색을 기반으로 하는 여러 알고리즘은 선형 시간에 강한 연결 요소들을 계산한다.
코사라주 알고리즘은 개념적으로 간단하지만, 타잔의 알고리즘과 경로 기반 알고리즘은 깊이 우선 탐색을 한 번만 수행하면 되므로 더 효율적이다.
3. 2. 도달 가능성 기반 알고리즘
이전 선형 시간 알고리즘들은 일반적으로 병렬화하기 어려운 깊이 우선 탐색을 기반으로 한다.[17][6] 분할 정복 접근 방식을 사용하며, 이러한 알고리즘은 일반적으로 '도달 가능성 기반 강한 연결 요소 알고리즘'으로 불린다. 무작위로 피봇 정점을 뽑고, 이 정점에 대해 앞뒤 방향으로 도달 가능성 쿼리를 적용한다. 두 개의 쿼리는 정점들의 집합을 서로에게 도달 가능한 것, 한 방향으로만 도달 가능한 것(2개), 도달 가능하지 않은 것의 4개의 부분 집합으로 분할한다. 각 검색을 통해 도출한 정점 부분 집합은 강한 연결 요소를 형성하고, 알고리즘은 다른 3개의 부분집합에 대해서 재귀적으로 해를 구한다.[17][6]
이 알고리즘의 예상 순차 실행 시간은 O(''n'' log ''n'')이며, 기존 알고리즘보다 O(log ''n'')만큼 더 크다. 그러나 병렬성은 다음 요인에서 비롯된다. (1) 도달 가능성 쿼리는 (예: 너비 우선 탐색에 의해) 더 쉽게 병렬화할 수 있으며, 그래프의 지름이 작은 경우 빠를 수 있다. (2) 분할 정복 프로세스에서 하위 문제 간의 독립성.[18][7]
이 알고리즘은 실제 그래프에서 잘 작동하지만,[18][7] 병렬성에 대한 이론적 보장은 없다 (그래프에 간선이 없는 경우, 알고리즘은 O(''n'') 레벨의 재귀가 필요하다).
Blelloch 등은[19][8] 2016년에 도달 가능성 쿼리가 임의의 순서로 적용되면 O(''n'' log ''n'')의 비용 경계가 여전히 유지된다는 것을 보여준다. 또한, 질의는 접두사 두 배 방식(즉, 1, 2, 4, 8개 질의)으로 일괄 처리되어 한 라운드에서 동시에 실행될 수 있다. 이 알고리즘의 전체 스팬은 log2 ''n'' 도달 가능성 질의이며, 이는 도달 가능성 기반 접근 방식을 사용하여 달성할 수 있는 최적의 병렬성일 것이다.
4. 강한 연결 요소의 활용
강한 연결 요소를 찾는 알고리즘은 2-충족 가능성 문제나 둘메이지-멘델슨 분해와 같은 다양한 문제를 해결하는 데 응용될 수 있다.
4. 1. 2-충족 가능성 문제
2-충족 가능성 문제(변수 쌍의 값에 대한 제약 조건이 있는 부울 변수 시스템)를 해결하기 위해 강한 연결 요소를 찾는 알고리즘을 사용할 수 있다. 아스팔(Aspvall), 플라스(Plass), 타잔(Tarjan) (1979)은 ''v''와 ''v''의 대칭 요소가 인스턴스의 함축 그래프의 같은 강한 연결 요소에 포함된 변수 ''v''가 존재할 때만 2-충족 가능성 인스턴스가 충족 가능하지 않다는 것을 밝혀내었다.[20]4. 2. 둘메이지-멘델슨 분해
강하게 연결된 요소는 이분 그래프의 간선 분류인 둘메이지-멘델슨 분해를 계산하는 데 사용될 수 있다. 이 분류는 그래프의 간선들이 완벽 부합의 부분이 될 수 있는지에 따라 결정된다.[21]5. 관련된 결과들
로빈스의 정리에 따르면, 무향 그래프는 강하게 연결되도록 방향을 설정할 수 있는데, 이는 그래프가 2-간선 연결 그래프일 때와 같다.[12]
5. 1. 이어 분해
유향 그래프는 강하게 연결되어 있는 경우에만 귀 분해를 갖는데, 이는 간선들의 분할은 유향 경로와 순환으로 이루어진 그래프열이 되는것을 말한다.[22] 이때 첫 번째 부분 그래프는 순환이고, 다음에 나오는 부분 그래프는 이전의 부분 그래프와 하나의 정점을 공유하는 순환이거나 이전의 부분 그래프와 두 개의 끝점을 공유하는 경로이다.[22]5. 2. 로빈스 정리
로빈스의 정리에 따라 무향 그래프는 강하게 연결되도록 방향을 설정할 수 있는데, 이는 그래프가 2-간선 연결 그래프일 때와 같다. 이 결과를 증명하는 한 가지 방법은 무향 그래프의 귀 분해를 찾고 각 귀에 일관된 방향을 부여하는 것이다.[22][12]참조
[1]
논문
On finding the strongly connected components in a directed graph
[2]
서적
Introduction to Algorithms
MIT Press and McGraw-Hill
[3]
논문
A strong-connectivity algorithm and its applications in data flow analysis
[4]
논문
Depth-first search and linear graph algorithms
[5]
서적
A Discipline of Programming
Prentice Hall
[6]
논문
Parallel and Distributed Processing
[7]
논문
Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis - SC '13
[8]
논문
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA '16
[9]
간행물
Generating strongly connected random graphs
https://csce.ucmss.c[...]
CSREA Press
2018-02
[10]
논문
A linear-time algorithm for testing the truth of certain quantified boolean formulas
[11]
논문
Coverings of bipartite graphs
[12]
논문
A theorem on graphs, with an application to a problem on traffic control
[13]
서적
Introduction to Algorithms
MIT Press and McGraw-Hill
[14]
간행물
A strong connectivity algorithm and its applications to data flow analysis
[15]
논문
Depth-first search and linear graph algorithms
[16]
서적
A Discipline of Programming
Prentice Hall
[17]
간행물
On identifying strongly connected components in parallel
http://www.sandia.go[...]
IPDPS
[18]
간행물
On fast parallel detection of strongly connected components (SCC) in small-world graphs
https://ppl.stanford[...]
SC
[19]
간행물
Parallelism in Randomized Incremental Algorithms
http://www.cs.cmu.ed[...]
SPAA
[20]
논문
A linear-time algorithm for testing the truth of certain quantified boolean formulas
[21]
논문
Coverings of bipartite graphs
[22]
논문
A theorem on graphs, with an application to a problem on traffic control
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com