流量算法改變各條弧的流量時,必須維持每個節點的平衡。生成樹提供清晰的記賬方法:固定非樹弧流量後,樹弧流量便被唯一決定。加入一條非樹弧恰好產生一個環,因此只需追蹤一條路徑,就能找到整個可行方向。本節在連通有限網絡上推導精確算術的主元規則。
樹表示
設 是有限連通有向多重圖,沒有自環;平行弧和相反方向的弧各有獨立標籤。節點—弧關聯矩陣 在弧的起點記 、終點記 。可行流滿足 及有限界限 ,其中 。因此 是流出量減流入量,必有 ;成本是 。
定義 26.1.1
(樹解)
選底層無向圖的一棵生成樹 。 的樹解把每條非樹弧固定在一個界限( 或 ),再由節點平衡 求出樹弧流量。所得樹弧流量均在界限內時,稱此樹解為可行。
樹弧本身可以在界限上:這是退化樹解,並非丟棄該樹的理由。上下界相等的非樹弧已固定,不能進入基底。
定理 26.1.2
(樹上平衡唯一決定流量)
對任意已選的非樹弧流量及總和為零的 ,恰有一組實數樹弧流量滿足 。
證明
(逐一消去葉節點)
從 減去非樹弧的貢獻,得到總和仍為零的剩餘平衡。在樹的葉節點,唯一相接的樹弧流量由該節點平衡唯一決定,符號視弧方向而定。移除葉及其弧,並按該流量的貢獻更新相鄰節點的剩餘平衡。更新後剩餘平衡總和仍為零。重複至只剩一點,其平衡自動成立。這構造出一組解;每次葉節點方程都迫使所選值唯一,故解唯一。只有所求值均落在各自區間內,此解才可行。
概念視角代數
生成樹就是關聯矩陣的基
的每一列恰有一個 和一個 ,所以 各行之和為零,每一列都位於維數為 的子空間 內。上述定理說: 條樹弧所對應的列把係數雙射地映到 ,即它們構成 的一組基,因而 正是 的列空間。反之,含無向環的弧集合,其列線性相關,因為沿環帶符號相加的列之和為零。所以 的基恰好是生成樹的弧集合,而樹解正是有界線性規劃的基本解:樹弧是基變量,非樹弧是停在界限上的非基變量。
價格、方向與比值測試
選節點價格 ,使每條樹弧 都滿足 。可任選一個價格,沿樹推算其餘價格。每條弧的約化成本記作 。處於下界的非樹弧只能先向前增加,其成本斜率為 ;處於上界的則只能先向後減少,斜率為 。因此候選改善弧是在下界而 ,或在上界而 的非樹弧。
常見錯誤
(判斷改善符號時忽略界限狀態)
常見做法是只讓 的弧進入。這規則只適用於處於下界的非樹弧。處於上界的弧只能減少,斜率是 ,所以 時才是改善。下面第二個例題中, 為正,但 正是應進入的弧。
要找配合它的樹弧變動,先把進入弧加入 ,得到唯一無向環。若進入弧由下界增加,令其係數 ;若由上界減少,令 。為環上樹弧指定 或 ,使 ,其他係數為零。等價地,沿進入弧選定方向前進,再沿唯一樹路徑返回:行進方向與原弧方向相同記 ,相反記 。
命題 26.1.3
(環方向的斜率等於進入弧的約化成本)
設價格 使每條樹弧 都有 ;設 是非樹弧, 是它的環方向:、,且環外每條弧 都有 。則
證明
(把成本寫成約化成本減去價格差)
由 的定義,每條弧 都有 ,而 是 的第 個分量。因此
因為 。餘下的和中,環外 ,環上樹弧 ,只剩進入弧一項,故 。
證明用了兩種不同的抵消,值得分開來看。
證明透視
為何整個斜率由約化成本決定
假設在哪裏用上:條件 消去價格項,樹價格消去環上其餘的弧。第一種抵消完全不用到樹:對任何循環方向及任何價格,都有 ,因為循環流看不見價格差。樹只用來令這個環上其他弧的約化成本為零。
關鍵一步:以 取代 ;這改變每條弧的成本,卻不改變任何環的成本。
缺了甚麼會出錯:沿用舊樹的價格,在當前樹弧上未必為零,單一弧的測試便會報錯斜率。例如第一個例題主元之後,舊價格 給新樹弧 的約化成本是 。
如何收結:命題只給出斜率的符號,並未保證成本下降。若下面的步長為零,成本根本不變。
最大可行步長 是所有 的環弧之 ,與所有 的環弧之 的最小值。進入弧也要納入最小值。令 。若某樹弧到達界限,它可以離開;以進入弧代替它後仍是生成樹,因為移去的邊位於新環上。其他同時到界的樹弧可留在樹內。若只有進入弧到達另一界限,保留原樹,讓該弧在另一界限繼續作非樹弧;這稱為界限翻轉。若兩類弧同時到界,可選合適的樹交換或界限翻轉。
常見錯誤
(把所有同時到界的樹弧都移走)
若幾條樹弧同時到界,只能有一條離開。 個節點的生成樹有 條弧,而只有一條弧進入;移走兩條便不足以連通所有節點。第一個例題中兩條樹弧都降到零,若全部移走,三個節點上只剩 一條弧。其餘同時到界的弧以界限值留在樹內,這正是退化樹解。
瓶頸為零時,基底改變但流量及成本不變。所以單憑負斜率,不能斷言當前流量不是最優。實際有限算法需要明確的平手處理或防循環規則;以上局部步驟本身不證明終止。這裏的成本及界限均按精確數值處理,不涉及浮點容差。
樹主元與證書
例題 26.1.4
(負約化成本令一條樹弧離開)
節點 間有弧 、、,成本 ,下界均為零、上界均為三;平衡為 。以前兩條弧為樹,取 ,成本 。令 ,樹方程給出 、。非樹弧約化成本為 。
增加 並沿樹路徑 返回,得 ,故 。新流量 的成本為 ,下降 。兩條樹弧都到零;移去 ,把零流量的 留在樹中。新樹價格為 ,唯一非樹弧約化成本是 。
對任意可行 ,。樹弧約化成本為零,而 且 ,所以 。新流量達到此下界,故最優。保留零流量樹弧是維持這個樹表示所必需的。
例題 26.1.5
(上界弧可反向進入並翻轉界限)
保持上述平衡及樹,但用成本 、上界 ,由 開始,成本為 。樹價格 給出 。因 位於上界,減少它:,成本斜率是 。容量最小值為 。只有進入弧到界,所以樹不變, 翻轉至下界。結果 成本為 ;不變的價格證明最優,因為下界處的 。
例題 26.1.6
(步長為零的退化主元)
沿用第一個例題的網絡(成本 、界限 ),但所有平衡為零,即求最便宜的循環流。取樹 及 ;兩條樹弧都在下界。價格仍是 ,而下界處 ,所以方向 的斜率為 。
比值測試給出 :樹弧不能再減少。讓 離開, 以零流量進入。流量和成本 都不變。新樹 的價格是 ,下界處 ,所以新的表示證明了最優性。
直接看,節點 的平衡是 ,而 ,所以唯一可行流是零。第一棵樹表示的流量本已最優,卻通不過符號測試:證書失敗只說明需要換基,並不表示流量可以改善。
反例模式
比值測試不能遺漏進入弧
第二個例子若只看樹弧,會得到步長 ,但這會使 由 降至 ,違反下界。進入弧本身的剩餘區間把合法步長限制為 。
每個例題最後得到的符號模式,是一個一般的證書。
定理 26.1.7
(約化成本最優性證書)
設 是生成樹 的可行樹解,價格 使每條樹弧都有 。若每條 的非樹弧,在 時有 ,在 時有 ,則 在所有可行流中使 最小。
證明
(逐條弧與任意可行流比較)
設 可行。與斜率命題一樣,,而 。因此
樹弧項為零。下界處的非樹弧有 及 ;上界處的有 及 。固定弧有 ,不論約化成本如何都貢獻零。每一項均非負,故 。
這些符號是當前可行流的證書;對固定的樹,定理沒有逆命題:退化例題正好給出一個最優流,其樹表示卻通不過測試。
練習與解答
快速檢查
(在第一例改為移去 (而非 )。求新價格並檢查最優性。)
新樹由 和 組成。
解答 · 答案
樹弧是 和 。令 ,則 、。非樹弧在下界且 ,原成本 仍是最優。
快速檢查
(在第二例把直達弧上界由 改為 ,但保留流量 。同一棵樹下它仍是樹解嗎?)
比較非樹弧流量與其界限。
解答 · 答案
不是。直達非樹弧流量 嚴格位於新界限 和 之間。流量雖仍可行,卻不符合此樹及界限狀態的樹解定義。
快速檢查
(某環方向係數為 ,當前流量為 ,界限為 。求步長及所有到界的弧。)
在 處用 ,在 處用 。
解答 · 答案
三個允許改變量為 、、,所以 ;只有第三條弧到達其上界。
快速檢查
(非樹弧有 和約化成本 。這會令價格證書失效嗎?)
想想這條弧在可行流中可以取甚麼值。
解答 · 答案
不會。每個可行流在該固定弧上的值相同,因此它對成本差貢獻零,也沒有可行的進入方向。