最小割最大流定理的內容:
對于一個網路流圖 $G=(V,E)$，其中有源點和匯點，那么下面三個條件是等價的：
- 流$f$是圖$G$的最大流
- 殘量網路$G_f$不存在增廣路
- 對于$G$的某一個割$(S,T)$，此時流的流量等于其容量
證明如下:
首先證明$1\rightarrow2$:
正確性顯然,
然后證明$2\rightarrow3$:
假設殘留網路$G_f$不存在增廣路，所以在殘留網路$G_f$中不存在路徑從$s$到達$t$，我們定義$S$集合為：當前殘留網路中$s$能夠到達的點，同時定義$T=V-S$，此時$(S,T)$構成一個割$(S,T)$，且對于任意的$u\in S,v\in T$，邊$(u,v)$必定滿流，若邊$(u,v)$不滿流，則殘量網路中必定存在邊$(u,v)$，所以$s$可以到達$v$，與$v$屬于$T$矛盾，因此有$$f(S,T)=\Sigma f(u,v)=\Sigma c(u,v)=C(s,t)$$
最后證明$3\rightarrow1$:
割的容量是流量的上界, 正確性顯然.
于是, 圖的最大流的流量等于最小割的容量.
殘量網路的性質:
- $s$與$t$一定不在同一$SCC$里
- 對于某條滿流邊$(u,v)$, 若$u$與$s$在同一$SCC$,$v$與$t$在同一$SCC$, 則它必定會出現在最小割中.
- 對于某條滿流邊$(u,v)$, 若$u$與$v$不在同一$SCC$, 則它可能出現在最小割中.
結論1非常顯然, 最大流的話$s$和$t$直接不連通更不要說在同一$SCC$里了.
結論2的話, 如果將一條滿足該限制的邊容量增大, 那么$s\rightarrow t$重新連通, 于是就會增加最大流的流量, 也相當于增加了最小割的容量. 所以這條邊必定會出現在最小割中.
結論3的話, 我們把$SCC$縮到一個點里, 得到的新圖就只有滿足條件的滿流邊了. 縮點后的任意一個割顯然就對應著原圖的一個割, 所以這些滿流邊都可以出現在最小割中.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/80723.html
標籤：C++
上一篇：第四章 復合型別
下一篇：QString轉char *