[Lecture] Cut Vertex

Cut Vertex

 

전제 : 전체가 연결된 graph가 있다고 했을 때 (일부분을 봐도 되지만, 여기선 그냥 전체를 전제로 한다)

Cut vertex를 버리면, graph가 disconnected graph가 된다

 

x와 y가 존재한다고 하자

x에서 y로 가는 모든 path가 s(Cut vertex)를 통해서 간다

 

그래프에서 Cut Vertex를 어떻게 찾을 수 있을까?

- 노드를 하나씩 빼보면서  disconnected graph가 되는지 확인한다

 

각 노드(N)에 대해 DFS를 한다(M+N) = O(N(M+N)) = O(MN)

 

Cut Vertex => cv로 대체한다

 

Idea1

child가 하나일 땐, parent는 cv가 아니다

왜냐하면, 하나의 노드가 사라진다고 해도, connected graph를 유지하기 때문이다

 

child가 두개일 땐, parent는 cv이다

하나의 child1 덩어리에서 child 2 덩어리로 가는 path를 찾아보자

cross edge가 없기 때문에, child1덩어리에 있는 노드는 parent를 거쳐 child2덩어리에 있는 노드를 접근해야한다

 

해당 Idea로 문제를 해결할 수 있지만, 여전히 각 노드에 대해서 DFS를 확인해야하기 때문에

시간복잡도 O(MN)이 걸린다

 

Idea2

Pre Order는 트리에 번호를 붙이는 것이다 (root 1 left child 2 right chid 3 .....) //DFS call이 들어간 순서를 의미한다 

모든 노드에 대해서, 세개의 값 중 가장 작은 것l(t)을 확인한다

t의 child는 u

1. Pre(t) (=~층수) // 자기 자신의 Pre Order를 확인한다

2. t에서 s까지가는 back edge 중에서 가장 작은 Pre(s)  // 제일 위로 가는(가장 Pre Order가 작은) back edge를 잡는다

3. Min of l(u) for all children of t // t의 child에서 제일 위로 올라가는 (가장 Pre Order가 작은)back edge를 잡는다

l(t)는 t의 서브트리 내에서 back edge를 한번 타서 올라갈 수 있는 가장 높은 위치의 노드 번호를 의미한다

 

u에서 위로 올라가는 것만 보는 이유

child1 덩어리에서 child2 덩어리로 가는 것은, (현재 cross edge는 없는 상태) 위를 거쳐서 가기 때문에

위로 올라갈 수 있는지만 확인하는 것이다

 

l(u) < Pre(t)

 u가 back edge를 통해서 t보다 높은 곳을(t를 거치지 않고) 올라갈 수 있다면 cv가 아니다

 

l(u) >= Pre(t) (값이 크다는 것은 더 아래쪽에 있다는 얘기)

u가 back edge를 통해 위로 올라간 최대 높이가 같거나 아래에 있을 땐, u가 위로가기 위해선 무조건 t를 거쳐야한다는 것을 의미한다

이 경우가 하나라도 있으면, t는 cv이다

 

1. DFS에서 chld가 leaf노드이면 cv가 아니다

증명)

2. t가 cv이면, u도 cv일까? 아니다

증명) 

 

- Pre(t) : 처음 DFS Tree를 생성하면서 계산됨

- t와 연결된 back edge의 반대쪽 노드들의 pre()값들도 금방 계산됨

- t의 자손들의 l() 값들 중 최솟값 : 밑에서부터 traversal(DFS를 하면 된다)하면, O(M+N)이다

 

Cut Edge?

모든 edge마다 새로운 빨간 노드를 추가한다 빨간색 노드가 cv이면, 해당 edge가 ce이다

u 위로 올라가는 back edge가 없다면, 해당 edge는 cut edge이다