動機
一個網絡即使從源點流出的總容量足夠大,也可能無法把這麼多流量送到匯點。在兩者之間,總有一些弧構成瓶頸。找到一個較大的可行流,給出的是可運輸量的下界;找到一個較小的分隔割,給出的是上界。當兩個界相等時,最優性即得證。
真正的困難在於,早先的路徑選擇有時需要被撤銷。殘餘網絡既記錄尚未使用的容量,也記錄取消已送出流量的可能性。這是沿增廣路徑反轉匹配邊這一做法在有向圖中的類比。若忽略這些取消用的弧,算法可能停在一個遠非最大的流上。
定義
定義 7.1.1
(流及其流值)
一個有限有向網絡具有互不相同的源點與匯點 ,沒有自環,並且每條弧 上有非負容量 。方向相反的弧容許同時存在,且彼此視為不同的弧。可行流為每條弧指定 ,並在除 以外的每個頂點處滿足守恆:流入的總流量等於流出的總流量。其流值為
源–匯割是全體頂點的一個劃分 ,滿足 。其容量為 ;反方向的弧不計入此和。
定義 7.1.2
(殘餘弧保留其原始標籤)
對每條原始弧 ,其正向殘餘弧方向為 ,容量為 ;其反向殘餘弧方向為 ,容量為 。搜尋時只保留容量為正的殘餘弧。每條殘餘弧都記住對應的原始弧,以及應當增加還是減少其流量。因此不同的殘餘弧可能具有相同的端點,當原始網絡含有方向相反的弧時尤其如此。
殘餘增廣路徑是一條從 到 的簡單有向路徑。其瓶頸是路徑上各弧殘餘容量的最小值。沿正向弧將原始流量增加該瓶頸值、沿反向弧將原始流量減少該瓶頸值,稱為增廣。原始容量與原始流量始終屬於各自的原始有向弧;反向殘餘弧只是一條操作指令,並不是新裝設的運輸弧。
定理/命題
定理 7.1.3
(每個割都為每個可行流提供上界)
對每個可行流和每個源–匯割,
等號成立當且僅當從 到 的每條原始弧都已飽和,且從 到 的每條原始弧上的流量為零。
定理 7.1.4
(殘餘增廣與割證書)
沿殘餘路徑按其為正的瓶頸值增廣,會保持可行性,並使流值恰好增加該數值。若不存在殘餘源–匯路徑,則從 可達的頂點構成一個割,其容量等於當前流值。因此當前流是最大流,該割是最小割。
定理 7.1.5
(整數最大流最小割定理)
若所有容量均為非負整數,則存在各弧取值均為整數的最大流,且其流值等於最小割容量。從零流出發,沿任意殘餘源–匯路徑反覆增廣,至多經過 次增廣即終止。當 時,算法立即停止。
證明思路或證明
證明
(在源側把守恆式加總)
對 中各頂點求「流出減流入」之和。內部弧各以相反符號出現一次而互相抵消。由守恆,除 以外各頂點的貢獻均消失,剩下的恰是上式所示的穿過割的淨流量。將割容量減去這個淨流量,其差等於向外弧上未使用的容量加上向內弧上的流量之和。每一項都非負,由此得到上界及其取等條件。
證明
(增廣保持可行性;搜尋停頓時得到緊的割)
對於增廣:瓶頸不超過路徑上任何正向弧的剩餘容量,也不超過任何反向弧上已有的流量。因此更新後的所有原始取值都仍介乎零與容量之間。路徑上每個內部頂點恰有一條殘餘弧進入、一條殘餘弧離開。無論某條指令是增加正向弧還是減少反向弧,它都沿殘餘方向改變該頂點的淨流出量。兩處改變在內部互相抵消,而源點增加瓶頸值,匯點減少瓶頸值。於是守恆性與流值的結論成立。路徑的簡單性避免了同一條原始弧在一條路徑上被雙向使用。
設不存在到 的殘餘路徑,並令 為殘餘意義下可達的頂點集。匯點不在 中。每條向外的原始弧必須飽和:否則其容量為正的正向殘餘弧會通向 之外。每條向內的原始弧上的流量必須為零:否則其容量為正的反向殘餘弧同樣會離開 。由第一個定理中的取等條件得 。再由對一切割成立的上界,兩個最優性即同時得到證明。
證明透視
從失敗的搜尋中讀出割
關鍵的一步是:割並非預先選定,而是從殘餘搜尋中讀出,即從 可達的頂點集 。兩類殘餘弧各司其職。正向殘餘弧迫使從 到 的每條原始弧飽和;反向殘餘弧迫使從 到 的每條原始弧流量為零。兩者缺一不可,因為割上界的取等情形有兩個條件。
在第一個例題中,沿 送出一單位後,若搜尋忽略反向弧,可達集恰為 。它的向外弧 與 都已飽和,所以這個割的容量為二,而流值只有一,因為向內弧 仍載有一單位。正是反向弧 讓搜尋得以繼續。論證透過對一切割成立的上界完成:流值等於 的流不可能被超越,容量等於 的割也不可能更小,所以兩者同時是最優的。整數性在此毫無作用;它只出現在終止性的證明中,那裏每次增廣使整數流值至少增加一,而上限 是有限的。
證明
(在源點割的上限下作整數步增廣)
最後,從零流和整數容量出發。所有殘餘容量與瓶頸始終是整數,所以每次增廣使整數流值至少增加一。僅由源點構成的割把流值限制在 以內。因此至多發生 次增廣,殘餘搜尋終將失敗。前面的割證書隨即證明整數最優流的存在,以及兩個最優值相等。這一論證證明了整數容量下的終止性;它並不能為不受限制的實數容量下任意選路的終止性提供依據。
例題詳解
例題 7.1.6
(反向弧修正早先的路徑選擇)
令 的容量均為一,其中每個兩字母標籤表示由第一個頂點指向第二個頂點的弧。首先沿 送一單位流。僅用原始弧已找不到第二條路徑,但殘餘路徑 存在。其中的弧 取消了先前在 上的那一單位流。結果是一單位經 ,另一單位經 ,流值為二。源點割的容量為二,故最優性得證。
例題 7.1.7
(用割證明低於源點容量的流值是最優的)
取容量 。流 是可行的:頂點 流入三單位、流出三單位; 流入四單位、流出四單位。其流值為六。割 的向外容量為 ,故此流為最大流。源點的總容量為七,那只是一個上界,並未達到。
例題 7.1.8
(數值上的界不一定是輸入長度的多項式)
令弧 的容量為 ,弧 的容量為一。反覆選擇殘餘路徑 與 。第二條路徑會取消第一條路徑在 上的那一單位流。每一對增廣使兩條直接支路上的流量各增加一,並使 復原。要達到流值 需要 次增廣,而 僅需 個二進制位。對於這些選路方式,終止界是成立的,但相對於編碼後的輸入長度可能是指數級的。
為甚麼反向殘餘容量等於已有流量
正向指令消耗尚未使用的容量,反向指令則撤回已經承諾的流量。人們取消的流量不可能超過先前送出的量,這正是反向容量恰好等於原始弧上已有流量的原因。取消之後,原始流量仍然非負;正向增加之後,它仍不超過原始容量。這兩個界就是局部可行性的證明。
當原始網絡中還存在反方向的弧時,它提供一個獨立的可能操作。走該弧的正向殘餘弧,是沿那個方向送出新的流量;走相反原始弧的反向殘餘弧,則是取消舊的流量。兩種操作可用的數量可能不同,並且改變的是不同的原始變量。帶標籤的殘餘表示能夠無歧義地區分它們。在精心設計的實現中也可以合併它們的容量,但證明仍須說明究竟改變了哪些原始流量。
殘餘圖在每次增廣之後也會改變。先前不存在的反向弧可能變得可用,先前可用的正向弧也可能因飽和而消失。因此只在初始殘餘圖中搜尋,會漏掉合法的修正。搜尋針對的是當前流狀態的性質。
源點與匯點的記帳
流值是源點的淨流出量,而不僅僅是流出弧上的流量之和,因為容許有弧流入源點。割恆等式自動處理了這一點。取源側為除匯點以外的全體頂點,還可說明流值等於匯點的淨流入量。其他所有頂點上的守恆性,保證了這兩種描述一致。
可行流中可能含有有向環流,它不帶來額外的源–匯流值。這樣的環流並不能證明存在更大的最優值;它的貢獻在每個割上都互相抵消。反過來,最大流不必唯一,其具體的走法也不由最小割決定。該定理等同的是最優值,而不是各個具體的流配置,也不是唯一的瓶頸。
匹配作為單位容量的運輸問題
對於二分部分為 的二部圖,添加一個源點,向每個左頂點連一條容量為一的弧,並添加一個新匯點,由每個右頂點向它連一條容量為一的弧。把圖的每條邊從左向右定向,並賦予容量 。一個匹配可以產生一個整數流:沿其每條「源點—左—右—匯點」路徑各送一單位流。
反過來,一個整數可行流從任一左頂點流出的至多為一單位,因為進入該頂點的唯一一條弧容量為一。出於類似的原因,進入任一右頂點的也至多為一單位。因此它的取正值的中間弧構成一個匹配,其條數等於流值。整數最大流的存在性由此建立了在所構造的網絡中最大匹配大小與最大流值之間的相等關係。
中間弧取較大的有限容量,也使最小割描述出一個頂點覆蓋。僅含源點的割容量為 ,所以最小割不可能穿過容量為 的中間弧。於是每條原始邊的左端點在匯側,或右端點在源側。這些頂點構成一個覆蓋,其大小恰好等於由單位邊界弧給出的割容量。這給出匹配與覆蓋相等的第二條證明路線,並說明有限的較大容量就已足夠;不需要真正的無窮大。
概念視角結構
交錯路徑其實就是殘餘路徑
被選中的匹配邊在其中間弧上載有一單位流,所以它的反向殘餘方向容許撤銷這一分配。未被選中的邊則容許添加一條。因此一條源–匯殘餘路徑恰好刻畫了增廣路徑的重新分配機制。更一般的流框架保留了同一思想,同時容許容量大於一。
初等算法的成本陳述意味著甚麼
利用鄰接表,殘餘搜尋可以在與頂點數加原始弧數成正比的時間內實現,因為每條原始弧至多貢獻兩條殘餘指令。將此與整數增廣次數的界結合,這一初等方法需要 次運算。參數 是容量的數值,而不是它的二進制長度。
第三個例子表明,這一區別是實際操作層面的,而不只是一個寬鬆的界。不同的選路規則可以顯著改善效能,但這些改進需要進一步的分析。本節的證明建立了正確性、依賴容量的終止界,以及整數最優流的存在性。它並未建立強多項式時間算法。
常見錯誤
常見錯誤
(原始路徑沒有剩餘容量便停止)
一條已飽和的原始源–匯路徑並不能證明最優。其他路徑或殘餘反轉仍可能改進該流:在第一個例題中,送出 後已沒有原始路徑可用,流值卻仍可加倍。同樣,一個匹配可能需要透過交換邊來改進,而不是直接添加一條邊;這兩種失敗都源於拒絕重新考慮先前的決定。
反例模式
整數容量並不迫使每個最優流都是整數流
令弧 的容量均為一。在 上送一單位流,並沿 與 各送半個單位。這個分數流的流值為一,等於源點割,因此是最大流。僅使用經過 的支路,同樣存在整數最優流。整數性定理斷言的是整數最優流的存在,而不是每個可行流或最優流都是整數流。
常見錯誤
(錯誤計算進入割的弧)
在割的上界中,不要把進入割的弧計為正的容量。它們的流量要從淨流值中減去。同樣,若向內的弧上仍有正流量,僅有向外弧飽和並不能證明取等;兩個取等條件缺一不可。
總結
殘餘弧同時編碼了剩餘容量與可逆的決定。增廣保持可行性,而一次失敗的殘餘搜尋會給出一個恰好等於所達流值的割。整數容量使任意選路的增廣必然終止,並給出整數最優流。依賴容量的運行時間與二進制輸入下的複雜度是兩個不同的論斷。
練習
快速檢查
(對於容量 、、、、,求一個最大流並列出所有最小割。)
這個四頂點網絡中,可能的源側只有四種。
解答 · 答案
取流 。守恆成立,流值為五。源側 、 與 的容量分別為五、五與五。其餘的可能 的容量為六。對一切割成立的上界證明最大流值為五,枚舉則恰好給出這三個最小割。
快速檢查
(在匹配的歸約中,解釋為甚麼在中間弧上使用容量一仍然能表示匹配的大小,卻可能使最小割不能直接給出所述的頂點覆蓋。)
考慮只有一條邊的圖。
解答 · 答案
設只有一個左頂點 、一個右頂點 和邊 ,則單位中間容量給出的網絡,其最大流為一。源側為 的割只穿過中間弧,並且是最小割。然而,由匯側左頂點與源側右頂點組成的所謂覆蓋是空集,因此漏掉了 。取中間容量 即把這個割排除出最小割,從而使覆蓋的論證得以恢復。
快速檢查
(證明:若一個可行流的流值等於某個割的容量,則每條向外的弧都已飽和,且每條向內的弧上的流量為零。)
解釋為甚麼誤差項之間的抵消不會使結論失效。
解答 · 答案
用容量減去割恆等式:其差為 。由可行性,每一項都非負。取等使這個有限和為零,因此每一項分別為零。這裏不可能有正項與負項之間的抵消,因為根本不存在負項。於是所述的兩個條件成立。