Min Cut과 Max Flow와의 관계

Link to original note: [[Flow Graph]]

Cut은 Flow Graph에서 정점 s에서 t까지 가는 유량이 없도록 어떤 간선들을 자를 때, 그 간선들의 집합을 의미한다.  

이때 Min Cut이란 간선 용량의 합이 최소가 되는 집합을 의미한다.   

세줄 요약:
1) 먼저 임의의 $cut$에 의한 간선 용량의 합($|cut|$)은 $flow$의 합($|flow|$)보다 항상 크기 때문에 모든 $|cut|$은 $max(|flow|)$ 이상이다.
2) 임의의 Max Flow를 흘린 다음의 그래프에서, 유량을 조금 더 흘릴 수 있는 Residual graph에서, src로부터 도달할 수 있는 정점들의 집합을 $S$라 할 때, $S$에서 $V \setminus S$까지 가는 모든 간선을 끊는 것은 valid한 cut이다.
3) $S \rightarrow V \setminus S$ 간선은 모두 사용되고, $V \setminus S \rightarrow S$ 간선은 사용되지 않음이 보장되어 이때의 $|cut|$은 $max(|flow|)$와 동일하고, 이것이 $min(|cut|)$이다. 

먼저 모든 flow $f$에 대하여 모든 cut $C$와의 관계를 알아보자.
$|f| \le |C|$다.

임의의 cut $C$에 대해서 나뉘어진 정점 집합을 $A$($s$ 포함), $B$($t$ 포함)이라 할 때 
$s \rightarrow t$ flow는$A \rightarrow B$ flow의 크기와 똑같고, 이는 $A ]rightarrow B$ 용량보다 작거나 같으므로
$|f| \le |C|$가 증명된다.

따라서 $max |f| \le min |C|$ 다.

이제 $max |f| = min |C|$ 가 되는 C의 존재성을 증명하자.
임의의 max flow를 흘린 후, (= 모든 augmenting path)를 찾은 후 Residual Graph를 생각해보자. (어떤 간선의 용량이 남아있는 경우  + 역간선의 용량이 남아 있는 경우(즉 유량 > 0) => e.g $f(u,v) < c(u,v)$ ). 한마디로 요약하면, 기존그래프의 간선과 그 역간선에 대하여 거기서 유량을 더 흘릴 수 있으면 Residual graph의 간선이다.

Residual Graph에서 $s$에서 도달 가능한 정점의 집합을 $S$라고 할 때
$S \rightarrow V \setminus S$로 향하는 간선은 없다. (만약 있다면 $S$를 확장시킬 수 있으므로 모순)

따라서 기존 그래프에서 모든 $V \setminus S \rightarrow S$ 간선만 우리의 관심사다.

$V \setminus S$에 속한 정점을 $v$, $S$에 속한 정점을 $u$라고 할 때

1) $v \rightarrow u$가 기존 그래프의 역간선일 경우
$u \rightarrow v$ 가 Residual graph에서 존재하면 안되므로, $u \rightarrow v$ 의 여유 용량은 $0$이다, 즉 $f(u,v) = c(u,v)$

2) $v \rightarrow u$ 가 기존 그래프의 정간선일 경우
$u \rightarrow v$ 가 Residual graph에서 존재하면 안되므로, $v \rightarrow u$ 의 유량은 $0$이다. $f(v,u) = 0$

이때 max flow인 $|f|$는 기존 그래프에서 계산하면, 
$|f| = \sum_{S \rightarrow V \setminus S}{f(u,v)} - \sum_{V \setminus S \rightarrow S}{f(v,u)}$가 되는데, 
이는 결국 위 1), 2)에 의하여 

$|f| = \sum_{S \rightarrow V \setminus S}{C(u,v)} - \sum_{V \setminus S \rightarrow S}{0}  =  \sum_{S \rightarrow V\setminus S}{C(u,v)}$가 된다.

 

따라서 max_flow는 $S \rightarrow V \setminus S$ 간선들의 용량 합과 같다.

$S \rightarrow V \setminus S$의 간선을 모두 끊으면 $S$에서 $V \setminus S$까지 가는 정방향 유량 간선이 없으므로 ($u,v: \ S \rightarrow V \setminus S$)는 valid한 Cut이다. 

 

따라서 $max(|flow|) \le  min(|cut|)$이고, $|cut|$이 $max(|flow|)$와 같은 $cut$의 존재성을 증명하였으므로 

모든 유량 그래프에서 Min Cut의 크기와 Max Flow의 크기는 같다.