저번 MCMF 증명 글도 그렇고 괜히 재미없는 글로 도배하는 거 같아 죄송하지만, 블로그를 팔 때까지만 참아주세용


오늘은 MFMC (Maximum flow, minimum cut) 정리를 설명 해 볼 거예요. 워낙 유명한 정리라 플로우를 접해보셨다면 당연히 아시겠지만, 임의의 유량 그래프의 최대 유량은 최소 컷과 동일하다는 정리입니다. 여기서 유량 그래프의 컷은 플로우를 하나도 흘리지 못하게 만들기 위해 제거해야 하는 간선들의 가중치의 합의 최소를 뜻합니다.


한 눈으로 보면 전혀 관계없어 보이는 두 개념이 왜 동일할까요? 엄밀하게 증명하기엔 어렵고 귀찮으니, 간단하게 어떤 느낌으로 성립하는 정리인지 알아봅시다.


다음 유량 그래프를 살펴봅시다. (유량의 용량은 써놓지 않았지만, 유한한 용량으로 제한된 간선들이라고 가정해 주세요).



하이라이트 된 간선들은 이 그래프의 최대 유량, 즉 maximum flow에 속하는 간선들입니다. 


하지만 왜 이 최대 유량을 늘릴 수 없는 걸까요?

여기서 어떤 개념을 소개하겠습니다. 실제로 그래프 이론에서 쓰이는 개념이 아님을 주의해 주세요.


다음 물병이 왜 물을 더 빨리 붓지 못하는 걸까요?

바로 좁은 입구: 이 물병의 보틀넥 (bottleneck) 때문입니다. 아무리 물병의 보틀넥 전과 후의 지름이 더 넓더라도 보틀넥에 막혀 실제로 부어지는 양은 보틀넥에 인하여 상한이 정해진다는 거죠.


이를 유량 그래프로 변환해 보자면:


물병의 지름을 어떠한 간선의 유량 용량으로 생각한다면 당연히 이 유량 그래프의 최대 플로우는 보틀넥과 동일합니다. 최소 지름보다 물이 더 많이 흘러나올 수 없으니까요.


비슷한 원리로, 어떠한 유량 그래프의 보틀넥을 찾을수만 있다면, 그 보틀넥은 최대 유량과 동일하겠죠.


그럼, 아까 살펴본 그래프에서 보틀넥은 어떻게 생겼을까요?


임의의 소스와 연결된 정점들의 부분집합과, 싱크와 연결된 정점들의 부분집합들을 잡았을때 이를 연결해주는 간선들의 집합들 중 간선들의 집합의 가중치의 합을 최소화하는 간선들이 보틀넥이란걸 볼 수 있습니다. 



어! 잠깐! 이 설명은 아까 최소 컷의 설명과 정확히 동일합니다. 이러한 논리로 최소 컷과 최대 유량은 동일하다는 사실을 관찰 할 수 있습니다.


물론 이게 엄밀한 증명의 역할을 하진 않습니다. 그저, PS를 할 때 쓸거라는 아주 중요한 필요조건이 주어졌기 때문에 증명을 건너뛸 수 있는거죠.