Cut Vertex

이번 포스팅에서는 Cut Vertex란 무엇인지 그에 대한 정의와, 판별하는 방법에 대해 알아보겠습니다.

그에 더불어 dfs graph, back edge 에 대한 개념도 살펴봅시다.

 

Definition of Cut Vertex

If node s is Cut Vertex,

• Removing a node s makes Graph G Disconnected.
• Exists x and y s.t., all paths from x to y goes through s.

 

Cut vertex 정의

1. 연결 그래프 G에서 노드 S를 없앴더니 비연결 그래프가 되었을때, S를 Cut vertex(단절점)라 부른다.

• 없앴을 때 Disconnected Graph 를 만드는 S를 Cut Vertex 라고 부른다.

2. 노드 X에서 Y로 가는 모든 경로가 반드시 노드 S를 지나게 된다면, S는 cut vertex이다.

이를 그림으로 나타내면 다음과 같다.

일반적인 정의는 (1)번이지만, (2)번 또한 (1)번과 같은 뜻임을 보이자.

 

(1)번 정의에 의해, Cut vertex인 정점 S를 빼면, Connected Graph → Disconnected Graph 가 된다.

• 이때 2개의 Connected Component가 생긴다.

(2)번 정의에서 어떤 정점 x, y에 대해 둘 사이의 경로는 무조건 정점 S를 지나게 된다.

S가 지워지면 위 그림과 같이 Disconnected Graph가 만들어지는것은 자명하다.

x에서 y까지 연결된 경로가 없으므로 비연결 그래프가 된다. 따라서 (2)도 (1) 과 같은 뜻이다.

 

 

이제 그래프에서 cut vertex를 어떻게 구할 수 있을지 알아보자.

 

사전 정보

• 주어진 그래프에 DFS를 적용하여 DFS Tree를 만든다.
• G의 DFS 트리 : T 라 하자.

 

DFS 트리란?

DFS 트리는 그래프에 관련된 자료구조로, 어떤 그래프에 대해 DFS(깊이 우선 탐색)을 적용하여 만들어진 트리를 말한다.

깊이 우선 탐색은 노드가 어떤 순서로 방문되었는지, 어떤 순서로 나가게 되었는지에 따라 노드 번호를 다르게 매길 수 있다.

• Pre-order: 들어간(탐색된) 순서대로 번호를 붙인다.
• Post-order: 나온(탐색이 끝난) 순서대로 번호를 붙인다.

위 그림은 DFS 그래프를 나타낸 것이다.

검은색 숫자는 pre-order를, 빨간색 숫자는 post-order를 나타낸다.

---

다시 돌아와서 그래프에서 Cut Vertex를 어떻게 판별할 것인지 알아보자.

 

주장

1. 루트 노드 r의 자식 노드가 2 이상이다. ⇔  루트 노드 r은 Cut Vertex 이다.

2. non-root v, v의 child u와 그 자손들에게서 v의 조상으로 연결된 Back Edge가 없다. ⇔  v는 Cut Vertex이다.

 

위 주장에서 '⇔' 는 필요충분 조건을 의미한다.

주장을 증명하기 전에 back edge에 대한 설명과 우리가 보는 트리 T에서 Cross Edge가 존재하지 않음을 보이자.

 

참고자료 - 그래프 간선

1. 트리 간선(tree edge) : 스패닝 트리에 포함된 간선

2. 순방향 간선(forward edge) : 스패닝 트레에서 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선

3. 역방향 간선(backward edge) : 스패닝트리에서 자손에서 선조로 연결되는 간선

4. 교차 간선(cross edge) : 위 세가지 분류를 제외한 간선으로 트리에서 선조와 자손 관계가 아닌 정점들간에 연결된 간선을 의미

(출처 : https://bowbowbow.tistory.com/1 )

 

 

예시) DFS TREE

위 트리에서 cross edge가 존재하지 않음을 보이자.

 

증명

• 우리가 현재 보고 있는건 DFS 트리다.
• Cross Edge가 만약 존재한다면, Cross Edge로 연결된 2개의 노드가 있을 것이다. 
• 이 2개의 노드는 먼저 DFS 로 방문한 branch로 연결되어야 하는데, 그러지 않았음.

이는 DFS 알고리즘이 모든 노드를 보지 않았다는 얘기이므로, 알고리즘에 대한 모순이 발생한다.

 

결론

1. dfs 트리에서 cross edge는 존재하지 않는다.

2. dfs 트리에서는 조상과 자손 노드를 잇는 형태만 존재한다.

---

이제Cut vertex를 판별하는 방법을 증명하자.

주장 1.  루트 노드 r의 자식 노드가 2 이상이다. ⇔ 루트 노드 r은 Cut Vertex 이다.

주장 1 증명.

Cut Vertex 정의 (2)번을 사용해 다음을 증명해보자. (필요 충분 조건을 증명해야 하므로 화살표 방향에 따라 총 2번 증명)

• 루트 노드 r의 자식 노드가 2 이상이다. → 루트 노드 r은 Cut Vertex 이다.

 

위에서 증명했듯 dfs tree는 조상과 자손을 잇는 형태뿐으로, cross edge 가 없다.

x에서 y까지 도달하는 방법은 Back Edge를 이용하는 방법이 존재한다.

 

이때 Back Edge는 자손에서 조상까지밖에 연결되지 않는다.

즉 back edge로는 최대 root r 까지밖에 올라가지 못한다.

따라서 어떤 점 x, y 에 대해서 모든 경로가 무조건 최상단 노드 r을 지나가므로, r은 Cut Vertex 이다.

 

마찬가지로 다음을 증명하자.

• 루트 노드 r은 Cut Vertex 이다. → 루트 노드 r의 자식 노드가 2 이상이다.

 

귀류법을 통한 증명

P -> Q 에서 ~Q임을 보여 명제가 참임을 보이자.

 

루트노드 r에서 x으로 도달하기 위해서는 x'을 무조건 거쳐야 하는 x'이 있다고 가정하자.

즉 x'은 r에서 노드 x로 가는 경로에서 서브트리에서 최초로 만나게 되는 노드다.

 

만약 루트 노드 r의 자식 노드가 2보다 작은 1이 되려면, x'의 서브트리에 y가 있어야 한다.

(x'은 r이 최초로 만나는 점이므로, 서브트리의 최상단에 위치해있다.)

 

하지만 그럼 x와 y가 s를 지나지 않고도 연결되는 경로가 생기게 되고, r은 cut vertex가 아니게 되므로,

이는 우리가 증명하려는 명제의 가정에 모순이 발생한다.

따라서 귀류법에 의해 명제가 증명되었다.

 

주장 1번 증명 끝.

---

주장 2. non-root v, v의 child u와 그 자손들에게서 v의 조상으로 연결된 Back Edge가 없다 ⇔ v는 cut vertex이다.

주장 2 증명.

마찬가지로 필요충분 조건이므로, 화살표 방향이 다르게 두 가지 명제를 증명한다.

 

• non-root v, v의 child u와 그 자손들에게서 v의 조상으로 연결된 Back Edge가 없다. → v는 cut vertex이다.

x에서 y로 v를 사용하지 않고 가는 방법이 있을까?

가정에 의해 back edge로 최대한 멀리 가는 길은 v까지밖에 가지 못한다.

따라서 back edge 만 사용해 x에서 y로 가는 건 불가능하다.

이때 다음 사실은 참임이 자명하다.

• x와 y 사이의 경로에 노드 v가 항상 존재한다.

cut vertex 정의 2번에 의해 노드 v는 cut vertex이다. (증명 끝)

 

• v는 cut vertex이다. → non-root v, v의 child u와 그 자손들에게서 v의 조상으로 연결된 Back Edge가 없다.

명제 P - > Q에서 대우 명제 ~Q → ~P 가 참임을 보여 증명하자.

대우 명제에서 위 주장이 두 개로 나뉜다.

 

1) 노드 v에 Child 가 없다. → 노드 v는 Cut vertex가 아니다.

• v를 삭제해도 연결 그래프를 비연결 그래프로 만들지는 못한다. -> 참

 

2) Child 가 하나라도 있으면 자신의 노드나 자손에게 올라가는 back edge가 있다. → cut vertex가 아니다.

• 위 증명에서 자신의 조상까지 back edge가 연결되지 않아서 노드v가 cut vertex가 됨을 보였다. 
• 따라서 조상까지의 Back edge가 존재한다면 cut vertex가 아닌 것 또한 자명하다.

주장 2번 증명 완료.

 

 

 

참고 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=babobigi&logNo=220544340790 

(생각이 다른 부분도 있는 것 같아 내용은 조금 상이할 수 있습니다.)

알고리즘) Cut Vertex