20 Jan 2020

Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그를 참고하였다.

1-1. Connected Components(연결요소)

그래프 $G$ 내에서 노드와 엣지가 서로 겹치지 않는 Subgraph.
이때, Subgraph 내의 모든 노드에 대해 경로가 존재한다.

연결요소에 대해 이해를 높이기 위해서는 Disjoint set(디스조인트 셋)이라는 자료구조에 대해 알 필요가 있다.

Disjoint set(디스조인트 셋)

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조
전체 집합이 있을 때, 구성 원소들이 겹치지 않도록 분할하는 데 자주 쓰인다.

Disjoint set의 연산은 make-set, union, find가 있다.

• make-set($x$) : $x$를 유일한 원소로 하는 새로운 셋을 만듬

• union($x, y$) : $x$가 속한 셋과 $y$가 속한 셋을 합침

• find($x$) : $x$가 속한 셋의 루트노드(대표값)를 반환함

예를 들어보자. 다음 그림은 Disjoint set $A = 3, 4$과 $B = 1, 2$이다.

따라서 find(4) = 3이고 find(3) = 3이다. 마찬가지로 find(2) = 1이고 find(1) = 1이다.

이 두 Disjoint set을 union해주면 다음과 같다. 이 Disjoint set의 루트노드는 1이다.

1-2. 연결요소 구축

다시 연결요소로 돌아오자. 연결요소를 구축하는 기법은 Disjoint set으로 구현하게 된다. 아래의 그림을 보자.

먼저, 위 그래프들의 Edge List는 다음과 같다.

$(b, d), 　(e, g), 　(a, c), 　(h, i), 　(a, b), 　(e, f), 　(b, c)$

우선 모든 노드에 대해 make-set 연산을 수행한다.(각 노드를 유일한 원소로 하는 새로운 셋을 만든다)

{$a$}, 　{$b$}, 　{$c$}, 　{$d$}, 　{$e$}, 　{$f$}, 　{$g$}, 　{$h$}, 　{$i$}, 　{$j$}

그 뒤, Edge List의 모든 엣지를 find 연산으로 하나씩 검토한다. $(b, d)$를 예로 들면, $b$와 $d$의 루트노드를 find연산으로 찾은 뒤, 값이 서로 다르다면 두 셋을 합치는 것이다. 위에서 $b$의 루트노드는 $c$이고, $d$의 루트노드는 $b$이다. 따라서 합쳐주면 된다. 결과는 다음과 같다.

{$a$}, 　{$b,d$}, 　{$c$}, 　{$e$}, 　{$f$}, 　{$g$}, 　{$h$}, 　{$i$}, 　{$j$}

이 과정을 Edge List의 모든 엣지에 시행하면 결과는 다음과 같다.

{$a,b,c,d$}, 　{$e,f,g$}, 　{$h, i$}, 　{$j$}

연결요소는 위와 같은 과정으로 만들 수 있다.

2-1. Strongly Connected Components(강연결요소)

유향그래프의 연결 요소 중, $u$에서 $v$로 향하는 경로와 $v$에서 $u$로 향하는 경로가 존재한다면 이 연결요소를 강연결요소라고 한다.

아래의 그림은 총 4개의 강연결요소가 있다.

2-2. 강연결요소 구축

원그래프 $G$의 노드 $a$에서 $b$로 향하는 경로가 있다고 하자. 그런데 엣지 방향을 정반대로 바꾼 $G^T$에서도 역시 $a$에서 $b$로 갈 수 있다면, $a$와 $b$ 사이에는 사이클(cycle)이 있어 강연결요소 속성을 만족한다.

그렇다면 강연결요소는 어떻게 구할 수 있을까? 기본적인 방법은 깊이우선탐색(DFS)를 기본으로 한다.

나중에 배우겠지만 미리 써먹자. 깊이우선탐색은 하나의 시작정점에서 출발하여 더 이상 나아갈 엣지가 없을 때 까지 깊이 탐색하는 그래프 순회기법이다. 연결된 정점이 없으면 나아갈 곳으로 되돌아간다(백트래킹). 이 탐색방법을 이용해 주어진 그래프의 강연결요소를 구해보자.

위 그래프에서 노드 안의 앞의 숫자는 start time(출발), 뒤의 숫자는 finish time(도착)이다. 먼저, 시작정점은 $c$이다. 이후 $c$에서 연결된 엣지 중 $g$로 향하는 엣지를 타고가서 $g$로 가자. 그러면 $g$의 출발했을 때의 숫자는 2가 된다(두 번째로 출발한 노드이니까). 그리고 $f$까지 가서 보니 $f$에는 연결된 엣지가 다시 $g$로 향하는 엣지 뿐이다. 따라서 도착하자마자 바로 떠나므로 3/4가 되는 것이다. 이 과정을 반복하면 위 그래프처럼 결과를 구할 수 있다.

이후, 그래프를 transpose한다. 노드는 그대로 두고 엣지의 방향만 바꾸는 것이다. 이후 transpose된 그래프를 대상으로 DFS를 다시 수행한다. 기존 그래프에 적용한 DFS의 finish time을 내림차순 정렬해 높은 숫자부터 시작하는 것이다. 따라서, 위 그래프에서는 $b$부터 시작한다. 결과는 다음과 같다.

이 그래프를 원래 그래프에 DFS를 수행한 것과 비교한다. 두 그래프의 DFS 결과 서로 도달 가능한 노드들, 즉 강연결요소를 음영처리하면 다음과 같다.

위 음영처리 된 노드들을 하나의 노드(메타 노드)로 묶어 표현하면 다음과 같다. 이러한 그래프를 메타 그래프라고 한다.

메타그래프는 DAG(유향비순환그래프)이다. 만약 메타그래프가 DAG가 아니라면, 즉 사이클이 있다면 이 메타그래프 전체가 또하나의 메타 노드가 되기 때문이다.