MCMF(min cut max flow)

 

어떤 그래프가 있고 해당 그래프의 간선에 가중치가 있다고 해봅시다. 이 그래프에 대해 다음 두 문제를 생각해 봅시다. 

 

그래프가 하나 주어집니다. 주어진 그래프에는 $N$개의 정점과 $M$개의 파이프가 있습니다. 각 파이프는 물을 한쪽 방향으로만 흘릴 수 있습니다. 각 파이프의 흐를 수 있는 양은 다릅니다. 시작 정점과 끝 정점이 주어졌을 때, 시작 정점에서 끝 정점으로 최대한 많은 양의 물을 보내고자 합니다. 얼마나 보낼 수 있습니까?

 

그래프가 하나 주어집니다. 주어진 그래프에는 $N$개의 정점과 $M$개의 간선이 있습니다. 각 간선은 한쪽 방향으로만 지날 수 있습니다. 각 간선에는 해당 간선을 끊는 데 드는 비용이 있고 이 비용은 다릅니다. 시작 정점과 끝 정점이 주어졌을 때, 최소한의 비용으로 간선들을 끊어서 시작 정점에서 끝 정점으로 이동할 수 없게 하려고 합니다. 얼마의 비용이 드나요?

 

1번 문제에서 가중치는 흘릴 수 있는 물의 양입니다. 2번 문제에서 가중치는 해당 간선을 끊는데 드는 비용입니다.

첫번째 문제를 max flow 문제, 두번째 문제를 min cut 문제라고 부릅니다. 이 두 문제의 답이 같다는 것을 증명할 것입니다.

 

min cut > max flow

min cut에 해당하는 간선을 자르면 시작 정점에서 무슨 짓을 해도 끝 정점으로 갈 수 없습니다.

 

그 말은 저희가 아무리 max flow에 해당하는 길을 잘 찾는다 하더라고 반드시 min cut에 해당하는 길을 지날 수 밖에 없다는 뜻입니다. 이 길에 해당하는 모든 가중치의 합이 min cut이므로 min cut > max flow일 수 밖에 없습니다.

 

max flow > min cut

저희가 아주 열심히 해서 max flow에 해당하는 모든 선을 찾고 해당 길을 통해 물을 전부 흘렸다 합시다. 그렇다면 어떤 간선은 자신이 흘릴 수 있는 모든 유랑을 전부 사용했을 것입니다. 해당 간선들을 전부 찾아봅시다.

 

그렇다면 그 간선들만 전부 잘라도 시작 정점에서 끝 정점까지 갈 수 없습니다. 즉, max flow > min cut입니다.

 

max flow > min cut이면서 max flow < min cut이기 때문에 max flow = min cut입니다.

사실 여기에는 논리적으로 말이 안되는 부분이 있습니다. 하지만 저희의 목적은 이것을 엄밀히 증명을 하는 것은 아닙니다. max flow = min cut임을 최대한 직관적으로 이해하는 것이 목적이죠. 그렇기 때문에 여기까지만 이해를 하고 넘어가겠습니다. 자세한 증명은 다른 블로그에도 잘 나와있으니 해당 블로그를 보시는 것을 추천합니다. "min cut max flow 증명"라고 검색하시면 됩니다.