이중 연결 요소
이중 연결 요소
분절점 (Articulation point)
그래프 G의 버텍스 v 의 삭제가 v 와 인접한 엣지들과
최소 두 개의 연결 성분을 가진 그래프 G’를 만들 때
버텍스 v 를 분절점이라고 한다.
이중연결 그래프 (Biconnected Graph)
이중연결 그래프는 분절점이 없는 연결된 그래프
이때 이 그래프가 최대가 되게 하는
maximal biconnected subgraph 를 이중연결 성분이라고 한다.
maximal biconnected 라는 것은
이중연결 그래프이면서, 즉 분절점이 없으면서
그 크기가 최대여야 한다는 뜻이다.
이중연결 성분 구하기
dfs 트리를 통해서 depth first spanning tree 를 그려보자.
여기서 자신의 자식 중에 자신의 조상 노드로 가는 백엣지가 있다면 이는 분절점이 아님을 확인할 수 있다.
또한 예외로, 두 개 이상의 자식을 갖는 루트는 분절점이다.
이중연결 성분을 구하기 위해서
low 와 dfn 의 도입이 필요하다.
dfn 은 이전에 나왔던 prev number 와 같다. 방문된 순서이다.
low 는 버텍스의 후손 중에서 최대 한 개의 백엣지를 통해서 갈 수 있는 버텍스의 dfn 중 최소의 값이다.
low 는 자기 자신의 dfn , 자식의 low, 자신한테 달린 백엣지로 이어진 노드의 dfn 중 최소 값이다.
low(u) = min { dfn(u), min{low(w)|w is a child of u}, min{dfn(v)|(u, v) is a back edge}}
low 와 dfn
왼쪽의 수는 dfn 으로, 루트는 0에서 시작한다.
low 는 돌아오면서 계산한다. (dfs 의 종료 직전)
왼쪽의 leaf 노드인 0 버텍스는 갈 곳이 없으므로 함수를 종료하면서
자기 자신의 dfn, 자식의 low, 자신의 백엣지와 이어진 노드의 dfn 중 최소값을 택하게 되는데,
이 경우엔 자식이나 백엣지가 없으므로 자기 자신의 dfn 인 4가 된다.
그 다음 1 버텍스는 백엣지가 있고, 이와 연결된 3 버텍스의 dfn 은 0이므로 low는 0이 된다.
(1 < 4)
2 버텍스는 자식인 1의 low 가 0 이로 최소값이 되어 이의 low 도 0이 된다.
4 버텍스도 같은 이유로 0의 low 를 가진다.
3 버텍스도 그러하다.
오른쪽 트리도 같은 방식으로 low 를 정하면 된다.
분절점 결정하기
자기 자신의 dfn 이 자식의 low 보다 낮거나 같으면 이는 분절점이다.
이것의 의미는, 자식은 자신을 통하지 않고는 자신의 위로 갈 수 없다는 뜻이 된다.
시간복잡도
이중연결요소는 DFS 한 번이면 끝난다.
따라서 시간복잡도도 DFS와 같다.
O(m + n)
m : 노드의 수
n : 엣지의 수
코드
이중연결 요소를 구하는 코드를 작성해본다.