DFS Tree의 성질을 이용하여 Articulation Point를 찾기

DFS Tree의 성질과 Articulation Point(단절점)의 정의를 활용하여 Graph에서 Articulation Point(단절점)를 찾아보자.

Definition of Articulation Point

단절점의 정의 : 어떤 Graph G에 속하는 vertex v에 대하여 vertex v와 vertex v와 incident한(edge의 구성요소로 v를 가지고 있는) edge를 G에서 제거했을 때, G가 disconnected 된다면 vertex v는 G의 Articulation Point가 된다,

*Definition of Connected G : G에 속하는 임의의 vertex v, w에 대하여 v에서 w가 reachable 하고 w에서 v가 reachable 하면 G는 connected 하다.

How to Find Articulation Point

> 보조정리1. DFS Tree에서 Root Node의 Child Node의 개수가 2개 이상이면 그 Root Node는 Articulation Point이다. (필요충분조건)

proof

i) -> 방향 증명
--> Contradiction(귀류법). 만약 Root Node가 Articulation Point가 아니라면 Graph G에서 Root Node를 제거한 G가 connected여야 한다. 그러나 DFS Tree에서는 Cycle이 존재하지 않으므로 (by Def of DFS Tree) 모순!

ii) <- 방향 증명
--> Contradiction. Child Node의 개수가 1개 이하라면 Root Node를 제거한 Graph G가 Connected이므로 Root Node가 Articulation Point라는 가정에 모순!

보조정리2. Non-Root Node인 Graph G에 속하는 임의의 vertex v와 v의 1) Child Node가 u일 때 2) descendant u와 v의 proper Ancestor간 edge가 없으면 v는 Articulation Point. (필요충분조건)

proof

i) -> 방향 증명
Contradiction. v가 Articulation Point가 아니라면, u의 descendant를 포함하는 subtree와 v의 proper Ancestor가 Connected여야하는데 둘 사이에 edge가 없으므로 모순!

ii) <- 방향 증명
Contradiction. V가 Articulation Point임에도 불구하고 v의 proper Ancestor와 v의 child node u의 descendant u사이에 edge가 존재하면 v를 뺀 G는 connected이므로 모순!

key lemma 3: leaf Node는 Aritculation Point가 될 수 없다.

proof

DFS Tree상에서 leaf Node와 incident한 backEdge가 존재하지 않을 때, leaf Node를 제거하더라도 여전히 남아있는 그래프 G는 Connected하다.

이 세가지 정리를 이용하여 그래프 G에 속하는 Vertex들이 Articulation Point인지 판단해주면 된다.

이것을 의사코드로 나타내면 다음과 같다.

### Pseudo Code
#pre[v] : v를 첫 방문한 순서
#low[v] : v의 descendant u(u=v일 수 있음)와 incident한 Back-Edge (u,w)가 존재할 경우 low[v] = min(pre[u], pre[w])로 정의
ArticulationPoint = [False for _ in range(V+1)]

counter = 1 #첫 방문 순서와 방문을 완료한 순서를 기록하기 위한 global변수

def DFS(v, parent of v, root Node)
	visited[v] = True
    pre[v] = low[v] = counter++
    children = 0
    
    for u in graph[v]:
    	if visited[u] and u != parent of v:
        	low[v] = min(low[v], pre[u]) #(v에서 u로의 Back-Edge가 존재할 때)
            
        else:
        	DFS(u, v, root Node)
            low[v] = min(low[v], low[u])
            if low[u] >= low[v] and v != Root Node:
            	ArticulationPoint[v] = True
        		children += 1
                
    if v == root Node and children > 1:
    	Articulation[v] = True

연관문제

BOJ 11266 : https://www.acmicpc.net/problem/11266

답안 예시

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def explore(graph, v, visited, r, root):
    global counter
    children = 0
    visited[v] = True
    pre[v] = counter
    low[v] = counter
    counter = counter + 1

    for i in graph[v]:
        if (visited[i]):
            if (r != i): #BackEdge에 대해서만 low 갱신할 수 있도록 parent의 pre는 배제
                low[v] = min(low[v], pre[i])
        else:
            explore(graph, i, visited, v, root)
            low[v] = min(low[v], low[i])
            if (low[i] >= pre[v]):
                if (v != root):
                    cutPoint[v] = True
            children += 1

    if (r==0 and (children>1)):
        cutPoint[v] = True



V, E = map(int, input().split())
graph = [ [] for i in range(V+1) ]
visited = [False for _ in range(V+1)]
cutPoint = [False for _ in range(V+1)]
pre = [0 for i in range(V+1)]
low = [0 for i in range(V+1)]

counter = 1

for _ in range(E):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, V+1):
    root = i
    explore(graph, i, visited, 0, root)


ans = ''
cnt = 0
for i in range(1, V+1):
    if (cutPoint[i] == True):
        cnt += 1
        ans += f'{i} '
print(cnt)
if cnt:
    print(ans)