本文使用 Zhihu On VSCode 創作併發布

嘗試以通俗語言解釋最大流最小割定理。如有錯誤還請指正。

前置知識

網路

：指具有兩個不同的特定頂點（

發點

和

收點

）的加權連通圖，記為

。其中

為

容量函式

：圖中某條邊到某個值（容量，或者通俗地說成“最大邊權”）的對映。

對某條邊

，其

容量

記為

，也就是這條邊的權值最大為

。

若

容量函式

的函式值非負，則稱該網路為

容量網路

。

流

：對一個容量網路，如果存在

滿足：對圖中的任意一條邊有

，並且對圖中除了發點和收點之外的任意頂點都有

，則稱

是

中從

到

的流。通俗地說，就是我基於原圖構造一個有向的新圖，這個有向新圖滿足：除了發點收點之外的任意點的出邊權值和與入邊權值和相等，並且這個新圖的每條邊權值非負且小於等於原來圖中對的權值。

流量

：

稱為流

的流量（發點出邊權值減去入邊權值稱為流量）。

中流量最大的流稱為

最大流

。

截邊集

：對容量網路，把

中的點分成兩個集合，並且保證

與

不在同一個集合中，且集合中的點相互可達（連通）。如果一條邊的兩個端點屬於不同的集合，則這條邊稱為“截邊”，所有這樣的邊的集合稱為截邊集，記為集合

。其實截邊集相當於阻斷

中所有

之間的路。

在容量網路中，對於任意的點的劃分，具有最小容量的截邊集稱為

最小截(minimum cut set)

，或者

最小割

。

最大流最小割定理

在任何容量網路

中，最大流量等於最小截容量。

大致的證明思路

首先形象地理解一下：把這個流想象成水流。流量就相當於質量守恆（？）。那我把這些流徹底阻斷（也就是選取一個截邊集），阻斷的時候的流量肯定就等於初始的流量。事實上這也是容易證明的，藉助圖論中最基本的整個圖中出度之和等於入度之和即可。

那麼顯然我們有流量小於等於截邊容量，因為每條邊流過的流量是小於初始容量的。更進一步地，由截邊集選取的任意性，流量一定小於等於最小截的容量。只需要證明流量可以取到這個值。

顯然在容量網路中最大流存在。如果最大流流量嚴格小於某個截邊集的容量，則在截邊集之中至少存在一條邊“水沒灌滿”，也就是說流量小於截邊集容量，設這條邊為

。（好吧，這裡其實涉及到流向的方向問題，可以把方向不對的邊當成負的理解）。由截邊集定義（連通性）可以找到一條從發點到收點且經過這條“沒灌滿”的邊的路。我們把這條路上的所有邊的容量都改變一個值，使得這條邊“灌滿”（如果這樣做使得流量增大，則這條截邊集裡的邊是“正向”的，否則是“負向”的。對於負的邊我們將它變成正的）。但是由於反證假設的存在，這一過程是無法完成的：這個流已經是最大流了，它的容量不能變的更大了——也就是說這條路上有一條邊已經“滿”了，設其為

，並且

。我們把截邊集中的

換成

，仍然可以得到一個截邊集。繼續這種操作，直到無法繼續的時候，我們就得到了一個截邊集，其截邊的容量之和等於最大流流量，也就是最大流流量大於等於最小截。

綜上，最大流量=最小截容量。