[백준/BOJ C++] 최대 유량 최소 컷 정리 (Max-Flow Min-Cut Algorithm, MFMC)

Reference

[알고리즘] Max-Flow Min-Cut Theorem (최대 유량 최소컷 정리)

Reference

최대 유량 최소 컷(MFMC) 정리

컷이란 그래프의 노드들을 두 개의 덩어리로 나누는 것을 의미한다.

(무향 그래프에서는 두 그룹 사이에 어떠한 간선도 존재하지 않아야 하지만, 유향 그래프의 경우에는 Sink에서 Sour로 이동이 간으해도 Sour에서 Sink로 이동이 불가능하기만 하다면 역시 컷에 해당된다.)

이때, 그래프를 나누기 위해 간선을 끊으면서 그 간선의 비용을 계산한다고 할때, 컷의 비용이 최소가 되도록 자르는 것을 최소 컷이라고 한다.

그런데 Min-Cut의 비용은 두 그래프의 사이에 흐를 수 있는 최대 유량과 같다.

즉, 최대유량 최소 컷 정리란, 최대 유량의 양과 최소 컷의 비용이 동일함을 활용하는 정리이다.

MFMC 활용

Min-cut 계산

이를 활용하는 대표적인 방법은, 최대 유량 알고리즘을 이용하여 최소 컷 정리를 푸는 것이다.

유향 그래프에서 Min-cut 그래프 찾기

우선 최대유량을 흘리고서 추가로 유량을 흘린다고 해보자.

어떤 노드는 접근이 가능하고 어떤 노드는 접근이 불가능하다.

초록색은 접근가능, 주황색은 접근 불가능

이때 어떤 간선 $(u, v)$에서 $u$까지는 접근가능하지만 $v$까지 접근이 불가능 할경우 Min-cut간선에 포함된다.