動機
一個網絡即使從源點流出的容量十分充裕,最終送達終點的流量仍可能很少:下游某處的瓶頸可能限制了每一條路線。流為各條邊分配相互兼容的流量,而割則給出對所有可能的流的一個上界。殘量網絡把這兩種觀點聯繫起來:它既告訴我們如何改進一個候選流,也告訴我們為甚麼不再有可改進之處。
定義
定義 3.1.1
(流、流值與割)
設 為有限有向圖, 與 為互不相同的源點和匯點,容量 。為簡單起見,每個有序點對只使用一條有向邊;允許存在方向相反的有向邊。流為每條邊指定 ,並在 以外的每個頂點滿足守恆:流入量等於流出量。流的值是 處的淨流出量。– 割是滿足 、 的劃分 ;其容量是原圖中從 指向 的各條邊的容量之和。
定義 3.1.2
(殘量網絡與增廣路徑)
對於原圖中的每條邊 ,殘量網絡含有一條容量為 的正向弧和一條容量為 的反向弧,並且只保留容量為正的弧。反向弧表示可以抵消先前已送出的流,並不是額外的原始容量。若方向相反的原始邊產生了平行的殘量弧,須保留它們各自的身份:沿其中一條弧增廣,修改的是它自己對應的原始邊。增廣路徑是殘量網絡中的一條有向 – 路徑;其瓶頸是該路徑上殘量容量的最小值。
定理
定理 3.1.3
(流–割等式與最優性)
對每個可行流 和每個 – 割 ,都有 。一個可行流是最大流,當且僅當其殘量網絡中沒有增廣路徑。此時,殘量網絡中從 可達的頂點給出一個容量為 的割。
定理 3.1.4
(整數增廣)
若所有容量均為非負整數,則從零流出發,沿任意殘量路徑按其瓶頸反覆增廣,必在有限步後終止,並得到一個整數最大流。若 為離開 的各邊容量之和,則增廣至多進行 次。這個界取決於 的數值大小,不一定是其二進制編碼長度的多項式。
證明思路或證明
證明
(弱對偶性:每個割都是每個流的上界)
對 中除 以外的所有頂點求守恆式之和。內部的邊互相抵消,得到 。這就證明了弱對偶性:任何割都是任何流的上界。
證明
(沿殘量路徑增廣)
沿殘量路徑,使用正向弧時增加相應原始邊的流量,使用反向弧時則減少。瓶頸保證每條被修改的邊的流量仍在其界限之內。路徑上每個內部頂點接收與送出的增量相同(包括某條弧抵消一條原始邊的情形),所以守恆依然成立,而流的淨值恰好增加瓶頸的大小。因此,存在增廣路徑的流不是最大流。
證明
(沒有增廣路徑便得到容量相等的割)
若不存在這樣的路徑,令 為可達頂點的集合, 為其餘頂點。每條從 指向 的原始邊都是飽和的,否則其正向殘量弧會到達 。每條從 指向 的原始邊流量為零,否則其反向殘量弧會到達 。於是割的恆等式化為 。由弱對偶性可知, 是最大流,而這個割是最小割。這同時也證明了逆命題:最大流沒有增廣路徑。
證明透視
一份證書,而非猜測
最優性的證明把失敗的搜尋轉化為一個割。從 可達的頂點集合 按構造對殘量弧封閉,而唯一用到的就是這個封閉性:沒有正容量的殘量弧離開 。逐條邊展開它,便得到所需的兩個等式。若原圖中從 到 的邊還有剩餘容量,就會有一條正容量的正向弧離開 ,所以每條這樣的邊都是飽和的。若從 到 的邊帶有正流量,就會有一條正容量的反向弧離開 ,所以每條這樣的邊流量為零。恆等式 於是成為 。由守恆證明的弱對偶性完成論證:沒有流可以超過這個割,也沒有割可以低於這個流。若沒有反向弧,第二個等式就會失去,搜尋可能停在並非最大的流上,這就是為甚麼抵消例子中的早期選擇必須可以撤銷。
證明
(整數容量保證終止)
對於整數容量,初始的零流是整數流,且所有殘量容量始終保持為整數。每次增廣的瓶頸為正整數,使流的值至少增加一。割 把流的值限制在 以內,所以該過程至多經 次迭代就會停止,最優性隨之成立。若以廣度優先方式選取最短增廣路徑,則存在與容量數值無關的多項式界,但這一單獨的界在此不予證明。
例題詳解
例題 3.1.5
(兩條路線與一個瓶頸)
設容量為 、、、、。沿 送出 ,沿 送出 ;再沿 送出 。該流的值為 。割 的容量為 ,由此證明該流是最優的。
例題 3.1.6
(抵消早先的選擇)
設 、、、、 的容量均為 。若第一條路徑取 ,則從 經 的直接正向路線已經飽和。殘量路徑 使用了 的反向弧。增廣時抵消該邊上的流,最終在 與 上各留下一個單位的流。所得的值 等於以源點為界的割的容量。
例題 3.1.7
(含有反向邊的割的界)
設某個割的正向容量為 ,當前正向流為 ,同時還有 個單位的原始流從 流回 。它對流的值的淨貢獻是 ,而不是 。若只累加正向流,就會高估流的值。即使最優流恰好在其證明用的割上沒有反向流,這個恆等式仍然同時包含兩個方向。
常見錯誤
常見錯誤
(殘量容量不等於原始容量)
即使原圖在某個方向上沒有邊,也可能出現容量為一的反向弧。它允許抵消先前送出的一個單位流,卻不允許在並不存在的邊上送出無限的新流。
反例模式
任意增廣路徑可以用盡整個界
考慮這樣的說法:沿任意殘量路徑增廣,所需步數對輸入的大小而言只是多項式的。設 為正整數。取邊 、、、,容量均為 ,再取邊 ,容量為 ,於是 。交替地沿 與沿 增廣,後一條路徑使用 的反向弧。每條路徑的瓶頸值都是一,每次增廣恰使流值增加一,而流值 要經過 次增廣才能達到。界 被達到了,步數隨 增長,對 的位元數而言是指數級的。修正後的說法限制路徑的選擇,例如只取廣度優先的最短路徑,其多項式界是另一個結果。
常見錯誤
(所選路徑被堵住並不表示沒有路徑)
僅因目前所選的路徑被堵塞就停止是不夠的:另一條殘量路徑可能會重新安排先前的選擇。算法必須搜尋整個殘量網絡。對於實數容量,弱對偶性和「無路徑」證書仍然有效,但整數情形的終止性證明不適用於任意的路徑選擇。
從過程到證書
殘量搜尋不僅應記錄某個頂點已被到達,還應記錄到達它所經的前驅弧。若到達了 ,從 沿前驅回溯至 即可得到一條路徑及其瓶頸。若搜尋結束時仍未到達 ,則其訪問過的集合恰好是最優性證書中的 一側。無論哪種情形,同一次搜尋都給出證明所需的下一個對象。須小心保留每條殘量弧的身份與方向,尤其是在原圖中兩個方向都有邊的時候:從 到 的一條弧,既可能增加 的流,也可能抵消某條 上的流。
例如,若 、、、,則從 到 有兩種殘量機會:把第一條邊的流最多增加 ,或把第二條邊的流最多抵消 。它們端點相同,但更新方式不同。只有當實作在更新原始邊時同時選取了一種合法的分解,才可以把它們的數值容量合併。保留帶標記的平行弧可以避免這項額外的記賬工作。
割的恆等式也說明了等式成立需要甚麼條件。在
中,正向求和裏的每個差 以及每個反向流都是非負的。等式成立當且僅當所有正向割邊都飽和,且所有反向割邊的流為零。這個條件可以對任意給定的可行流和割證明最優性,而無須假定該流是如何構造出來的。它也解釋了可達性割為何有效:若有一條容量為正的殘量弧從 跨向 ,就會與 的定義相矛盾。
例題 3.1.8
(流與割作為相互獨立的證書)
考慮容量 、、、、。依次指定流量 。在 處,所設的流入量為 ,而流出量為 ,所以這一指派根本不是流。將 增加到 即可修正。此時流的值為 ,且守恆成立:在 處 ,在 處 。割 的容量為 ,所以修正後的流是最大流。若先檢驗割而不檢驗守恆,原先的錯誤就會被掩蓋。
建模的限制
容量是上界,並不是要求每條邊都必須被使用。守恆只適用於中間頂點,源點和匯點可以既有入邊又有出邊;這正是把流的值定義為「淨」流出量的原因。沿有向圈的一個正環流會改變各條邊的流量,卻不改變流的值。因此,即使最大值是唯一的,最大流也不一定唯一。最優解也不必用到每一條可用的邊。
定理允許容量為零,也允許零流。若不存在容量為正的從 到 的有向路徑,則初始的殘量搜尋會得到容量為零的割,而零已經是最優值。反過來,即使存在路徑,流的值也可能很小:路徑存在只保證有某個正的增廣量,並不限制總量。對於整數數據,界 在最壞情形下計數增廣的次數;若容量以二進制編碼, 位的數可以大到 。因此,僅憑這個界不能確立關於輸入長度的多項式執行時間。
應用:二分圖匹配
對於左頂點集為 、右頂點集為 的二分圖,構造如下網絡:從 到每個左頂點連一條單位邊;對圖中的每條邊,從 到 連一條有向單位邊;從每個右頂點到 連一條單位邊。這裏的整數流可以分解為被選中的左–右邊:由守恆以及源點、匯點處的單位邊可知,沒有任何頂點被使用超過一次。反之,對匹配中的每條邊,沿 送出一個單位的流。因此最大流的值等於最大匹配的大小。整數性定理對於把邊上的流解讀為真正的「選或不選」的匹配決定至關重要;一般的分數可行流不能直接稱為匹配。
例如,取 、,邊為 –、–、–。若先選 –,可能會堵住 的直接選擇。殘量路徑 抵消先前的 – 選擇,改為 – 與 –。這就是匹配版本的流重新安排。僅含 的割容量為二,這證明所得大小為二的匹配是最優的。
檢驗一個給定的解
一種實用的檢驗順序是:先檢查邊的界限,再檢查守恆,再檢查所聲稱的值,最後才與割比較。這四個步驟缺一不可。若某個流的值大於所給出的割,那它不可能是弱對偶性的反例:這幾項檢查中至少有一項失敗了。對於數值證書,應寫出每條邊上的流(包括為零的),並列出割上所有按正向穿越的原始邊。反向穿越的邊進入流的恆等式,卻不計入割容量的定義。要成為值相等的證書,它們的流實際上必須為零。
殘量路徑是由殘量弧組成的序列,不一定是由正向原始邊組成的序列。只要有任一殘量遊走到達匯點,就能找到一條簡單路徑,因為遊走中重複的頂點可以去掉。如果某條路徑使用了一條對應於已載有三個單位流的邊的反向弧,增廣就不能抵消超過這三個單位。若同一路徑上其餘各弧的殘量容量最小為二,則瓶頸為二,所以算法使每條弧改變二,被抵消的邊仍留下一個單位。選取更大的增量會違反至少一個容量或非負性約束。
整數增廣的界並不要求每條邊的流各自單調增加。反向殘量弧可以減少先前指派的流,如匹配例子所示。單調增加的是整個流的「淨值」。由於該值是整數,而固定的割給它設了上界,這個單調的量就足以證明終止性。這是算法中常見的證明模式:確立進展的勢函數,可以不同於每一步所修改的局部變量。
最後,最小割命題還提供靈敏度資訊。如果某個割的容量為六,那麼給不穿越該割的邊增加容量,其本身不可能使最大值超過六,因為同一個割仍然是上界。增加穿越某個最小割的邊的容量可能會提高這個界,但並不保證最大值上升:另一個最小割可能保持不變。在斷言有所改進之前,應重新計算,或給出新的值相等的流–割證書。
總結
流的守恆使每個割都成為上界。殘量路徑改進可行流,而這類路徑的不存在則構造出容量相等的割。整數容量保證整數流以及有限的增廣過程,其迭代次數的界可能是偽多項式的。
練習
快速檢查
(在第一個例子中,驗證三次增廣全部完成後 與 處的守恆。)
把進出每個頂點的邊上的流量分別相加。
解答 · 答案
在 處,流入量 等於流出量 。在 處,流入量 等於流出量 。所有使用到的邊上的流量都符合各自的容量。
快速檢查
(某可行流的值為 ,某個割的容量為 。可以得出甚麼結論?為甚麼?)
分別與弱對偶性比較。
解答 · 答案
由弱對偶性,每個流都以 為上界,每個割的容量都不小於 ,所以所給的流是最大流,所給的割是最小割。
快速檢查
(容量均為整數且 時,沿任意路徑增廣的算法至多能執行多少次增廣?)
每次增廣使整數流值至少增加一。
解答 · 答案
至多 次:每次增廣使整數流的值至少增加一,而源點割把流的值限制在 以內。
快速檢查
(某網絡中 的容量為 , 的容量為 ,沒有其他邊。求一個最大流和一個最小割。)
找出唯一路徑上的瓶頸。
解答 · 答案
沿該路徑送出 個單位的流。割 的容量為 ,證明了最優性。源點邊未使用的 個單位容量無法穿過瓶頸。