강한 연결 요소

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

정의

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

강하게 연결된 정점 쌍에서 경로의 존재에 대한 이항관계는 동치 관계이며, 동치류의 유도된 부분 그래프를 강한 연결 요소라고 부른다. 다르게 표현하면, 유향 그래프 G 의 강한 연결 요소는 강하게 연결된 부분그래프이고, 이러한 속성을 가지는 최대 그래프이다. 강하게 연결되는 특성을 깨뜨리는 정점과 간선 외에는 G 에서 부분 그래프에 포함될 수 있는 추가적인 간선 또는 정점이 없어야 한다. 강한 연결 요소의 모임은 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 등은 2016년에 무작위적인 순서의 도달 가능성 쿼리는 여전히 O(n log n)의 비용을 갖는다는 것을 보였다.^[7] 또한, 접두사 두배의 방식의(즉, 1, 2, 4, 8 쿼리) 쿼리들이 일괄처리될 수 있고, 한 라운드에서 동시에 실행된다. 이 알고리즘의 총 범위는 log₂ n 개의 연결 쿼리들인데, 이것은 도달 가능성 기반 접근법을 사용하여 달성 할 수 있는 최적의 병렬 처리 일 것이다.