최소 컷(Minimum Cut)

---

목록

1. 최소 컷(Minimum Cut)이란?

2. Max-flow Min-cut theorem

3. Min-cut 문제임을 알아채는 방법

---

1. 최소 컷(Minimum Cut)이란?

네트워크 플로우에 대해서 공부하다 보면 이제 최소 컷(Minimum Cut)이라는 개념이 등장하기 시작한다.

최소 컷(Minimum Cut)이 무엇일까?

아래와 같은 그래프가 있다고 생각해보자.

이와 같은 그래프가 있을 때, 그래프를 2개의 서로 다른 집합으로 나누고 싶다.

이렇게 자르면 A만 있는 그래프와, B, C, D, E가 있는 그래프 두가지로 나뉘게 된다.

이렇게 그래프를 2개의 서로 다른 집합으로 나누는 것을 Cut이라 한다.

그리고 두 집합을 A와 B라고 했을 때, 한 쪽 끝은 A에 다른 한 쪽 끝은 B에 있는 간선을 Cut-Set이라고 한다.

이때 가중치가 없다면, 간선의 개수를 가장 적게 하여 자르는 것이 Minimum Cut이고

가중치가 존재한다면, 간선의 가중치의 합을 가장 적게 하여 자르는 것이 Minimum Cut이다.

이와 같이 B-C와 B-E를 cut한다면 Minimum Cut이 될 수 없다는 의미이고(A-C 혹은 D-C 혹은 C-E를 자르는게 Minimum Cut이다.)

가중치가 다음과 같이 존재하게 된다면 Minimum Cut은 B-C, B-E를 자른 것이다.

2. Max-flow Min-cut Theorem

네트워크 플로우에서 Min-cut은 Max-flow와 같다.

결국 Min-cut에 해당하는 Problem을 만났을 땐, 최대 유량 문제로 접근하여야 한다.

이 블로그에서는 결론적인 내용만 이야기 하지만, 더 자세히 알고 싶으면 아래 사이트를 이용해보자.

Wiki :: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

---

한국어 :: http://godkad.blog.me/220693301763

(위의 블로그에서 증명의 부분을 발췌하였습니다. 문제가 될 시 삭제 조치 하도록 하겠습니다.)

[증명]

- 모든 flow는 어떤 Cut을 설정하든 그 Cut의 Capacity를 넘을 수 없다.

- 따라서 만약 어떤 Cut의 Capacity와 동일한 flow가 있다면 최대 flow가 된다.

- 모든 flow는 net flow across cut과 동일한 크기를 갖는다고 했다.

- 포드 포커슨 알고리즘에서 augmenting path가 더 이상 존재하지 않기 위해서는

정점에서 연결된 간선들이 용량이 다 찼거나, 텅 비어있는 경우라고 했었다.

- 따라서 augmenting path가 더 이상 없는 경우의 유량은 최대 유량이다.

 

- 그림처럼 s를 시작점으로 해서 용량이 다 차지 않은 간선과, 역방향으로 흘려보낼 수

있는 간선만으로 도달 가능한 정점들로만 집합 A를 구성하면 집합 A에서 B로 흘러가는

간선은 모두 꽉 찼거나 역방향으로 흘려보낼 수 없다.

- 따라서 A에서 B로 흘러가는 유량은 A에서 B로 흘러가는 용량의 합이 된다.

즉, 최대 유량 = 용량이 되는 것이다.

여기에서 더 작은 용량이 존재한다면 최대 유량보다 작으므로

용량이 최대 유량보다 같거나 크다라는 가정에 위배되므로 해당 Cut이 최소 Cut이 된다.

따라서 최대 유량은 최소 컷과 동일한 값을 가지게 된다.

---

결국 바로 위의 그림에서 Min-cut은 S(source) -> T(sink)로 가지 못하도록 제거해야 하는 

Edge Capacity합의 최솟값을 의미한다.(결국 최대 유량을 구하라는 의미와 동치이다.)

3. Min-cut 문제임을 알아채는 방법

간단하다. 문제에서 S->T로 가는 것을 막으려 하는 늬앙스가 보인다면 우선적으로 Min-cut을 생각해보아야 한다.

그리고 이 문제가 네트워크 플로우 문제인지 확인하고, Min-cut 문제임이 확인된다면

최대 유량을 구하는 방식으로 접근해보자.

최소 컷 문제 :: http://www.crocus.co.kr/search/%EC%B5%9C%EC%86%8C%20%EC%BB%B7