從找出割點到理解全圖
兩個三角形若恰好共用一個頂點,就沒有橋,但刪除公共頂點會使它們分開。因此橋森林不能描述所有單頂點故障。僅有一張割點清單也不夠:它告訴我們哪些頂點脆弱,卻沒有說明這些頂點把哪些部分連在一起。
這裏需要的部分可以重疊。在上述例子中,每個三角形都應保留為一個部分,所以公共割點必須同時屬於兩者。下面精確定義這些部分,證明它們的連接方式是一片森林,再用森林回答:除了指定的兩個端點之外,哪些頂點能在單獨刪除時將它們分開?
本節 是有限簡單無向圖,容許不連通圖和空圖。用 表示連通分支數。刪除頂點時也刪除其所有關聯邊。
定義 9.1.1
(割點)
若 ,就稱頂點 為圖 的割點。
空圖有零個分支;單頂點圖沒有割點。
可以共用頂點的部分
定義 9.1.2
(塊)
的一個塊是沒有割點的連通子圖,且在具有這兩個性質的子圖中按包含關係極大:它不是 中另一個沒有割點的連通子圖的真子圖。
常見錯誤
(極大不等於最大)
「極大」表示子圖無法再擴大而保持兩個性質,並不表示它在所有候選中頂點最多。在三角形 加上懸掛邊 的圖中,單條邊 連同兩端點是一個塊,雖然它的頂點比三角形少:任何真包含它的連通子圖都含有 以及 在 中的某個鄰點,此時 是割點,把 與該鄰點分開。
定義包括兩種小情形。一條邊連同其兩個端點沒有割點,因為刪除任一端點後仍留下連通的單頂點圖。孤立頂點自身也構成一個塊。
定義 9.1.3
(2-連通圖)
若一個圖至少有三個頂點、連通,且刪除任一頂點後仍連通,就稱它為 2-連通圖。
因此,至少有三個頂點的塊是2-連通圖;小塊則需要另外說明約定。
每個塊都是其頂點集上的誘導子圖。在同一頂點集內補上一條缺失邊,不會破壞原來的連通性,也不會破壞刪除任一頂點後的連通性。若候選不是誘導子圖,就還可以擴大,違反極大性。有限性還保證:任何沒有割點的連通子圖都可擴充成一個塊,只需在還能擴大時繼續擴大,過程必定停止。特別地,每條邊至少屬於一個塊。
反例模式
塊並不劃分頂點集
設兩個三角形的邊集分別為 和 。並圖有割點 ,所以並圖不是一個塊。兩個三角形正是它的塊,都包含 。若強行把每個頂點只分配給一個部分,就會抹去其中一個連接關係。相比之下,稍後將證明每條邊恰好屬於一個塊。
在一個割點處分開問題
關鍵證明使用較小的圖,而不預先假定塊應如何連接。
定理 9.1.4
(割點把塊問題分成較小問題)
設 連通, 是割點。令 為 的各連通分支的頂點集,其中 ,並令
每個 連通,頂點數小於 ,且至少有兩個頂點。 的塊恰好就是這些 的塊,沒有重複。
證明
(塊在割點處分開的證明)
每個 內都有 的鄰點,否則 不連通。因此 連通。各部分只共用 ,不同 之間沒有邊。
取任意沒有割點的連通子圖 。若 同時包含不同 中的頂點,其連通性迫使它包含 ;但 在這兩個分支中仍有頂點,彼此沒有路徑。因此 成了 的割點,矛盾。所以 必須包含在某個 中。單頂點子圖 雖包含在每一部分內,卻在任何一部分中都不極大,因為每個 都有一條與 關聯的邊。
於是, 的每個塊包含在某一部分中,且在該部分內也必須極大。反過來,取 的塊 。由於 連通且至少有兩個頂點, 必有一條邊。若 中有更大的無割點連通子圖包含 ,前面的論證說明它仍須包含在某個部分中; 的那條邊迫使該部分就是 ,違反 在其中的極大性。不同部分的塊也不能相同,因為各塊有邊,而各部分的邊集互不相交。
證明透視
為甚麼分割後仍能保留極大性?
證明由兩步支撐。第一步是分離:與 的兩個不同分支都相交的連通子圖必須經過 ,而此時 是該子圖的割點。這裏用到 正是 的連通分支,所以 中沒有邊連接其中兩個。因此 的每個沒有割點的連通子圖都落在單一部分 內。
第二步是識別。各部分的頂點集在 處重疊,所以頂點無法說明一個塊屬於哪一部分;但各部分的邊集互不相交。由於每個 連通且至少有兩個頂點,其每個塊都有一條邊,這條邊把任何可能的擴大固定在同一部分內。於是 中的極大性與 中的極大性在同一個固定部分內比較,兩個方向都由此完成。唯一落在每一部分內的子圖是單頂點 ;因為 在每個 中都有鄰點, 從不極大,所以它不會造成問題。若沒有分離這一步, 的塊原則上可能經過 延伸到 ,遞歸描述便說明不了 的塊。
構造關聯森林
定義 9.1.5
(塊關聯圖)
的塊關聯圖 是一個二部圖,節點分為兩類: 的每個原頂點各有一個節點,每個塊另有一個新節點。當且僅當 時,連接頂點節點 和塊節點 。
兩類節點始終區分;即使原圖恰有一個頂點也名為 ,它也不等於塊節點。
定理 9.1.6
(塊關聯森林)
是森林,其連通分支與 的連通分支一一對應。 的每條邊恰好屬於一個塊;兩個不同的塊至多共用一個頂點。
證明
(分割再黏合樹的證明)
對 的每個非空連通分支分別按頂點數歸納。若它沒有割點,整個分支就是唯一的塊,關聯圖是星形樹;邊的唯一歸屬及交集結論也成立。單頂點分支包括在內。
否則,在割點 處按上面的方式分割。每個較小的 都滿足歸納假設。分割定理說明它們的塊正好是 所需的塊;不同部分沒有公共邊,只共用原頂點 。因此這些關聯樹恰好共用節點 。將若干棵樹在同一個節點黏合仍是樹:結果連通;一個簡單圈不可能離開某棵樹後只經由同一公共節點返回而不重複該節點。邊的唯一歸屬在每一部分內部由歸納成立,在不同部分之間由邊集不交成立。不同塊在同一部分內至多共用一個頂點,在不同部分內也只能共用 。所有結論得證。對於空圖,塊集和 都為空。
概念視角結構
把塊看成邊的等價類
若兩條邊相等或位於同一個圈上,就稱它們相關。圈是連通且沒有割點的,所以它包含於某一個塊中;由邊的唯一性,相關的邊屬於同一個塊。反過來,2-連通圖中任意兩條邊都位於同一個圈上,這是一個標準事實,本節不證明。因此這個關係是等價關係,其等價類恰好是含邊的塊的邊集;一條橋自成一類。這種以邊為本的描述只遺漏孤立頂點這種塊。
定義 9.1.7
(塊割森林)
的塊割森林是 中由全部塊節點以及屬於至少兩個塊的原頂點節點所誘導的子圖。
下面將證明後者恰好就是割點。暫時使用完整的關聯森林 ,好處是每個可能的路徑端點都已經有對應節點。
從唯一路徑讀出頂點故障
設不同頂點 和另一個頂點 屬於 的同一分支。比較刪除 後兩張圖中的連通性。 中的一條路徑給出 中的遊走:將路徑的每條邊 替換成 ,其中 是該邊唯一所屬的塊。反過來, 中的路徑交替經過頂點節點和塊節點。把每段 替換成 內避開 的一條 – 路徑。如果 ,使用 的連通性;如果 ,使用 沒有割點的性質。兩個不同的端點都保留下來,保證 非空。拼接得到 中的遊走,再刪除重複部分即可得到路徑。
定理 9.1.8
(每個分離頂點都有路徑證據)
設 在 中連通,且 。刪除 分開 ,當且僅當原頂點節點 位於 中唯一的 – 路徑上。
證明
(經由路徑對應的證明)
若 不在包含 的分支中,刪除它不影響兩者的連通性,其節點也不在兩者的關聯樹路徑上。否則,前面的對應說明, 中有 – 路徑當且僅當 中有這樣的路徑。在樹中,刪除一個節點會分開另外兩個節點,當且僅當它位於兩者的唯一路徑上。對 中相應的樹應用此性質即可。
這裏有意排除了刪除端點的情況:刪掉 後,不再有一對都存活的頂點供我們比較連通性。原來 連通的條件也不可省。
若 不是孤立頂點,則其原關聯樹中, 的每個分支都含有存活的原頂點。該分支的第一個節點是一個包含 的塊;塊至少有兩個頂點,另一個成員就在該分支內。由同樣的路徑對應,刪除 後,它原來的分支恰好分成 個分支。因此
常見錯誤
(割點不一定只把分支分成兩部分)
刪除一個割點可能產生多於兩個新部分,上式正好計算其數目:在星圖 中,中心屬於三個橋塊,故 ,刪除它後留下三個孤立頂點,分支數增加二。把「割點」理解為「恰好分成兩部分」會少算;計算屬於四個塊的頂點被刪除後的分支數時,也會犯同樣的錯。
所以,頂點是割點當且僅當它屬於至少兩個塊。孤立頂點只屬於自己的單頂點塊,刪除它卻有 ,故它不是割點。從 中刪除其餘原頂點節點,只是逐一刪去葉節點。因此緊湊的塊割圖確實是一片森林,原圖每個分支對應一棵樹;沒有割點的分支對應單個塊節點。
對照三個例子
例題 9.1.9
(橋森林看不見公共頂點)
對於三角形 ,完整關聯樹有路徑 ,另有葉節點 。緊湊樹是 。因此,除端點 外,只有刪除 能分開 。每條邊都在某個三角形上,沒有橋,故橋森林只有一個節點。兩種答案並不矛盾:橋森林描述邊故障,塊則描述頂點故障。
例題 9.1.10
(三角形、尾巴和孤立頂點)
取三角形 、邊 和孤立頂點 。各塊的頂點集是 。非平凡的緊湊樹為
另有代表 的單獨節點 。所以恰有 能分別分開 。刪除 後,全圖有三個分支:、 和 。由於 屬於兩個塊,,公式給出 。若刪除 ,分支數卻從二降到一,這正是孤立頂點的例外。
例題 9.1.11
(兩個重疊的圈未必是兩個塊)
取共用邊 的三角形 。整個四頂點圖沒有割點:刪除 或 留下三角形;刪除 留下路徑 ;刪除 留下路徑 。所以全圖只有一個塊,而不是兩個三角形塊。各三角形雖然沒有割點,卻不極大。真正不同的塊不可能共用一條邊,甚至不能共用兩個頂點。
計數與有限構造
設 、、,塊數為 。完整關聯森林有 個節點、 個分支及 條邊。森林的邊數公式給出
第二個等式來自邊的唯一歸屬。上面的帶尾巴例子中,第一個和為 ,第二個和為 。這些等式可用於核對候選清單,但數值吻合本身不能證明各部分沒有割點或具有極大性。
證明還給出有限構造:逐個處理連通分支;若當前圖沒有割點,就輸出它;否則選一個割點,分成上述誘導部分並遞歸處理。每個子問題頂點更少,所以遞歸終止。必須保留原頂點標籤,因為割點本來就會出現在幾個遞歸部分中。可用前文的 DFS 判別尋找割點。這裏證明了構造正確,卻沒有證明在重疊部分中反覆搜尋具有線性時間界;專門的邊棧實現需要另外分析。
練習與解答
快速檢查
(求路徑 的全部塊。哪些頂點分開 ?)
檢查連續兩條邊能否同時位於一個沒有割點的連通子圖中。
解答 · 答案
每條邊各是一個塊。任何包含連續兩條邊的連通子圖,都以兩邊的公共頂點為割點,因此不能成為更大的塊。緊湊樹為 ,所以恰有 分開兩端。
快速檢查
(至少有兩個頂點的連通圖中,一個頂點屬於四個塊。刪除它後有多少個分支?若原來另外還有兩個連通分支呢?)
使用關聯森林的度數公式。
解答 · 答案
關聯度數為四,所以它原來的分支分成四部分。不連通情形中,另外兩個分支保留,總數為六。兩種情形的分支數都增加三。
快速檢查
(證明:兩頂點塊恰好是橋及其端點。)
兩個方向都要論證:不是橋的邊位於某個圈上;較大塊中的橋會產生割點。
解答 · 答案
兩頂點塊只包含邊 。若它不是橋,就有避開該邊的 – 路徑,連同 組成一個圈。圈沒有割點,會擴大候選塊,矛盾。反過來,橋屬於某個塊。至少三個頂點的無割點連通圖不可能有橋:刪除橋將頂點分為兩個非空側;至少一側有兩個頂點,刪除該側的橋端點後,該側剩餘頂點與另一側分開。因此包含橋的塊只能有橋的兩個端點。
快速檢查
(連通圖有四個塊,頂點數分別為 。求全圖頂點數。邊數也能確定嗎?)
使用森林計數 。
解答 · 答案
由公式,,所以 。邊數不確定:四頂點塊可以是四邊形圈,有四條邊;也可以是完全圖,有六條邊。在兩種構造中按同樣方式接上一個三角形塊及兩個橋塊,各部分仍是塊,但總邊數相差二。
快速檢查
(設 是兩個原本連通的不同頂點。它們能否同時屬於兩個不同塊?若刪除任意一個其他頂點後它們都仍連通,能否不屬於任何公共塊?)
觀察 中 – 路徑的內部節點。
解答 · 答案
第一個答案是否定的,因為不同塊至多共用一個頂點。第二問先假設兩頂點原來連通。若關聯路徑內部有原頂點節點,它就是一個分離頂點;若沒有,路徑只能是 ,所以兩頂點屬於同一個塊。因此所述單頂點穩健性蘊含公共塊。相鄰端點可能只共用一個橋塊:刪除其他頂點不會刪掉它們之間的邊,故這個結論不能推出相鄰端點間有兩條內部頂點不交的路徑。