動機
穩健路線需要不會一同失效的備選路徑,但邊與頂點是不同資源。兩條路徑可無公共邊,卻共用關鍵的中間頂點。因此,同一端點對的刪邊問題和刪點問題可以有不同答案。
Menger 定理把最多的不交路徑與阻斷所有路線的最小分隔集連繫起來。路徑族給出可行性下界,分隔集給出最優性上界。本章從已證明的整數最大流最小割定理推導兩種等式,逐項解釋化歸模型,並不略過建模步驟。
定義
定義 9.2.1
(不相交路徑與分隔集)
設 為有限簡單無向圖, 為兩個不同的頂點。本章中的路徑均為簡單路徑。若若干條路徑沒有公共邊,則稱它們是邊互不相交的,它們可以共用頂點。若它們僅有的公共頂點是端點 ,則稱它們是內部頂點互不相交的。邊分隔集是這樣一個邊的集合:刪去它之後不再存在 – 路徑。內部頂點分隔集是 的一個子集:刪去它之後不再存在這樣的路徑。
如果兩個端點本來就不連通,則容許取空分隔集,同時需要裝入的路線數為零。內部頂點形式的定理將假設端點不相鄰。如果有一條邊直接連接兩個端點,那麼刪除內部頂點永遠無法摧毀這條邊,因此所述的分隔集問題沒有有限解。
對於包含 但不包含 的頂點集 ,令 為恰有一個端點在 內、另一個端點在 外的無向邊的集合。這樣的邊界是一個邊分隔集。反過來,刪去任意一個邊分隔集之後,取從 可達的頂點集,則它的邊界上的每條邊都必然已被刪去。因此,最小分隔集的大小等於最小邊界的大小。
定理/命題
定理 9.2.2
(有限無向圖 Menger 定理的邊形式)
兩兩邊互不相交的 – 路徑的最大條數等於邊分隔集的最小大小。等價地,它等於 。無論 是否相鄰,該命題都成立。
定理 9.2.3
(有限無向圖 Menger 定理的內部頂點形式)
若 是兩個不同且不相鄰的頂點,則內部頂點互不相交的 – 路徑的最大條數等於內部頂點分隔集的最小大小。端點永遠不會被刪除,也不計入內部頂點。
任何分隔集都必須與每一條所選路徑相交。對於不相交路徑,分隔集中被刪除的各個資源必須互不相同。這就給出了兩個定理中容易的那個不等式。實質性的部分是反方向:最小大小的阻斷集總能與同樣數量的相容路線相配對。
證明思路或證明
我們使用下面已經建立的流的結果。具有非負整數容量的有限有向網絡存在整數最大流,其值等於最小割的容量。容許有弧進入源點或離開匯點;流的值指源點處的淨流出量。當用方向相反的兩條弧取代無向邊時,這一精確表述是有用的。
以下引理把流轉化為路線。
引理 9.2.4
(整數流可分解為路徑)
設 是有限有向網絡中從源點 到匯點 的非負整數流,其值為 。則存在簡單有向 – 路徑 (容許重複),使每條弧 至多位於其中 條上。
證明
(逐條移去正流路徑的證明)
若流值為正,則存在一條從源點到匯點的、流為正的有向路徑。否則,設 為從源點出發經由正流弧可達的頂點集。沒有正流離開 ,所以其淨流出量非正。但由守恆性及匯點不在 內,這個淨流出量應等於正的源點流值,矛盾。取一條簡單的正流路徑,並從中減去其最小的正弧流量。這保持了守恆性,並使流值減少一個正整數。重複這個過程即可提取出承載全部流值的路徑;剩下的值為零的環流可以捨棄。承載多個單位流的路徑按相應重數列出。由於每次相減後流仍為非負,所列路徑使用每條弧 至多 次。
證明
(邊形式的證明)
把每條無向邊 取代為弧 與 ,每條弧容量為一。一個有向割對每條無向邊界邊恰有一條向外的弧,所以最小割容量等於最小邊分隔集的大小。取一個整數最大流。
方向相反的兩條弧可能各承載一個單位的流。把兩者流量中較小者從兩條弧上同時減去。在每個端點處,流入與流出被減去相同的量,所以守恆性與淨值都不變。全部抵銷之後,每條原有的邊至多有一個方向的流為正。把這個流分解為路徑。由於弧的容量為一,提取出的路徑使用互不相同的弧;又因為相反方向的正流已被消除,它們也使用互不相同的無向邊。反過來,把任意一族邊互不相交的路徑沿從 到 的方向定向,就得到一個同樣值的可行流。最大流最小割定理即證明了等式。
證明
(內部頂點形式的證明)
記 ,並使用有向的拆點網絡。保持 不拆。把其餘每個頂點 取代為 ,二者之間由一條容量為一的有向弧相連。對每條無向邊,加入兩個方向的對應弧,即從一個端點的輸出副本指向另一個端點的輸入副本,每條容量為 。對於未拆分的端點,其輸入副本與輸出副本都表示原來的端點。
整數流可分解為路徑,而每次經過內部的原有頂點都必須穿過其容量為一的拆點弧。因此提取出的路線是內部頂點互不相交的。反過來,這樣的一族路徑給出一個整數流;當端點不相鄰時,每條路線至少使用一個內部頂點,所以其大小至多為 。容量 對每條鄰接弧都足夠大。
刪去全部 條拆點弧會使源點與匯點不連通。在此刪除之後取可達集割,得到一個容量至多為 的割。因此,最小割不可能包含容量為 的向外鄰接弧。所以它向外的弧只能是拆點弧。設 為這些弧所對應的原有頂點。割的容量是 ,而任何避開 的原有路徑都會提升為網絡中一條不穿過任何割弧的路徑,這是不可能的。因此 是一個內部頂點分隔集。最大整數流提供了同樣數量的不相交路線,證明完畢。
證明透視
把容量限制與證明對象的提取分開
頂點證明有三個運作部分。第一,每條拆點弧 上的單位容量是唯一強制不相交的地方。
第二,關鍵一步是鄰接弧上的容量 。它只在解碼最小割時用到:僅由拆點弧已可得到容量至多為 的割,所以任何最小割都承擔不起一條鄰接弧。最小割的向外弧都是拆點弧,它們確定一個頂點集 ,其大小就是割的容量。
第三,不相鄰假設恰好在這一點進入。若 ,刪去全部拆點弧後弧 仍然存在,上界 不再可用,每個割都要為這條弧付出容量。整數最大流最小割等式經由兩個轉換(流到路線、割到分隔集)完成證明。
例題詳解
例題 9.2.5
(兩條邊路線共用一個脆弱頂點)
取路徑 與 ,圖中恰好只有這八條邊。它們沒有公共邊,所以存在兩條邊互不相交的路線。與 關聯的兩條邊構成一個邊分隔集,由此證明邊的最優值為二。然而每條路線都經過 ,所以 是一個內部頂點分隔集。又因為存在路線,所以頂點的最優值恰為一。邊的獨立性並不蘊含頂點的獨立性。
例題 9.2.6
(三個獨立的中間選擇)
把 中的每一個都與 和 相連,且沒有邊 。經由三個不同中間頂點的三條路徑是內部頂點互不相交的。刪去全部三個中間頂點就能分隔端點,而只刪去兩個則仍留下一條路線。在拆點網絡中,有三條容量為一的內部弧,鄰接容量為 。最大流與最小割的值都是三。三條路徑共用源點與匯點,這正是定理所容許的。
例題 9.2.7
(路徑長度不是選取問題的目標)
取五圈 。它提供了路線 與 ,長度分別為三和二。它們既是內部頂點互不相交的,也是邊互不相交的。 處的邊界有兩條邊,而刪去內部鄰點 會使 孤立。因此兩個局部分隔集的最優值都是二。一個最大的路徑族不必由同樣短的路徑組成,該定理也不會最小化它們的總長度。
為甚麼抵銷要先於邊分解
有向流把有向弧視為相互獨立的資源。在無向模型中,沿一個方向走過一條邊與沿相反方向走過這條邊,使用的仍是同一條底層邊。如果在處理這一區別之前就進行分解,就可能得到作為有向弧列表互不相交、卻違反所需無向要求的路徑。
抵銷在不改變目標的情況下修正了模型。它去掉的是一個由兩條弧構成的環流,而不是有用的淨運輸。一旦只剩下一個正方向,隨後的分解只做減法,永遠不會產生新的相反方向。因此提取出的路徑在原圖中仍然邊互不相交。這是一個正確性步驟,而不僅僅是為了讓路線顯示得更整齊。
內部不相交意味著端點可以重複使用
如果對每個頂點(包括源點)都以單位容量拆點,整個答案就會被限制為一。端點被有意地豁免,因為每條所選路線都必須使用它們。同樣,內部分隔集排除端點:否則刪去源點就會使每個連通的實例變得平凡。
不相鄰假設使得最小分隔集的陳述在這一約定下有意義。它還為歸約中大容量的選取提供了有限的上界:全體內部頂點合起來是一個有效的分隔集。如果端點之間有直接的邊,這個集合就不能分隔它們,證明中關於小割的論證恰好在相應之處失效。
反例模式
相鄰的一對端點沒有內部頂點分隔集
在頂點為 的三角形中,路徑 與 是內部頂點互不相交的。它們的最大條數是有限的,即二。但是,在唯一的內部頂點集 的任何子集中,都沒有能摧毀直接邊 的。因此所述的分隔集最小值並不存在。修正後的頂點定理假設端點不相鄰;邊定理則不需要這樣的限制。
局部證明與全局邊連通度的陳述
如果每一對頂點之間都至少有 條邊互不相交的路徑,那麼刪去少於 條邊後,每一對頂點仍然連通。每條被刪去的邊至多破壞某個特定不相交族中的一條路線,所以至少有一條路線倖存。反過來,如果刪去少於 條邊總是使圖保持連通,那麼每個局部邊分隔集的大小都至少為 。於是 Menger 定理對每一對頂點都給出 條邊互不相交的路線。
當圖至少有兩個頂點時,這就給出了有限 -邊連通性的精確詮釋。該陳述針對所有頂點對。單獨一對高度連通的頂點並不能證明整個圖是高度連通的:另一個頂點可以只透過一條橋接入,而第一對頂點仍然保有許多備選路線。
一個簡單的必要局部界是各端點的度。邊互不相交的路線需要不同的第一條邊,所以它們的數量至多等於任一端點的度。對於不相鄰的端點,內部互不相交的路線還需要不同的第一個內部頂點。這些界是快速的阻礙,但它們並不能證明相應的下界;圖內部更遠處的瓶頸可能更小。
貪心地刪除路徑可能丟失最優解
找到一條路線並永久刪去它的全部內部頂點,並不能自動構造出最大的路徑族。在邊為 的圖中,選取 會刪去兩個內部頂點,從而不再留下路線。然而 與 構成一個大小為二的族。因此,極大族可以比最大族更小。
殘餘算法可以修正先前的決定。當不再有殘餘改進時發現的分隔集是一個數學證明;而在不可逆的貪心刪除之後找不到另一條路線則不是。這一區別類似於極大配對與最大配對的區別,每當某個選取問題誘使人採用局部選擇規則時,它都是一個有用的警示。
常見錯誤
常見錯誤
(通行容量太小會隱藏分隔集)
拆點網絡中鄰接弧的容量必須嚴格大於已知的分隔集上界,例如 。容量取一時,最小割可能全由通行弧組成而不指出任何頂點,路徑 即為一例。
大小相等的路徑族與分隔集可以獨立於其尋找方式來證明最優性。只展示若干條路線而沒有上界,只證明了可行性;只展示一個小分隔集而沒有路線,只證明了一個阻礙。
總結
整數流經過相反方向的抵銷與路徑分解後,成為邊互不相交的路線。拆點用來保證內部不相交,而很大的通行容量使最小割可以解碼為頂點分隔集。這些假設把真正的連通度等式與端點相鄰時的例外情況以及貪心失敗區分開來。
練習
快速檢查
(取邊為 的圖。求兩種局部不交路徑選取的最優值以及相應的分隔集。)
源點的度為二,但通向匯點的最後一條邊只有一條。
解答 · 答案
每條 – 路線都使用 ,所以邊裝入至多為一; 達到一。單獨一條邊 是最小邊分隔集。每條路線也都使用內部頂點 ,所以內部頂點裝入與分隔集的大小都是一,由同一條路線與頂點集 證明。僅憑端點的度為二,並不能推出存在兩條路線。
快速檢查
(證明下面兩個條件的全局等價:刪去少於 條邊的任何操作後圖仍然連通;每一對頂點之間都有 條邊互不相交的路徑。)
假設圖是至少有兩個頂點的有限圖,且 為整數。
解答 · 答案
如果每一對頂點都有 條邊互不相交的路線,那麼少於 條邊的被刪集合不可能與任何一對頂點的全部路線都相交,所以剩下的圖是連通的。反過來,如果所有這樣的刪除都保持連通性,那麼沒有任何一對頂點的邊分隔集的大小小於 。因此邊定理對每一對頂點給出至少 條不相交路線。結論是逐對地同時具備可用性,而不是要求所有頂點對所選取的路徑族彼此互不相交。
快速檢查
(為甚麼每條通行弧的容量都取一,可能無法把最小割解碼為內部頂點分隔集?請使用路徑 。)
有效的流值與正確詮釋的割是兩個獨立的要求。
解答 · 答案
在單位通行容量下,對應 的拆點網絡有一個源點側恰為 的割。它穿過指向 的通行弧,容量為一,且是最小割。它不穿過任何內部拆點弧,因此所提出的被提取的頂點集將是空集,而空集並不能分隔原來的路徑。把通行容量取得大於已知的內部分隔集上界,就能避免這樣的割成為最小割。