動機
局部路徑定理比較的是一對選定的頂點。全局頂點連通度則問:當少量頂點失效時,整個圖是否仍然連通。兩種觀點互相關聯,但局部分離集定理中「端點相鄰」的例外情形不能簡單忽略:刪除內部頂點永遠無法去掉連接兩個端點本身的那條邊。
我們會明確處理這個例外,從而對全局連通圖中的每一對頂點都得到互不相交的路徑。第二個構造把單一目的地換成一個可能目的地的集合,得到一個扇:其中各條路徑只在公共起點相交,且終點是目標集中互不相同的頂點。證明會說明,為甚麼圖的階數和不同目標的數目都必須寫入假設。
下文唯一引用的結果,是上一篇筆記中已證明的、有限圖且端點不相鄰的頂點版 Menger 定理;我們並不假設任何更強的全對頂點命題。
定義
定義 9.3.1
(全局頂點連通度)
設 為有限簡單無向圖, 為整數。若 ,且刪除任意少於 個頂點後所得的圖仍然連通,則稱 是 -頂點連通的,此處簡稱 -連通。刪除操作指去掉所選頂點及其所有關聯邊。
路徑均指簡單路徑。若從 到 的一族路徑中任意兩條只共享端點,則稱它們內部頂點互不相交。這些路徑必須互不相同;直接相連的那條邊在這樣的路徑族中至多只能作為一條路徑出現。
階數條件排除了這樣的情形:在刪除所有有意義的頂點之後,圖變為空圖或單點圖,令判斷失去意義。按慣常約定, 個頂點的完全圖的頂點連通度為 。如果只檢驗不相鄰的頂點對,則對完全圖甚麼也說明不了,所以它不能單獨取代全局定義。
定義 9.3.2
(到目標集的扇)
對頂點 與目標集 ,由 到 的 -扇是由 條路徑組成的族:這些路徑都從 出發,終點是 中互不相同的頂點,且除 外兩兩不相交。我們另外要求每條扇路徑的內部頂點都不屬於 ;在第一個目標處截斷即可保證這個約定。
前面的局部定理指出:對於互不相同且不相鄰的兩個端點,內部頂點互不相交的路徑的最大條數,等於分離這兩個端點的、不含端點的頂點集的最小規模。下文應用該結果的所有圖都是有限簡單圖,並且滿足所需的不相鄰條件。
定理/命題
定理 9.3.3
(全局連通性等價於每一對頂點都有不相交的路徑)
設 。圖 是 -連通的,當且僅當任意兩個不同頂點之間都至少有 條內部頂點互不相交的路徑。該命題包括相鄰的頂點對。因此,-連通圖中每個頂點的度至少為 。
引理 9.3.4
(扇引理及其逆判據)
在 -連通圖中,對每個頂點 以及每個不含 且 的目標集 ,都存在由 到 的 -扇。
反之,若一個圖至少有 個頂點,且對每個頂點 與每個不含 的 元目標集都存在這樣的扇,則該圖是 -連通的。逆命題用到的是對所有目標集的全稱選取,而不只是某個特別有利的目標集。
概念視角結構
局部證書度量全局的刪除承諾
連通性對每一個小的失效集作量化。Menger 定理把這個承諾轉化為每對頂點之間許多獨立的路線。在下面的證明中,加入一個輔助目的地,把目標集轉化為單一頂點對的問題,再透過截斷恢復原來互不相同的目的地。輔助頂點只是證明的工具,並不是留在原圖中的額外資源。
度的結論是必要條件而非充分條件。同樣,某一對選定頂點之間有許多不相交的路徑,並不能推出全對性質。扇給出的是互不相同的目標終點;若容許所有路徑終止於同一個目標,則表達的是另一個弱得多的要求。
證明
證明
(每一對頂點都有不相交路徑,包括相鄰端點)
先設每一對頂點之間都有 條內部不相交的路徑。刪除滿足 的集合 ,並在 之外任取兩個頂點。每個被刪除的頂點至多出現在其中一條路徑的內部,所以被破壞的路徑少於 條,至少有一條倖存。因此其餘每一對頂點仍然連通,這就證明了全局刪除性質。
再設 是 -連通的。不相鄰的兩個端點不可能被其他少於 個頂點分離,所以由局部定理立即得到 條路徑。相鄰的端點則需要額外的論證。當 時,它們之間的邊就提供了所需的一條路徑。設 , 為一條邊,令 ,保留所有頂點。
我們斷言:不存在至多含 個其他頂點的集合 在 中分離 與 。假設存在這樣的 ,則 連通,而把單一條邊 加到 上就會連接它的各個連通分支。於是 恰有兩個連通分支,各含一個端點。剩下的頂點至少有三個,因為 。因此至少有一個分支在其端點之外還含有別的頂點。
若含 的分支有這樣一個額外頂點,則從 中刪除 。該額外頂點仍與含 的非空分支分離:兩個分支之間唯一的邊已經消失。由於 ,這與 -連通矛盾。若含 的分支有額外頂點,則刪除 ,同理得到對稱的矛盾。所以所設的分離集不存在。
在 中端點 不相鄰,於是局部 Menger 定理給出其中至少 條內部不相交的路徑。再加上原來的單邊路徑 ,就得到 中 條互不相同、內部不相交的路徑。這就證明了包含相鄰情形的全對等價性。
對於度的下界,假設某頂點的鄰點少於 個。刪除它的所有鄰點會令它成為孤立點,而階數條件保證還剩至少一個其他頂點。於是刪除少於 個頂點後圖就不連通,矛盾。
證明透視
刪去一條邊令局部定理得以適用
由路徑推出連通性的方向純屬計數:每個被刪除的頂點至多位於路徑族中一條路徑的內部,所以少於 次刪除不能破壞全部 條路線。另一方向包含唯一不顯然的一步。局部 Menger 定理要求端點不相鄰,而任何內部分離集都不能去掉邊 ,所以證明先刪去 ,並只要求在 中找到 條路線。
假設正是在 中分離集的下界處發揮作用。 的連通性用了兩次: 時它令 連通,所以 恰有兩個分支; 時它禁止刪除 或 。階數條件 只用了一次,保證 至少剩三個頂點,使某一側含有端點以外的頂點。若只剩兩個端點,刪去其中一個只留下單一頂點,得不到矛盾。最後把 恢復為第 條路徑;它的內部為空,所以與其餘 條路徑內部不相交,論證至此完成。
證明
(輔助目標頂點,再加上被迫的內部相遇)
對於扇引理,加入一個新頂點 ,使其恰與 的所有頂點相鄰。端點 不相鄰。設 是此擴充圖中不含 且少於 個頂點的任意集合。因為至少有 個目標,可取 。原圖 連通且含 ,所以存在由 到 的路線,再接上新邊到達 。因此 不能分離 。
在擴充圖中應用局部 Menger 定理,得到 條內部不相交的 到 的路徑。去掉它們通向 的最後一條邊,並在每條剩餘路徑第一次進入 時截斷。它們的終點互不相同,因為若有共同的目標,該目標就會是原路徑的內部交點。截斷保證它們的內部不含 中的頂點,且去掉後綴不會產生新的交點。這就是所求的扇。
對於逆命題,設刪除某個滿足 的 令圖不連通。在剩餘的一個連通分支中取 ,在另一個分支中取 。選一個包含 且不含 的 元目標集;圖的階數保證有足夠多的其他頂點來補足。任何到這個集合的 -扇都必須用到它的全部目標,包括 。但每條由 到 的路徑都必須經過 ,而 屬於目標集。路徑在到達 之前就會在內部遇到某個目標,違反扇的定義。這個矛盾排除了每個大小小於 的分離集,證明圖是 -連通的。
頂點失效不同於邊失效
刪除一個頂點可以同時破壞許多關聯邊。因此,一個圖可能沒有任何脆弱的單一條邊,卻有某個頂點,使兩個區域之間的所有路線都必須經過它。反過來,度的下界把局部的可用性與全局的韌性作了比較:內部不相交的路線必須從不同的鄰點出發,但鄰點足夠多並不能排除遠處的瓶頸。
這些定理在兩個方向上都給出了證書。一族路徑證明少於該數目的內部頂點刪除不能分離其端點。一個小的分離集證明全局連通性失敗。扇記錄的是到若干個分別指定的目標的更強的路由安排。這些對象應當作為實際的頂點序列來檢查,而不是憑圖中看起來分開的線條來推斷。
例題詳解
例題 9.3.5
(完全圖達到階數上限)
在 中,刪除少於 個頂點後至少剩下兩個頂點以及它們之間的所有邊,所以圖是 -連通的。對端點 ,取它們的直接邊,並對其餘 個頂點 各取兩邊路徑 。這恰好是 條內部不相交的路徑。每個端點的度為 ,所以不可能有更大的互異路徑族。直接邊雖然內部頂點集為空,但只計一次。
例題 9.3.6
(圈有兩條路線,但沒有任意的韌性)
對至少有三個頂點的圈,刪除一個頂點後得到一條連通的路徑,所以它是 2-連通的。在任意兩個端點之間,繞圈的兩個方向給出內部不相交的路徑。圈的度為二,所以當階數容許 3-連通圖的度條件時,它仍然不滿足;三角形也不滿足 3-連通所需的階數。長圈並不會僅因為頂點更多就具有更高的頂點連通度。
例題 9.3.7
(輪圖提供三個獨立的連接)
取一個至少有三個頂點的輪緣圈,以及一個與每個輪緣頂點都相鄰的輪心。若被刪除的至多兩個頂點不含輪心,則每個倖存的輪緣頂點仍與輪心相連。若輪心被刪除,則至多還有一個輪緣頂點被刪除,剩下連通的輪緣圈或輪緣路徑。因此輪圖是 3-連通的。
對於四個頂點的輪緣 與輪心 ,由 到 的 3-扇為:;;以及 。它們的目標終點互不相同,且唯一的公共頂點是 。這是對扇的明確檢驗,而不只是觀察到有三條路徑從源點出發。
常見錯誤
反例模式
最小度為二並不蘊含 2-連通
把兩個三角形在一個公共頂點 處連接起來,不再有其他重疊或邊。每個頂點的度至少為二,且刪除任意一條邊後圖仍然連通。然而刪除 會把一個三角形的另外兩個頂點與第二個三角形的另外兩個頂點分開。該圖連通,但不是 2-頂點連通的。無論選取哪些邊,位於兩個三角形相對兩側的頂點之間的所有路線都必須經過同一個割點。
常見錯誤
(把直接邊計算多於一次)
內部不相交的路徑族是一組互不相同的路徑。單邊路徑 的內部為空,所以它與其他每條路徑都不相交,但它仍然只是一條路徑:把它列出兩次並不會增加條數。在 中條數恰為 :一條直接邊加上 條兩邊路徑。
常見錯誤
(讓扇路徑共用目標)
到 的 -扇終止於 中 個互不相同的頂點。由 到同一目標 的多條內部不相交路徑表達的是頂點對 的局部 Menger 性質,那是另一個命題。在證明中,正是單一輔助頂點 (經最後一條邊由 到達)迫使截斷後的路徑終止於不同的目標。
常見錯誤
(只用一個目標集檢驗逆判據)
逆判據要求對每個起點和每個 元目標集都存在扇。在共享 的兩個三角形中,中心 到其中一個三角形另外兩個頂點有 -扇 與 ,但該圖並非 -連通。若起點的目標全是它的鄰點,就不能說明遠處的瓶頸。
總結
只要透過刪去並恢復端點之間的邊來處理相鄰端點,全局刪除定義就等價於每一對頂點之間都有不相交的路徑。輔助目標頂點證明了扇引理,而精心選取的目標集證明了它的逆命題。度、頂點韌性與邊韌性仍是不同的量,各有不同的證書。
練習
快速檢查
(證明:當 時,從 -連通圖中刪除一個頂點,所得的圖是 -連通的。)
檢查剩餘的階數,然後對進一步的刪除作量化。
解答 · 答案
刪除 之後至少還剩 個頂點,滿足 -連通對階數的要求。若 是剩餘頂點中少於 個頂點的任意集合,則 。原圖的保證令 連通。這恰好就是對 的刪除檢驗。該命題給出的是下界,而不是斷言連通度總是恰好減少一。
快速檢查
(在約定 個頂點的圖的連通度至多為 的前提下,證明具有至少三個輪緣頂點的輪圖的頂點連通度恰為 。)
把三角形輪緣與更大的輪緣分開討論。
解答 · 答案
例題中的證明對每個容許的輪圖都給出了 3-連通性。輪緣為三角形時,輪圖就是 ,其階數把連通度限制為三。輪緣至少有四個頂點時,每個輪緣頂點的度為三。刪除它的三個鄰點會令它成為孤立點,而且還剩至少一個其他頂點,所以連通度至多為三。結合已經建立的下界,兩種情形下連通度都恰為三。
快速檢查
(對共享頂點 的兩個三角形,求其頂點連通度與邊連通度。給出刪除證書,並證明所需的下界。)
這裏的邊連通度指令該連通圖不連通所需刪除的最少邊數。
解答
該圖連通且至少有兩個頂點,所以它的頂點連通度至少為一。刪除 會令圖不連通,由此證明該值恰為一。
刪除任意一條邊至多把一個三角形變為一條路徑;這條路徑仍透過 與另一個三角形相連,所以圖保持連通。因此邊連通度至少為二。刪除任一非中心頂點關聯的兩條邊會令該頂點孤立,而其他頂點仍然存在,由此得到規模為二的邊割。所以邊連通度恰為二。這個比較說明,即使沒有任何一條邊是橋,也存在真正的頂點瓶頸。