Max-flow min-cut theorem - 최대 유량 최소 컷 정리

이 글의 목차

인터랙티브

증가 경로, 잔여 간선, 최소 컷

증가자동초기화

유량 네트워크 (유량 / 용량)

증가 경로최소 컷유량

증가를 눌러 첫 번째 증가 경로를 찾으세요.

최대 유량 = 최소 컷

유량과 컷이 만나는 이유

유량은 용량이 제한된 유향 간선을 따라 시작점에서 도착점으로 보낼 수 있는 양을 나타냅니다. 컷은 두 정점을 가르는 병목을 나타냅니다. 최대 유량 최소 컷 정리는 두 관점이 같은 한계값을 찾아낸다고 말합니다.

서로 다른 시작점 $s$와 도착점 $t$를 가진 유한 유향 네트워크 $G=(V,E)$를 생각합시다. 각 간선 $e$의 용량 $c_e$는 유한하고 음이 아닙니다. 실현 가능한 유량은 각 간선에 $f_e$를 할당하여

$$0\leq f_e\leq c_e$$

를 만족하고, $s,t$ 이외의 모든 정점에서 유입량과 유출량이 같도록 한 것입니다. 유량의 값 $|f|$는 $s$에서 나가는 순유량이며, $t$로 들어가는 순유량과 같습니다.

$s$–$t$ 컷은 $V=S\mathbin{\dot\cup}T$, $s\in S$, $t\in T$인 분할입니다. 용량은 원래 간선 중 $S$에서 $T$로 향하는 간선만 합산합니다.

$$c(S,T)=\sum_{e=(u,v)\in E:\,u\in S,\ v\in T}c_e.$$

정리는 실현 가능한 유량의 최댓값이 모든 $s$–$t$ 컷 용량의 최솟값과 같다는 내용입니다.

모든 컷은 모든 유량의 상한

임의의 실현 가능한 유량과 컷에 대해 $S$에 속한 정점들의 순유출량을 합하면 내부 간선의 유량은 상쇄되어

$$\begin{aligned} |f| &= \sum_{e=(u,v):\,u\in S,\,v\in T}f_e\\ &\quad-\sum_{e=(u,v):\,u\in T,\,v\in S}f_e \end{aligned}$$

를 얻습니다. 두 번째 합은 음이 아니고, 첫 번째 합의 각 항은 해당 간선의 용량 이하입니다. 따라서 $|f|\leq c(S,T)$이며 모든 유량과 컷에 성립합니다.

잔여 도달 가능성으로 등호 증명

최대 유량은 존재합니다. 영 유량은 실현 가능하고, 실현 가능한 유량들의 집합은 유한 차원 공간에서 닫혀 있고 유계이기 때문입니다. 원래 간선 $u\to v$마다 잔여 그래프에는 용량 $c_e-f_e$인 정방향 간선과 용량 $f_e$인 역방향 간선이 있습니다. 역방향 간선은 해당 원래 간선에 이미 보낸 유량을 취소할 수 있음을 뜻합니다.

양의 잔여 용량 간선만 따라 $s$에서 도달 가능한 정점 집합을 $S$, 나머지를 $T=V\setminus S$라 합시다. $t$가 $S$에 있다면 잔여 경로의 양의 병목만큼 유량을 늘릴 수 있으므로 최대 유량이라는 가정에 모순입니다. 따라서 $S$에서 $T$로 향하는 양의 잔여 용량 간선은 없습니다. 이에 따라 원래 간선 중 $S$에서 $T$로 향하는 간선은 모두 포화되고, $T$에서 $S$로 향하는 간선에는 유량이 없습니다(그렇지 않으면 역방향 잔여 간선이 컷을 넘습니다). 앞의 컷 등식에서 $|f|=c(S,T)$를 얻습니다. 모든 유량이 모든 컷 용량 이하이므로 이 유량은 최대이고 이 컷은 최소입니다.

작은 최적성 인증서

간선과 용량이 $s\to a:3$, $s\to b:2$, $a\to t:2$, $a\to b:1$, $b\to t:3$인 네트워크를 보겠습니다. 같은 순서로 유량 $3,2,2,1,3$을 보내면 $a,b$에서 유량 보존이 성립하고 전체 유량값은 5입니다. 컷 $S=\{s\}$, $T=\{a,b,t\}$의 용량도 $3+2=5$입니다. 유량 5와 컷 용량 5가 일치하므로 더 큰 유량이나 더 작은 컷은 있을 수 없습니다.

핵심: 유량은 가능한 운송량이고 컷은 병목의 용량입니다. 잔여 네트워크의 도달 가능성이 두 값이 같음을 보이는 컷을 구성합니다.