강하게 연결된 구성 요소
Strongly connected component관련 항목 |
그래프 연결 |
---|
지시된 그래프의 수학 이론에서, 모든 꼭지점에 다른 모든 꼭지점에서 도달할 수 있다면 그래프는 강하게 연결되어 있다고 한다.임의로 지시된 그래프의 강하게 연결된 구성요소는 그 자체로 강하게 연결된 하위 그래프로 분할을 형성한다.그래프의 강한 연결성을 테스트하거나, 그래프의 강하게 연결된 구성요소를 선형 시간(즉, θ(V + E))으로 찾을 수 있다.
정의들
방향 그래프는 그래프의 각 꼭지점 쌍 사이에 각 방향에 경로가 있으면 강하게 연결된다고 한다.즉, 쌍의 첫 번째 꼭지점에서 두 번째 꼭지점까지 경로가 존재하며, 두 번째 꼭지점에서 첫 번째 꼭지점까지 다른 경로가 존재한다.그 자체가 강하게 연결되지 않을 수도 있는 방향 그래프 G에서, 정점 u와 v의 쌍은 그 사이에 각 방향에 경로가 있으면 서로 강하게 연결되어 있다고 한다.
강하게 연결되는 이항 관계는 동등성 관계이며, 그 동등성 등급의 유도 하위 그래프를 강하게 연결된 성분이라고 한다.동등하게 방향 그래프 G의 강하게 연결된 구성요소는 강하게 연결된 서브그래프로서, 이 특성과 함께 최대치가 된다. G의 추가 에지나 정점들은 강하게 연결된 특성을 깨지 않고는 서브그래프에 포함될 수 없다.강하게 연결된 요소들의 집합은 G의 정점 집합의 분할을 형성한다.

강하게 연결된 각 구성요소가 하나의 꼭지점에 수축된 경우, 결과 그래프는 방향의 아세클릭 그래프, G의 응축이다. 지시된 그래프는 두 개 이상의 꼭지점을 가진 강하게 연결된 하위그래프가 없는 경우에만, 방향 사이클이 강하게 연결되어 있고 모든 비거리 강하게 연결된 구성요소가 c.최소 한 개의 방향 사이클을 가진 온트.
알고리즘
DFS 기반 선형 시간 알고리즘
깊이 기반한 여러 알고리즘은 먼저 검색이 강력하게 연결된 구성요소를 선형 시간으로 계산한다.
- 코사라주의 알고리즘은 두 번의 깊이 첫 번째 검색 패스를 사용한다.첫 번째 그래프에서는 두 번째 깊이의 바깥쪽 루프가 이미 방문한 적이 있는지 정점을 테스트하고 그렇지 않은 경우 반복적으로 탐색하는 순서를 선택하는 데 사용된다.두 번째 깊이 첫 번째 검색은 원래 그래프의 전치 그래프에 표시되며, 각 재귀 탐색은 강하게 연결된 하나의 새로운 구성요소를 찾아낸다.[1][2]1978년 그것을 기술한 S. 라오 코사라주(그러나 그의 결과를 발표하지 않았다)의 이름을 따서 지은 것이다. 미차 샤리르는 이후 1981년에 그것을 출판했다.[3]
- 1972년 로버트 타르잔에 의해 출판된 타르잔의 강하게 연결된 구성요소 알고리즘은 첫 번째 검색의 단 한 번의 통과를 수행한다.[4]검색에 의해 탐색되었지만 구성요소에 아직 할당되지 않은 정점 스택을 유지하고, 정점 집합을 스택에서 새 구성요소로 푸시해야 하는 시기를 결정하는 데 사용하는 각 정점(정점 후예에서 한 번에 도달할 수 있는 가장 높은 상위 항목의 색인 번호)의 "낮은 숫자"를 계산한다..
- 경로 기반 강력한 구성요소 알고리즘은 타르잔의 알고리즘처럼 깊이 첫 번째 검색을 사용하지만 두 개의 스택이 있다.스택 중 하나는 구성 요소에 아직 할당되지 않은 정점을 추적하는 데 사용되는 반면, 다른 하나는 깊이 첫 번째 검색 트리에서 현재 경로를 추적하는 데 사용된다.이 알고리즘의 첫 번째 선형 시간 버전은 1976년에 Edsger W. Dijkstra에 의해 출판되었다.[5]
코사라주의 알고리즘은 개념적으로 단순하지만 타르잔과 경로 기반 알고리즘은 두 개보다는 한 개의 깊이 우선 검색만 필요하다.
도달 가능성 기반 알고리즘
이전의 선형 시간 알고리즘은 일반적으로 병렬화하기 어려운 것으로 간주되는 깊이 우선 검색을 기반으로 한다.2000년에 Fleischer 외 [6]연구진은 도달성 질의를 기반으로 한 분할 및 재무 접근법을 제안했고, 그러한 알고리즘을 보통 도달성 기반 SCC 알고리즘이라고 부른다.이 접근방식의 아이디어는 무작위 피벗 정점을 선택하고 이 정점에서 전방 및 후방 도달 가능성 쿼리를 적용하는 것이다.두 쿼리는 설정된 정점을 4개의 하위 집합으로 분할한다. 즉, 둘 다에 도달한 정점, 하나 또는 하나도 검색하지 않은 정점.하나는 강하게 연결된 구성 요소가 하위 집합 중 하나에 포함되어야 함을 보여줄 수 있다.두 검색으로 도달한 정점 부분 집합은 강하게 연결된 구성요소를 형성하고 알고리즘은 나머지 3개 하위 집합에 반복된다.
이 알고리즘의 예상 순차적 실행시간은 O(n log n)로 나타나는데, 이는 고전적 알고리즘보다 O(log n)가 많은 계수다.병렬은 (1) 도달성 질의를 보다 쉽게 병렬화할 수 있으며(예: 너비 우선 검색(BFS)에 의해), (2) 분할 및 결합 프로세스에서 하위 작업 사이의 독립성에서 비롯된다.이 알고리즘은 실제 그래프에서는 잘 작동하지만 병렬에 대한 이론적 보장은 없다([2]그래프에 에지가 없다면 알고리즘에는 O(n) 수준의 재귀가 필요하다).
2016년 [7]블렐로치 등은 도달성 질의를 무작위 순서로 적용해도 O(n log n)의 원가 경계가 여전히 유지된다는 것을 보여준다.더 나아가 쿼리는 접두사-더블 방식(즉, 1, 2, 4, 8 쿼리)으로 일괄 처리하여 한 라운드에서 동시에 실행할 수 있다.이 알고리즘의 전체 범위는 로그2 n 도달 가능성 쿼리로, 이것은 아마도 도달 가능성 기반 접근법을 사용하여 달성할 수 있는 최적의 병렬 처리일 것이다.
강력하게 연결된 임의 그래프 생성
Peter M. Maurer는 강력한 연결 증대를 위한 알고리즘의 수정, 그래프를 강하게 연결하기 위해 가능한 적은 에지를 추가하는 문제에 기초하여,[8] 무작위로 강하게 연결된 그래프를 생성하기 위한 알고리즘을 설명한다.노드 라벨이 있는 Gilbert 또는 Erdős-Rényi 모델과 함께 사용할 경우, 알고리즘은 생성될 수 있는 구조물의 종류에 제한 없이 n개 노드에 강하게 연결된 그래프를 생성할 수 있다.
적용들
강하게 연결된 요소들을 찾는 알고리즘(부울 변수의 변수 쌍의 가치에 제약 조건들과 시스템)2-satisfiability 문제를 해결하기 위해:Aspvall, Plass&Tarjan(1979년)을 보여 주고 경우에만 가변 v은 v와 보충하는bo 그렇게 된2-satisfiability 인스턴스unsatisfiable은 사용할 수 있다.번째 c해당 인스턴스의 시사 그래프에서 강하게 연결된 동일한 구성요소에 존재함.[9]
또한 그래프에서 완벽한 일치의 일부가 될 수 있는지에 따라 초당적 그래프의 가장자리 분류인 Dulmage-Mendelson 분해를 계산하는 데 강하게 연결된 성분이 사용된다.[10]
관련결과
지시된 그래프는 귀 분해, 가장자리의 분할, 일련의 지시된 경로 및 주기(순서의 첫 번째 하위 그래프가 주기)로 되어 있는 경우에만 강하게 연결되며, 각 후속 하위 그래프는 이전 하위 그래프와 하나의 꼭지점을 공유하는 주기 또는 이전 하위 그래프와 두 개의 끝점을 공유하는 경로 중 하나이다.서브그래프
로빈스의 정리에 따르면, 만약 그것이 2개의 가장자리로 연결되어 있다면, 그리고 그것만이 강하게 연결될 수 있는 방법으로 방향을 잡을 수 있다.이 결과를 증명하는 한 가지 방법은 밑바탕에 있는 비방향 그래프의 귀 분해를 찾아 각 귀의 방향을 일관되게 정하는 것이다.[11]
참고 항목
참조
- ^ 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein.알고리즘 소개, Second Edition.MIT 프레스 앤 맥그로우 힐, 2001. ISBN0-262-03293-7.섹션 22.5, 페이지 552–557.
- ^ a b Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013), "On fast parallel detection of strongly connected components (SCC) in small-world graphs" (PDF), Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis - SC '13, pp. 1–11, doi:10.1145/2503210.2503246, ISBN 9781450323789
- ^ Sharir, Micha (1981), "A strong-connectivity algorithm and its applications in data flow analysis", Computers & Mathematics with Applications, 7: 67–72, doi:10.1016/0898-1221(81)90008-0
- ^ Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146–160, doi:10.1137/0201010
- ^ Dijkstra, Edsger (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25.
- ^ Fleischer, Lisa K.; Hendrickson, Bruce; Pınar, Ali (2000), "On Identifying Strongly Connected Components in Parallel" (PDF), Parallel and Distributed Processing, Lecture Notes in Computer Science, vol. 1800, pp. 505–511, doi:10.1007/3-540-45591-4_68, ISBN 978-3-540-67442-9
- ^ Blelloch, Guy E.; Gu, Yan; Shun, Julian; Sun, Yihan (2016), "Parallelism in Randomized Incremental Algorithms" (PDF), Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA '16, pp. 467–478, doi:10.1145/2935764.2935766, ISBN 9781450342100.
- ^ Maurer, P. M., Generating strongly connected random graphs (PDF), Int'l Conf. Modeling, Sim. and Vis. Methods MSV'17, CSREA Press, ISBN 1-60132-465-0, retrieved December 27, 2019
- ^ Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4.
- ^ Dulmage, A. L. & Mendelsohn, N. S. (1958), "Coverings of bipartite graphs", Can. J. Math., 10: 517–534, doi:10.4153/cjm-1958-052-0.
- ^ Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly, 46 (5): 281–283, doi:10.2307/2303897, JSTOR 2303897.
외부 링크
- jBPT 라이브러리에서 강하게 연결된 구성 요소의 계산을 위한 Java 구현(강력 연결 구성 요소 클래스 참조).
- C++ 강력한 연결 구성 요소 구현