3-edge-connectivity notes

대충 이 노트 의 끝자락에서 한 얘기를 정리했다.

그래프가 2-edge-connected 라고 가정하자. (그렇지 않다고 하더라도 코드가 크게 바뀌지 않는다)

알고리즘은 재귀적이다. 그래프 $G$ 의 DFS 트리에 대해서, 특정 서브트리의 노드를 모두 3-connected-component로 바꿔주는 알고리즘이 존재하고, 이 알고리즘을 bottom-up 으로 호출하면서 "서브트리의 답을 합쳐주면" 된다.

2-connected 인 경우를 예시로 생각해 보자. 서브트리를 컴포넌트로 분할하는 알고리즘이 있다면, bottom-up 알고리즘은 절선으로 연결되어 있지 않으며 루트를 포함하는 컴포넌트들을 가져온 후 이들을 합쳐주면 된다. 3-connected 의 경우에는 컴포넌트 하나만 가져올 수는 없으나, 대신 DFS 트리 경로로 연결된 컴포넌트 체인을 가져올 수 있다. Cactus representation이 있다는 걸 생각해 보면 이해하기 쉽다.

목표는 그래프 $G$ 의 DFS tree에 대해서, 특정 서브트리의 노드들을 모두 3-connected-component로 합쳐주고, 합쳐준 component 들 중 부모와 연결될 가능성이 있는 것을 path order로 반환하는 재귀적 알고리즘을 만드는 것이다. 자식에 대해서 3-connected component들을 다 구했다고 하면, 이제 선형으로 된 체인들이 존재할 텐데, 이를 적당히 합쳐주는 것이 알고리즘의 목표이다. 이 때 component의 표현은 union-find를 사용한다.

첫 번째로 각 체인의 맨 위 컴포넌트의 차수가 $2$ 이하인 경우를 생각해 보자. 이 경우 해당 컴포넌트는 다른 컴포넌트와 합쳐질 가능성이 없다. 고로 더 이상 고려해 줄 필요가 없고 이 컴포넌트를 제거해 준다. 이제 남은 컴포넌트의 차수는 모두 $3$ 이상이다.

두 번째로 $v$ 의 서로 다른 두 자식이 있을 때, low-link가 큰 쪽의 컴포넌트는 모두 $v$ 와 같은 컴포넌트에 속한다. 그림으로 보면 이해하기 쉽다. $low(w_1) \le low(w_2)$ 인 경우, $v$ 와 $w_2$ 사이에 다음과 같은 세 edge-disjoint path를 찾을 수 있다. 차수가 3 이상인 것이 중요하다. 이렇게 하면 결국 low-link가 최소인 체인만 남고 3-connected component가 path 형태로 나열됨을 볼 수 있다.

위 두 케이스에서 트리 엣지들은 모두 고려했는데 백엣지는 고려되지 않았다. 리프에서 루트로 가는 방향의 백엣지는 위의 논리와 동일하게 지금까지 본 $v$ 의 서브트리를 모두 하나의 컴포넌트로 만들어 준다. 루트에서 리프로 가는 방향의 백엣지는, 해당 백엣지에서 $v$ 로 가는 path와 겹치는 컴포넌트들을 모두 하나로 합쳐준다. DFS 트리를 만들면서 euler tour interval을 만들 수 있어서 쉽게 합쳐줄 수 있다. 아래 그림을 보면 각 컴포넌트에서 $v$ 로 가는 edge-disjoint path가 존재함을 볼 수 있다.

이제 마지막으로 어려운 것은 degree를 구하는 것이다. 간단히 생각하면 두 정점을 합칠 때 루프가 하나 사라지고, 고로 degree를 2만큼 줄이면 될 것 같다. 하지만 정점을 합치는 과정에서 중복 간선이 생기기 때문에 이는 틀린 논리이다. small-to-large를 써도 되기는 하겠으나 간단한 방법이 존재한다. 결국 중복 간선은 백엣지들에 의해서 생긴다. 루트에서 리프로 가는 방향의 백엣지를 처리하는 결과로, 어차피 백엣지의 양쪽 끝은 같은 컴포넌트에 속하게 된다. 고로 루트 -> 리프 방향의 백엣지가 처리되는 시점에서 해당 정점의 차수를 2씩 줄여주면 된다. 트리엣지는 그냥 위랑 똑같이 합치면서 차수를 2씩 줄여주면 된다. degree를 구할 때 전체 그래프에서 시작하는 것이 아니고, DFS가 간선을 발견하는 시점에 degree를 조정하는 식으로 해야 함에 유의해야 한다.

코드
연습 문제 1
연습 문제 2
연습? 문제 3
연습? 문제 4