跳至內容

最大流最小割定理

維基百科,自由的百科全書

最大流最小割定理最優化理論的定理。根據該定理,在一個網絡流中,從源點匯點的最大的流量,等於它的最小割中每一條邊的容量之和。「割」指的是一種的集合,如果移除這個集合的全部邊,就會斷開源點和匯點的連接。

最大流最小割定理線性規劃中的對偶問題的一種特殊情況,並且可以用來推導門格爾定理König–Egerváry定理[1]

定義

最大流和最小割定理是圖論的一部分,因此為了準確定義,我們需要先定義圖、流、割,然後再定義這個定理。

為一個有向圖,其中有一個起源點 和一個超匯點 ,代表 是所有流的源頭, 是所有流的終點。這個圖的每一條邊都有一個容量 c : ER+,記做 或者 ,代表着能通過邊 的最大流量。

最大流

定義: 流量代表一種映射 ,記做 或者 ,代表通過邊 的流量。每一條邊所通過的流有以下兩個限定條件:

  1. 流量限制 也就是說,一條邊上的流量不可以超過它的容量。
  2. 流量守恆 也就是說,除了源點和匯點以外,進入一個節點的流量等於流出這個節點的流量,節點內不能保存流。

規定在一個圖中,流的值是

也就是說,一個圖的流是自其源點流出的流量之和,也是向其匯點流入的流量之和。或者說,由源點向匯點移動多少內容,這個圖的流就是多少。

最大流問題計算的最大值,即從的最大流量。

最小割

定義: s-t割  將圖 完全劃分為兩部分,使得 也就是一側有源,一側有匯。割集 也就是說,一條邊當且僅當騎在這個劃分方法上,一個節點位於劃分出來的源側,另一個位於匯側,那麼它包含在 里。因此如果  的割集是空集,或者我們把一個割集裡的邊全都從圖中拿走,則 。通俗地說,割集就是一個圖的斷面,而割則是劃分斷面的方法。

規定在一個圖中,s-t割的容量

其中當 時,, 否則為

通俗地說,割的容量就是斷面中所有邊的總容量。

最小 s-t 割問題: 計算  的最小值。即找到一種割法,使割的容量最小。也就是說,找到通過能力最弱的斷面。

主定理

可以證明一切流都不能超過任何s-t割,所以經過圖的最大流就是圖的最小割。我們直觀上就可以知道,通過能力最弱的斷面就是整個網絡的最大流量。這個理論把最大流問題和最小割問題聯繫了起來。

線性規劃公式

最大流最小割問題可以被看做為一對線性規劃對偶問題。[2]

Max-flow (Primal)

Min-cut (Dual)

variables

[a variable per edge]

[a variable per edge]

[a variable per non-terminal node]

objective

maximize

[max total flow from source]

minimize

[min total capacity of edges in cut]

constraints

subject to

[a constraint per edge and a constraint per non-terminal node]

subject to

[a constraint per edge]

sign constraints

最大流的線性規劃公式是容易理解的,對於最小割的線性規劃公式的理解如下:

最小化目標是使在割中的邊最小。

下列限制保證了這些變量可以確保一個合法的割。

  • 限制 (即 ) 確保了對兩個非源點或匯點 u,v, 如果uS中 且 vT中, 那麼邊 (u,v)一定會被記在割中 ()。
  • 限制 (即 ) 確保了如果 vT 中, 那麼邊 (s,v) 一定會被記在割中。
  • 限制 (即 ) 確保了 uS 中, 那麼邊 (u,t) 一定會被記在割中。

需要注意的是,這是一個最小化問題,我們不需要確保一條邊不在割里,我們只要保證每條應當在割里的邊被計算了。

注意到在給定的 s-t 割  中,如果 那麼 並且 0 反之。 所以 應該等於 1 並且 應該等於0。由線性規劃中的強對偶定理推得最大流最小割問題中的等式,也就是說如果原問題有一個最優解 x*,則對應問題也有一個最優解 y* ,並且兩個解相等。

舉例

一個流量等於s-t 割的容量的流網絡

上圖是一個網絡,上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點, 從而形成了一個割集包含圖中虛線的 s-t 割,並且其容量為 7,與流量相同。故由大流最小割定理知,前述的流與 s-t 割皆達到流量及容量的極值。

應用

廣義最大流最小割定理

額外規定映射 為點的容量,記做 c(v),使得一個流 f 不只要滿足邊的流量限制與流量守恆,還要滿足點的流量限制,即

換句話說,流過 v 點的總流量不能超過 v 的容量 c(v)。一個 s-t 割 的定義為一個包含一些點和邊的集合,滿足與任一條由 s 到 t 的路徑皆不互斥。並且 s-t 割的容量 定義成所有點和邊的容量總和。

在此定義之下,廣義最大流最小割定理的敘仍為流量的最大值等於所有 s-t 割的容量最小值。

門格爾定理

不共邊路徑問題為給定無向圖 及兩頂點 s、t,求從 s 到 t 彼此沒有共同邊的路徑數量的最大值。

門格爾定理的敘述為從 s 到 t 彼此沒有共同邊的路徑數量的最大值等於在所有 G 的 s-t 割(以原本的定義)中,頂點分別在不同集合的邊數的最小值。

計畫選擇問題

計畫選擇問題的網絡型態

計畫選擇問題敘述如下:當下有 n 個計畫 可以被實施、m 種設備 可以被購買,要執行計畫必須擁有該計畫要求的設備,執行計畫 可獲得 的收益,但購買設備 要支付 的費用。如何選擇執行計畫並購買所需設備以獲得淨利的最大值?

設 P 為被執行的計畫的集合,Q 為所購買的設備,則問題變成求最大值

注意到 與 P、Q 的選擇無關,故只需求後兩項和的最小值,即

現在考慮一個網絡,起源點 s 連接到 n 個點 ,邊的容量分別為 ,超匯點 t 連接到 m 個點 ,邊的容量分別為 ,若執行任務 需購買設備 ,則在 之間連上一條容量為無限大的邊,若不需購買設備,則不連上邊。則 對應到一個 s-t 割的容量,其中的兩個集合是要執行的計畫與要購買的設備和它的餘集,也就是

在此,。於是,原問題轉成求該圖的最大流問題,並且可以藉由各種算法求得其極值。

以下給出一個計畫選擇問題的例子,右圖是該問題對應到的網絡。

計畫收入 r(pi)

設備價格 c(qj)

備註
1 100 200

執行計畫 p1 須購買設備 q1q2

2 200 100

執行計畫 p2 須購買設備 q2

3 150 50

執行計畫 p3 須購買設備 q3

該網絡的最小 s-t 割是選擇計畫 p2p3 與設備 q2q3,容量為 250。三個計劃的總收益是 450,因此最大淨利為 450 − 250 = 200。

以上解法可以理解為將計畫所給予的收益流過所需設備,如果無法流滿設備至 t 的邊,代表執行計畫不合成本,最小割將選擇穿過 s 到計畫的邊而非穿過設備到 t 的邊。

影像分割問題

Each black node denotes a pixel.

設原圖有 n 像素,想要把該圖分割為前景和背景,並且將 i 像素歸類為前景有效益  fi,歸類為背景有效益  bi,但是若 i、j 像素相鄰且被歸類為不同塊,則會減少 pij 的效益。求將該圖分割為前後景的最有效益方法。

令 P 為前景的集合,Q 為背景的集合,於是問題轉化成求最大值

因為  fi bi 的總合是與 P、Q的選取無關,因此等價於求以下最小值

以上的最小值問題可以被描述為一個網絡的最小割問題,其中該網絡如右圖,以橘點為起源點;紫點為超匯點。各個像素被描述為網絡的頂點,起源點至第 i 個像素連上一條容量為  fi有向邊;第 i 個像素至超匯點連上一條容量為 bi有向邊。相鄰的像素 i、j 之間連上來回兩條容量為 pij有向邊。則一個 s-t 割代表一種將部分像素歸類為前景 P、其餘歸類為背景 Q 的安排。

歷史

最大流最小割問題最早在1956年被P. Elias, A. Feinstein,和 C.E. Shannon 證明[3], 並且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年證明了該定理[3]

證明

同之前的設定,G = (V, E) 是一個網絡(有向圖) ,s 點和 t 點分別為 G 的起源點和超匯點。

將所有流考慮成一個歐式空間有界子集,滿足流量限制與流量守恆,而流量是一個連續函數,因此有極大值 |f| 。

設 f 達到最大流,令 (Gf ) 是 f 的殘留網絡,定義

  1. A:在 (Gf ) 中可以從 s 出發到達的點
  2. Ac:A 以外的點,即 V − A

換句話說,v∈A 若且唯若 s 可以流出更多流量到 v。

我們宣稱 ,其中該 s-t 割的容量定義為

.

由於 的大小等於所有流出集合 A 的流量總和減所有流入集合 A 的流量總和,故 ,並且等號成立若且唯若

  • 所有從 A 流向 Ac 的邊流量均已達飽和。
  • 所有從 Ac 流向 A 的邊流量均為 0。

我們用反證法分別證明以上兩點:

  • 假設存在從 A 流向 Ac 的邊 並未達到飽和,即 。因此,可以從 x 流更的流量到 y,(x,y) 是 Gf 的一條邊。由 x∈A 知 Gf 圖中有一條中的路徑從 s 到 x,其中只經過 A 中的點, 所以 y∈A,產生矛盾。是故所有從 A 流向 Ac 的邊流量均已達飽和。
  • 假設存在從 Ac 流向 A 的邊 其流量不為 0,即 。因此,可以從 y 流更的流量到 x,(x,y) 是 Gf 的一條邊。由 x∈A 知 Gf 圖中有一條中的路徑從 s 到 x,其中只經過 A 中的點, 所以 y∈A,產生矛盾。是故所有從 Ac 流向 A 的邊流量均為 0。

於是,聲稱得證。

由於流量恆不超過容量,|f| 是容量的下界,所以 是容量的最小值,由聲稱知,最大流最小割定理得證。

參見

參考文獻

  1. ^ Dantzig, G.B.; Fulkerson, D.R. On the max-flow min-cut theorem of networks (PDF). RAND corporation. 9 September 1964: 13 [10 January 2018]. (原始內容存檔 (PDF)於2018-05-05). 
  2. ^ Trevisan, Luca. Lecture 15 from CS261: Optimization (PDF). (原始內容存檔 (PDF)於2019-11-01). 
  3. ^ 3.0 3.1 P. Elias, A. Feinstein, and C. E. Shannon, A note on the maximum flow through a network, IRE. Transactions on Information Theory, 2, 4 (1956), 117–119