本節討論網絡優化中最大流及最短路徑兩個核心問題的模型與證書。證明直接使用圖論推理;線性規劃的界與證書觀念有助理解兩者的聯繫。
動機
通訊網絡有兩個不同問題:每條連線容量有限時,每單位時間最多可傳多少數據?每條連線有延遲時,哪條路線總延遲最小?前者容許多條路線同時分流,後者找一條最短路線。快速但狹窄的連線仍可能限制總流量,大容量連線也未必在最短路上。目標不同,便不能沿用同一個直覺答案。
一次貪心選擇可能堵塞日後的兩條路線。殘量網絡把已做決策可增加或可撤回的幅度記錄下來,修正舊選擇便轉化成另一個路徑搜尋,不必全部推倒重來。尤其反向殘量弧不是物理上逆向傳送,而是帳目上取消先前流量。
兩種問題都有短證書。流與割的值相等,證明吞吐量最大;路徑長度等於可行勢能的下界,證明路徑最短。檢查證書不必重演找出答案的全部步驟,這對大型計算尤其有用。
定義
定義 2.1.1
(有向流、流值及割)
設 是有限有向圖,源點 與匯點 不同。每條有標籤弧 的容量 有限且非負。可行流滿足 ,並在源點、匯點以外每個頂點保持流入總量等於流出總量。流值是源點的淨流出量:
割是包含 而不包含 的頂點集 。割容量只加總從 指向補集的弧容量。
原圖容許相反方向的兩條不同弧,必須保留標籤。每條原弧 產生正向殘量容量 ,以及從 到 的反向殘量容量 ;只有正容量方向才放入殘量網絡。多條殘量弧即使起點終點相同,也可能代表不同原變量的改動,不能不加分辨地合併。
殘量網絡中由源至匯的路徑稱為增廣路徑,其瓶頸是沿路最小殘量容量。增廣時對正向弧增加這個量,對反向弧所屬原流量減去這個量。這個定義把修正方向與原圖方向清楚分開。
最短路徑問題另給每條弧實數長度 。遊走可以重複頂點及弧,長度按使用次數累加;路徑不重複頂點。距離勢能是一組實數 ,滿足 及每條弧上的 。它描述到達頂點的下界,本身還不是一條被選中的路徑。
定理/命題
定理 2.1.2
(最大流等於最小割)
有限網絡配有限非負容量時,最大可行流存在,其值等於最小割容量。一個可行流最優,當且僅當殘量網絡沒有增廣路徑。若全部容量是整數,則存在整數最大流。
實數容量也有最大流,但任意選路的增廣算法對無理數容量未必有限步終止。下面整數終止論證只直接適用於整數容量;有理容量可先統一縮放。證書成立的條件與某一算法終止的條件要分開。
命題 2.1.3
(最短路徑的勢能證書)
若 是距離勢能,則每個由 到 的有向遊走長度至少為 。若一條源匯路徑上全部弧都緊,即 ,則該路徑長度恰為 ,在所有源匯遊走中最短。
全圖可行勢能排除了任何負長度有向環,因為環上不等式相加會導出零不大於負數。不相關的不可達分量若有負環,也會妨礙全圖勢能存在。計算源點距離時可先限制於可達頂點;對特定匯點,負環只有在源點能到達它、且它能到達匯點時,才令源匯遊走長度向下無界。
證明思路
證明
(割限制流,而可達割取得此界)
把割集 內的守恆方程相加,內部弧互相抵消,得到
故任何割都限制任何流。實際流值要扣除進入割集的流;割容量卻只計外向容量,兩者不能混淆。
若有增廣路徑,按瓶頸改動保留每條原弧的容量界。內部頂點的淨流出改變量為零,即使使用反向殘量弧也一樣;源點淨流出則嚴格增加。因此最優流不能有增廣路徑。
反過來,若無增廣路徑,取 為殘量網絡內源點可達的頂點。匯點不在其中。每條離開 的原弧必飽和,否則還有正向殘量弧可到達新頂點;每條進入 的原弧必為零流,否則其反向殘量弧會離開 。割恆等式遂成等號,流與割同值,證明最優。
存在性也須交代。零流可行,每個流量座標都被有限容量夾住,而守恆及容量條件形成閉集,所以可行集非空且緊緻。連續流值取得最大值,再套用前面的殘量網絡論證便得到等值割,毋須假設算法終止。
整數容量時從零開始,每次增廣保持流量及殘量容量整數,瓶頸至少一。流值有源點外向容量總和這個有限上界,因此有限步後終止,產生整數最大流。
證明透視
兩個剩餘事實補上差距
這個證明有四項獨立工作:割恆等式對每個流和每個割給出上界;增廣說明最大流沒有增廣路徑;可達割給出逆命題;緊緻性與整數步長給出存在性及整數性。
關鍵一步:取 為殘量網絡中一切可達頂點。 沒有向外的正向殘量容量,表示外向弧飽和;沒有向外的反向殘量容量,表示內向弧零流。這正是令割不等式成為嚴格不等式的兩類項。
缺了反向弧會怎樣:在第一個例題中,沿 送流後,只用正向弧的可達集是 。它的外向弧 與 都飽和,但內向弧 帶一單位,所以流值 嚴格小於割容量 。這甚麼也證明不了,而該流確實不是最大。
有限性在哪裏用上:存在性用有限多條弧及有限容量令可行集緊緻;整數性用有限上界及每步至少增加一。兩者都不依賴算法選哪條增廣路徑。
最短路徑證書只需一次伸縮求和。
證明
(把勢能不等式伸縮相加)
勢能定理把路徑各弧不等式相加,中間項抵消,留下 ;全為緊弧時取等號。
這部分不要求弧長非負;非負性只在 Dijkstra 這個特定貪心算法的正確性證明中才需要。回到流的問題,割恆等式也有代數的讀法。
概念視角代數
割證書是一組非負誤差之和
割容量減淨流值,等於外向弧未用容量之和,加上內向弧已有流量之和,每項皆非負。殘量可達集令兩類誤差都為零:外向弧飽和,內向弧零流。這與線性規劃對偶差距的模式相同。圖論找到令全部誤差消失的割,代數則說明局部核驗何以保證全局最大。
如何找出距離標籤
Dijkstra 方法把源點標籤設為零,其他設為無限。每次固定未固定頂點中標籤最小者,用其標籤加弧長更新相鄰頂點,同時記錄前驅。
命題 2.1.4
(弧長非負時已固定標籤是精確距離)
若每條弧長都非負,則 Dijkstra 方法固定頂點 時,其標籤等於由 到 的有向遊走的最短長度。
證明
(更短路線上第一個未固定頂點)
已固定頂點的標籤是前驅所記錄的一條實際遊走的長度,所以不會低於真實距離。考慮一條據稱更短的路線及其第一個未固定頂點。它的前驅已固定,故鬆弛操作曾給它不大於該路線前綴的標籤。非負弧長保證前綴不長於整條路線,與本次選取最小標籤矛盾。
無限標籤表示不可達,並非實數勢能值。
反例模式
一條負弧就能擊敗只固定一次的標籤法
改用弧長 。Dijkstra 固定 ,給 標籤 和 ;固定 後把 設為 。因為 ,它在檢查 之前就把 固定為 。但路徑 的長度是 。圖雖沒有有向環,負弧仍破壞非負前綴論證。弧長非負的假設不能刪去;相反,勢能證書對負弧長依然成立。
有負弧時可用 Bellman–Ford 的分階段推理:第 階段記錄最多使用 條弧的最佳遊走,從上一階段所有入弧更新。沒有可達負環時,刪去環不增加長度,所以最多 條弧已足夠;再一階段仍可改善便揭示可達負環。這不是永久固定頂點的貪心證明。
例題詳解
例題 2.1.5
(反向弧修正第一次選路)
原弧 容量全為一。先沿 傳一單位,若只看未用正向弧,似乎再無可行路線。
殘量網絡卻有 ,其中 是原弧 的反向殘量弧。沿此路增廣一單位, 的流從一降至零,其餘四條原弧各流一。最後是兩條普通正向路線 與 ,流值二。割 容量二,證明最優;逆向步驟修正的是舊分配。
例題 2.1.6
(完整核驗流與割)
容量依次為 。沿 傳二,沿 傳二,再沿 傳一,得流量向量 。
的流入三等於流出一加二; 的流入二加一等於流出三。源流值五,源點割容量 ,匯點前的割容量也為 ,任一個都證明最大性。
但割 的外向流是 ,還有原弧 進入此集合並帶一單位。淨跨割流是 。這說明為甚麼流值公式不能漏掉反向穿越割的流。
例題 2.1.7
(路線與勢能給出同一答案)
設弧長 。固定 後, 標籤為二、五;固定 後,把 降至三, 設為八;固定 後,把 降至五。
最後勢能 在五條弧的差依次為 ,都不超過弧長。前驅路徑 全為緊弧,長度五恰等於下界。
常見錯誤
守恆表示頂點局部收支平衡,不表示每條弧流量相同。流可分合,也可帶有不影響源流值的循環。因此即使在同一個圖上,最短路線與最大流也需要不同的核驗。距離標籤同樣要逐弧核驗,並有路徑達到下界;算法中途的暫定值不自動是證書。
常見錯誤
(把飽和弧永久刪除)
殘量容量是對現有決策容許的改動,增廣後必須重新計算。飽和的正向弧仍可能有正的反向殘量弧,日後的增廣也可能令正向重新可用。把飽和弧當作永久刪除,會失去有效的改進。
常見錯誤
(指出瓶頸卻沒有列明頂點集)
看似狹窄的一組弧不一定是割。先列明包含源而不含匯的頂點集 ,再加總所有外向容量。割單獨只給上界,還要同值可行流才證明最大。
常見錯誤
(把整數性誤讀為唯一性)
整數容量只保證存在整數最優流,不表示每個最優流都是整數。取單位容量弧 、、、,按此次序記錄。整數流 與 都取得最大值 。兩者的平均 可行,值亦為 ,所以是帶分數座標的最優流。
總結
殘量網絡記錄可逆決策,沒有增廣路便暴露飽和割;勢能記錄路徑下界,緊弧路徑則取得下界。兩種證書都由可行對象及相等目標值組成。整數容量、非負長度等算法假設,須與較一般的證書結論分開。
練習
快速檢查
(第一例按 順序列出修正前後原流量,核驗兩個內部頂點守恆。)
解答 · 答案
修正前是 , 各流入一、流出一。修正後是 ,兩個頂點各直接由源接收一,再直接送往匯。反向剩餘步驟減少舊 流,不是新增原圖弧。
快速檢查
(第二例只把 容量改為一,求最大流及最小割。)
解答 · 答案
取流 ,值四。 把流入二分成一加一, 把總流入三送往匯。割 的外向弧是 ,容量總和 。匯點前的割容量也是四。可行流配合任一個同值割,便證明最優。
快速檢查
(最短路例提出勢能 ,找出失敗的弧不等式,給出正確勢能及達界路徑。)
解答 · 答案
弧 的勢能差 大於長度一。弧 的差二是容許的,所以只檢查最後一條弧會漏掉錯誤。正確勢能 ,路徑 長度 達到下界。
快速檢查
(弧長 ,證明源匯遊走長度向下無界。若刪去 後再無弧到達 ,結論如何?)
解答 · 答案
環 長度負一。先從 到 ,繞環 次,再沿 到匯,總長 ,趨向負無限。刪去唯一入匯弧後,匯不可達,根本沒有源匯遊走。可達負環不能憑空創造到匯的路線。
快速檢查
(證明可行勢能也是任何非負單位源匯流的成本下界,即使該流分散於多條路線。)
解答 · 答案
把每條 乘以非負流量後相加。內部勢能係數因守恆抵消,源的單位淨流出及匯的單位淨流入留下 。故總成本至少為 ;不用先把流分解成路徑,這已展示最短路線性規劃對偶的核心。