강한 연결 요소

각각의 정점을 포함하는 길을 도달하는 유향 그래프
그래프에 강한 연결 요소를 표시한 모습

유향 그래프에서 모든 정점이 모든 다른 정점에 대해 도달 가능한 경우, 그래프는 강하게 연결되었다 또는 상호연결되었다라고 한다. 강한 연결 요소 또는 상호연결요소는 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향그래프의 분할이다. 그래프가 강하게 연결 되었는지와 그래프에서 강한 연결 요소를 찾는것은 선형 시간(Θ(V+E))에 가능하다 .

정의편집

유향 그래프에서 그래프 상의 각 정점 쌍에 사이에 경로가 존재하는 경우 그래프는 강하게 연결되었다라고 한다. 이것은 한쌍의 정점 중 첫번째 정점에서 두번째 정점으로의 경로가 존재하고, 두번째 정점에서 첫번째 정점으로 가는 다른 경로가 존재한다는 것이다. 유향 그래프 G 가 강하게 연결되지 않은 경우에도 한 쌍의 정점 u 와 v 에 대해 그들 사이에 서로에게 가는 경로가 있으면 정점 u 와 v 는 강하게 연결되었다고 할 수 있다.

강하게 연결된 정점 쌍에서 경로의 존재에 대한 이항관계는 동치 관계이며, 동치류의 유도된 부분 그래프를 강한 연결 요소라고 부른다.  다르게 표현하면, 유향 그래프 G 의 강한 연결 요소는 강하게 연결된 부분그래프이고, 이러한 속성을 가지는 최대 그래프이다. 강하게 연결되는 특성을 깨뜨리는 정점과 간선 외에는 에서 부분 그래프에 포함될 수 있는 추가적인 간선 또는 정점이 없어야 한다.  강한 연결 요소의 모임은 G의 정점집합의 분할을 형성한다.

 
파란색 유향 그래프를 응축시킨 노란색 비순환 유향 그래프.   노란색 그래프는 파란색 그래프의 강한 연결 요소를 응축시켜 하나의 노란색 정점으로 함으로써 만들어졌다. 

강한 연결요소들을 하나의 정점으로 응축시켰을 때 결과가 되는 그래프는 비순환 유향 그래프이며, 이를 의 응축이라고 한다. 유향 그래프는 강하게 연결된 부분 그래프가 없을 때만 순환이 없을 수 있는데, 왜냐하면 유향 순환은 강하게 연결되어있고 모든 강한 연결 요소는 적어도 하나의 유향 순환을 포함하기 때문이다.

알고리즘편집

DFS 기반 선형 시간 알고리즘편집

깊이 우선 탐색을 기반으로 하는 몇가지 알고리즘들은 선형 시간에 강한 연결 요소들을 계산할 수 있다.

  • 코사라주의 알고리즘은 두번의 깊이 우선 탐색을 거친다. 첫번째 탐색은 원본 그래프에서 두번째 깊이 우선 탐색의 외부 루프에서 방문된 점들을 테스트하고 방문되지 않은 점들을 재귀적으로 방문하는 정점의 순서를 정하는데 사용된다. 두 번째 깊이 우선 탐색은 원본 그래프의 역방향 그래프에서 진행되며, 재귀적 탐색으로 새로운 강한 연결 요소들을 찾는다.[1] 이 알고리즘은 1978년에 이 알고리즘에 대해 처음 설명한 (그러나 결과를 출판하지 않은) 삼바시바 코사라주의 이름을 따서 붙여졌지만, 1981년 미샤 샤리르에 의해 출판되었다.[2]
  • 타잔의 강한 연결 요소 알고리즘은 1972 년에 로버트 타잔에 의해 출판되었으며,[3] 한번의 깊이 우선 탐색을 거친다. 유지 스택 의 정점을 탐구되었으로 검색을 하지만 아직 지정되지 않는 구성 요소 및 계산"낮은 숫자를"각각의 정점(인덱스 번호의 조상이 닿을 수 있는 하나의 단계에서의 자손이 정점)하기 위해 사용되는 결정할 때 정점의 설정해야 팝 스택으로 새로운 구성 요소입니다.
  • 경로기반 강한 요소 알고리즘은 타잔의 알고리즘과 유사하게 깊이 우선 탐색을 하지만 두개의 스택을 사용한다. 스택 중 하나는 요소들에 추가되지 않은 정점의 경로를 기억하는데 사용되고, 다른 스택은 깊이 우선 탐색 트리의 현재 경로를 기억하는데 사용된다. 이 알고리즘의 선형시간 풀이는 1976년 에츠허르 데이크스트라에 의해 출판되었다.[4]

코사라주의 알고리즘은 개념적으로 간단하지만, 타잔의 알고리즘과 경로기반 알고리즘이 깊이 우선 탐색을 한번만 필요로 하는것에 비해 두번의 탐색을 필요로 한다.

도달 가능성 기반 알고리즘편집

이전 선형 시간 알고리즘들은 일반적으로 병렬화하기 어려운 깊이 우선 탐색을 기반으로 한다. 피셔 등은[5] 2000년에 도달 가능성 쿼리를 기반으로 한 분할 정복 접근 방식을 제안하였고, 이러한 알고리즘은 일반적으로 도달 가능성 기반 강한 연결 요소 알고리즘으로 불리게 되었다. 이러한 접근의 아이디어는 무작위적으로 피봇 정점을 뽑고, 이 정점에 대해 앞뒤 방향으로 도달 가능성 쿼리를 적용하는 것이다. 두개의 쿼리는 정점들의 집합을 서로에게 도달 가능한 것, 한 방향으로만 도달 가능한것(2개), 도달 가능하지 않은 것의 4개의 부분 집합으로 분할한다. 이렇게 강한 연결 요소가 부분 집합중 하나에 포함되어에 함을 보일 수 있다. 각 검색들을 통해 도출한 정점 부분 집합은 강한 연결 요소를 형성하고, 알고리즘은 다른 3개의 부분집합에 대해서 재귀적으로 해를 구하게 된다.

예상되는 이 알고리즘의 순차 실행 시간은 기존의 알고리즘에 O(log n)의 요소가 추가된 O(n log n)이다.  그러나 도달 가능성 쿼리는 병렬화 되기가 더 쉬우며(예를 들어 너비 우선 탐색를 통하여, 그리고 그래프의 지름이 작으면 빨라질 수 있다는 점에서), 분할 정복 과정에서 부분 문제들 간의 독립성에 의해 이 알고리즘은 병렬성을 갖게 된다. 이 알고리즘을 실세계(real-world) 그래프에서 잘 수행된다.[6] 그러나 병렬성으로 인한 이론적인 이득은 없다 (그래프에 간선이 없는 경우를 고려해 보면 ,알고리즘은 O(n)단계의 재귀를 필요로 한다).

Blelloch 등은[7] 2016년에 무작위적인 순서의 도달 가능성 쿼리는 여전히 O(n log n)의 비용을 갖는다는것을 보였다. 또한, 접두사 두배의 방식의(즉, 1, 2, 4, 8 쿼리) 쿼리들이 일괄처리될 수 있고, 한 라운드에서 동시에 실행된다. 이 알고리즘의 총 범위는 log2 n 개의 연결 쿼리들인데, 이것은 도달 가능성 기반 접근법을 사용하여 달성 할 수있는 최적의 병렬 처리 일 것이다.

강한 연결요소의 활용편집

강한 연결 요소를 찾기 위한 알고리즘은 2-충족 가능성(변수 쌍의 값에 대한 제약 조건이있는 부울 변수의 시스템) 문제를 해결하는데 사용될 수 있다.  Aspvall, Plass & Tarjan (1979)은 vv의 대칭 요소가 인스턴스의 함축 그래프의 같은 강한 연결 요소에 포함된 변수 v가 존재할 때만 2-충족 가능성 인스턴스가 충족 가능하지 않다는 것을 밝혀내었다. [8]

강하게 연결된 요소들은 또한 둘메이지-멘델슨 분해를 계산하는데 사용될 수 있는데, 이분 그래프의 간선들의 분류는, 그래프에서 그들이 완벽 부합의 부분이 될 수 있는지에 따르기 때문이다.[9]

관련된 결과들편집

유향 그래프는 강하게 연결되어 있는 경우에만 귀 분해를 갖는데, 간선들의 분할은 유향 경로와 순환으로 이루어진 그래프열이 된다. 이때 첫번째 부분 그래프는 순환이고, 다음에 나오는 부분 그래프는 이전의 부분 그래프와 하나의 정점을 공유하는 순환이거나 이전의 부분 그래프와 두개의 끝점을 공유하는 경로이다.

로빈스의 정리에 따라 무향 그래프는 강하게 연결된 것으로 방향 부여될 수 있으며, 이것은 항상 2 간선 연결 그래프이다. 이 결과를 증명하기 위한 한가지 방법은 하나의 기반이 되는 무향 그래프의 귀 분해를 찾고 각각의 귀마다 일정하게 방향을 부여하는 것이다.[10]

같이 보기편집

각주편집

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.
  2. Micha Sharir. A strong connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications 7(1):67–72, 1981.
  3. Tarjan, R. E. (1972), “Depth-first search and linear graph algorithms”, 《SIAM Journal on Computing1 (2): 146–160, doi:10.1137/0201010 
  4. Dijkstra, Edsger (1976), 《A Discipline of Programming》, NJ: Prentice Hall, Ch. 25 .
  5. Fleischer, Lisa K; Hendrickson, Bruce; and Pinar, Ali. On identifying strongly connected components in parallel. IPDPS 2000.
  6. Hong, Sungpack; Rodia, Nicole C; and Olukotun, Kunle. On fast parallel detection of strongly connected components (SCC) in small-world graphs Archived 2017년 8월 8일 - 웨이백 머신. SC 2013.
  7. Blelloch, Guy; Gu, Yan; Shun, Julian; and Sun, Yihan. Parallelism in Randomized Incremental Algorithms. SPAA 2016. doi:10.1145/2935764.2935766.
  8. 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 .
  9. Dulmage, A. L. & Mendelsohn, N. S. (1958), “Coverings of bipartite graphs”, 《Can. J. Math.》 10: 517–534, doi:10.4153/cjm-1958-052-0 .
  10. Robbins, H. E. (1939), “A theorem on graphs, with an application to a problem on traffic control”, 《American Mathematical Monthly46: 281–283, doi:10.2307/2303897, JSTOR 2303897 .

외부 링크편집