33. cut vertex [12 2주차]

33. Cut Vertex [12-2주차]

2024년 1월 14일 일요일

오후 4:54

<Cut Vertex 찾기 문제>

모든 노드가 연결된 그래프에서 어떤 노드가 없어지면 그래프가 끊어지는 경우, 그 노드를 Cut Vertex라고 한다.

 

다른 관점에서의 정의 : 노드 v에 대해, 노드 x와 y를 잇는 모든 경로가 노드 v를 지나가도록 하는 노드 x, y가 존재하는 경우, 노드 v를 Cut Vertex라 한다.

 

이 문제의 쉬운 해법은 Reachability를 이용하는 것이다. 노드 하나를 제거하고 Reachability를 했을 때 나머지 모든 노드가 마킹되지 않았다면, 제거된 노드가 Cut Vertex이다.

 

노드가 V개, 간선이 E개인 그래프의 모든 Cut Vertex를 찾는 데 걸리는 시간은?

• Rechability가 O(V+E)시간이 걸리므로 각 노드를 없애고 Rechability를 하면 O(V²+VE) 시간이 걸린다.
• 그런데 DFS트리를 이용하면 O(V+E)시간에 Cut Vertex를 모두 구할 수 있다.

 

 

<DFS Tree를 이용한 Cut Vertex 찾기 : 루트 노드 >

DFS 트리에서 루트 노드가 Cut Vertex인지는 쉽게 알 수 있다.

 

• 루트 노드의 자식 노드가 하나인 경우 :

루트 노드를 없애도 자손 노드들이 전부 연결되어 있으므로 Cut Vertex가 아니다.

 

• 루트 노드의 자식 노드가 두 개 이상인 경우 :

자식 노드를 루트 노드로 하는 서로 다른 서브트리 간에는 서로를 연결하는 간선이 존재할 수 없다. 무방향 그래프에는 Cross edge가 존재하지 않기 때문이다.

따라서 루트 노드가 없어지면 서브트리 간 연결이 끊어지며, 루트 노드는 Cut Vertex임을 알 수 있다.

 

루트 노드에 대해서만 cut vertex인지 알 수 있으므로, DFS를 V번 돌려야 하여 여전히 O(V²+VE)시간이 걸린다.

시간을 줄이기 위해서 DFS트리의 루트가 아닌 노드들도 Cut Vertex인지를 판별해야 한다.

 

 

<DFS Tree를 이용한 Cut Vertex 찾기 : 모든 노드>

어떤 노드 v의 자식 노드가 c1, c2, c3, … 일 때, 그 자식 노드들을 루트 노드로 하는 서브트리를 S1, S2, S3, … 라 하자.

노드 v가 제거된다면, DFS트리 내에서 서브트리들은 서로 끊어진 상태가 된다. 서로 다른 서브트리에 있는 두 노드를 직접 연결하는 간선은 존재하지 않으므로, 두 서브트리가 연결되기 위해서는 서브트리의 노드와 v의 조상 노드를 연결하는 back edge가 존재해야 한다. 만약 어떤 서브트리 내에 v의 조상 노드와 연결해 주는 back edge가 존재하지 않는다면, 그 서브트리는 다른 서브트리와 연결될 수 없고, v는 Cut Vertex임을 알 수 있다.

 

또한 모든 서브트리가 v의 조상 노드와 연결되어 있다면, 서브트리가 모두 연결되므로, v는 Cut Vertex가 아니다.

 

조상 노드의 Pre번호가 자손 노드의 Pre번호보다 작다는 점을 이용해 서브트리에 v의 조상 노드와 연결된 back edge가 있는지를 판단할 것이다.

 

또한 어떤 노드 c에 대해, l(c)를 다음과 같이 정의한다.

 

min(Pre(s))는 c의 back edge와 연결된 노드 중 가장 높이 위치한 것의 Pre 값을 의미하며,

min(l(u))는 c의 자손 노드들과 back edge로 연결된 가장 높이 위치한 노드의 Pre값을 의미한다.

 

• l(c1), l(c2), l(c3), … 중 하나라도 Pre(v)보다 크거나 같은 것이 있는 경우 :

v의 조상 노드와 back edge로 연결되지 않은 서브트리가 존재한다는 뜻이므로, v는 Cut Vertex이다.

• l(c1), l(c2), l(c3), … 이 모두 Pre(v)보다 작은 경우 :

모든 서브트리가 v의 조상 노드를 통해 서로 연결되어 있으므로, v는 Cut Vertex가 아니다.

 

• l(c)을 정의한 식에서 Pre(c)를 구하는 것은 정답을 구하는 데 쓸모없어 보인다. 그럼에도 Pre(c)를 구하는 이유는 c가 back edge가 없는 리프 노드인 경우, Pre(c)가 없으면 l(c)가 정의되지 않기 때문이다.

 

 

<DFS Tree를 이용한 Cut Vertex 찾기 : 시간복잡도>

모든 노드 v에 대해 l(v)를 계산해야 한다. 이때 아래쪽 노드의 값부터 계산하여 그 값을 이용해 위쪽 노드의 l값을 계산한다. 즉, dynamic programming을 이용한다.

 

Pre값은 DFS실행 과정에서 구하면 된다. 마찬가지로, l값을 구하는 것과 Cut Vertex를 판별하는 것도 DFS 실행 과정에서 할 수 있다.

 

한 노드가 Cut Vertex인지 판별하기 위해서는 그 노드의 Pre값과 자식 노드의 l값을 비교하면 되므로, Cut Vertex인지 판별하는 데 노드당 자식 개수에 비례하는 시간이 걸린다. 전체로는 DFS 트리의 간선 개수에 비례하는 시간이 걸린다.

 

노드 v의 l값을 구하기 위해 v의 자식 노드들의 l값들을 서로 비교해야 하고, v의 back edge에 연결된 노드들의 Pre값도 비교해야 한다.

노드 v의 l값을 구하는 데 걸리는 시간은 v의 자식 노드 개수와 back edge 개수의 합에 비례하게 된다. 따라서 전체 노드의 l값을 구하는 데 걸리는 시간은 그래프의 간선 개수에 비례하여, O(E)시간이 걸린다.

 

DFS 에는 O(V+E)시간이 걸리므로, DFS를 이용해 Cut Vertex를 찾는 데 총 O(V+E) 시간이 걸린다.