網絡失去一條連線後可能仍然連通;樹則處於另一極端:它連通,而且每條邊都不可缺少。本節說明這個局部性質與不含圈的整體性質為何等價。
定義
定義 1.1.1
(遊走、路徑、圈與橋)
有限簡單無向圖是二元組 ,其中 有限, 由 的二元子集組成。遊走是相鄰頂點依次相接的頂點序列;路徑是不重複頂點的遊走。長度為零的路徑把頂點與自身連接。若任意兩頂點之間都有路徑,圖就是連通的。圈是長度至少為三、除首尾相同外不重複頂點的閉遊走。刪除邊 後若連通分支數增加,便稱 為橋。
定理 1.1.2
(橋的判別法)
一條邊是橋,當且僅當它不屬於任何圈。
證明
(繞圈改道的證明)
設 。若 屬於某圈,去掉它後圈的其餘部分仍給出一條由 到 的路徑。把任意遊走中經過 的部分換成此路徑,再刪去重複段,便得到不經過 的路徑。因此刪除 不會拆開原來的分支。反過來,若 不是橋,刪除後 仍然連通;否則原來包含 的分支會分裂,因為其兩側之間原有的每條路徑都必須經過 。取一條不含 的 至 路徑,加上 就形成一個圈。
拼接路徑可能重複頂點,所以首先得到的是遊走。若有限遊走重複頂點,刪去該頂點兩次出現之間的一段;反覆操作便得到同端點的路徑。
定理/命題
定義 1.1.3
(樹與森林)
樹是至少有一個頂點的連通無圈有限簡單圖。森林是無圈圖;每個分支都是樹,孤立頂點也算一個分支。
定理 1.1.4
(樹的刻畫)
對有 個頂點的圖,下列條件等價:
- 圖是樹。
- 任意兩頂點之間恰有一條路徑。
- 圖連通且有 條邊。
- 圖無圈且有 條邊。
證明
(經由葉、生成樹與森林計數的證明)
在樹中,連通性保證存在路徑;若兩條不同路徑有相同端點,從首次分岔處走到下一次相遇處便形成圈。因此 (1) 推出 (2)。反之,圈上相鄰兩頂點之間有兩條路徑,所以唯一性排除圈,(2) 推出 (1)。
至少有兩個頂點的有限樹必有度為一的頂點,稱為葉。取最長路徑:端點不能有路徑外的鄰點,否則可以延長;也不能有路徑上其他鄰點,否則形成圈。刪去該葉及其邊後,剩下的圖仍連通且無圈:連接其餘頂點的路徑不能以葉為內部頂點。從單頂點樹開始歸納,得到樹有 條邊,故 (1) 推出 (3) 與 (4)。
任何有限連通圖都有生成樹:只要有圈,就刪去圈上一條邊。橋的判別法說明刪除後仍連通;邊數有限,所以最後得到連通無圈的生成子圖。它有 條邊,因此原圖若恰有這麼多邊,就等於其生成樹,即 (3) 推出 (1)。最後,森林若有 個分支,其頂點數分別為 ,則邊數為 。無圈且有 條邊便迫使 ,所以圖是樹,即 (4) 推出 (1)。
證明透視
每個推出關係用不同的工具
(1) 與 (2) 的等價只用到分岔論證:兩條端點相同的不同路徑含有圈,而一個圈提供兩條路徑。邊數依賴葉的引理,有限性正是在這裏、透過選取最長路徑而用到;歸納每次刪去一片葉和一條邊,並保持是樹。
逆命題需要的是構造而不只是計數。對 (3),生成樹是刪去圈上的邊得到的,而橋的判別法正好保證每次刪除都不會使圖不連通;生成樹有 條邊,原圖也不多於此數,所以實際上沒有刪去任何邊。對 (4),計數逐個分支進行,,而假設 迫使 。兩個逆命題中,邊數都只有與第二個性質((3) 中的連通性、(4) 中的無圈性)配合才起作用。
邊數條件中伴隨的性質都不能省去。
反例模式
只有邊數不能刻畫樹
這裏排除空圖,避免對空圖是否連通的約定產生歧義。只有 條邊還不夠:三角形加一個孤立頂點有四個頂點、三條邊,卻既不連通又含圈。
例題詳解
例題 1.1.5
(帶尾巴的三角形的橋與生成樹)
令 ,,其中以 簡記 。三角形的邊都在圈上,所以都不是橋; 不在任何圈上,是橋。刪去 得到路徑 ,它是一棵有三條邊的生成樹。刪去 卻會孤立 ,這說明了橋的判別法的作用。生成樹通常不唯一,例如刪去 也得到另一棵。
練習
快速檢查
(森林有 個頂點和 條邊,求分支數。)
解答 · 答案
由 得 。孤立頂點也要計作分支。
快速檢查
(連通圖有 個頂點和 條邊。證明它恰有一個圈。)
解答 · 答案
取生成樹 ,它有 條邊,所以圖中恰有一條不屬於 的邊 。樹中唯一的 至 路徑與 一起構成一個圈。任何圈都必須含樹外的邊,因此必須含 ;去掉 後剩下 中的一條 至 路徑,唯一性迫使它就是前述路徑。所以恰有一個圈。
向樹添加一條邊
定理 1.1.6
(向樹添加一條邊恰產生一個圈)
設 是樹, 是不相鄰的不同頂點。添加邊 後恰好產生一個圈,它由樹中唯一的 至 路徑與新邊構成。
證明
(由樹中路徑唯一性的證明)
樹中唯一的 至 路徑與新邊構成圈。擴充圖的任何圈都必須經過新邊,因為原樹無圈;去掉新邊後,圈餘下部分是樹中由 到 的路徑,樹的刻畫迫使它就是上述路徑。
這給出一種交換操作:刪去該圈上除新邊以外的任意一條邊,仍得到生成樹。確實,原來經過被刪邊的遊走可改走圈的其餘部分,因此圖仍連通;它有 條邊,所以是樹。這裏不能任意刪除圈外的邊。
概念視角結構
極小連通圖與極大無圈圖
樹恰好是極小連通圖:圖連通,而且每條邊都是橋;由橋的判別法,「沒有邊在圈上」與「每條邊都是橋」說的是同一件事。對偶地,樹恰好是極大無圈圖:圖無圈,而且在任意兩個不相鄰頂點之間加邊都會產生圈,這是上面的定理。反過來,極大無圈圖必定連通,因為連接兩個分支的邊不會產生圈。
例題 1.1.7
(路徑上的一次交換)
從路徑 開始,添加 ,唯一的圈為 。刪去 後得到邊 ;新樹中從 到 的唯一路徑為 。如果原樹另有葉 ,僅以 相連,那麼 不在這個圈上,刪去它會孤立 。
計數與構造是不同的問題
常見錯誤
(未知無圈就使用森林計數)
公式 用來計算森林的分支數,使用前必須先知道圖無圈。例如兩個不相交的三角形有六個頂點、六條邊和兩個分支,而 。圈上的邊增加了冗餘,卻不改變連通性,因此僅靠邊數不能看出分支結構。
不用枚舉所有邊的子集也能構造生成樹。從連通有限圖的一個頂點出發,每次選擇恰有一個端點已到達的邊,加入另一端點。只要仍有未到達頂點,這種邊就存在:取一條從已到達頂點到未到達頂點的路徑,選它首次離開已到達集合的邊。每步增加一個頂點和一條邊,且新頂點在構造出的子圖中只有一條邊,所以不會產生圈。最終得到生成樹。不同選擇可能得到不同的樹;這並不保證總權重最小。
例題 1.1.8
(從同一頂點長出的兩棵生成樹)
對正方形 加對角線 ,從 開始,依次選 ,得到一棵生成樹;選 又得到另一棵。沒有指定權重及優化算法,就不能斷言哪棵最便宜。
補充練習
快速檢查
(一棵樹有 個頂點,向兩個原本不相鄰的頂點間添加一條邊。要恢復同頂點集上的樹,須刪去多少條邊?哪些邊可以刪除?)
解答 · 答案
擴充圖有 條邊,而同頂點集的樹有 條,因此恰須刪去一條。刪去新邊或唯一圈上的任意邊都可以,因為圈的其餘部分保持其端點連通。刪去圈外邊不行:刪去它會把原樹分成兩部分,而新邊的端點仍在同一部分,因為原來連接它們的路徑不經過被刪邊。
快速檢查
(證明至少有兩個頂點的樹至少有兩片葉。)
解答 · 答案
取最長路徑。前述證明適用於它的兩個端點,所以兩端度數都是一;由於樹至少有兩個頂點,它們互不相同。這裏有限性不可省略:雙向無限路徑沒有葉。
樹中的度數計數
有限簡單圖的每條邊對兩個端點的度數各貢獻一,因此 。對 的樹,減去每個頂點的 得到
設葉的數目為 。每片葉貢獻 ,度為二的頂點貢獻零,度至少為三的頂點貢獻正整數,所以
這比至少有兩片葉更強:一個度為四的頂點迫使至少有四片葉。公式必須排除單頂點樹:其唯一頂點度數為零,貢獻 ,而不是葉所貢獻的 。
例題 1.1.9
(一個度為四的頂點迫使的葉數)
一棵樹恰有一個度為四的頂點,其餘頂點度數為一或二。公式給出 。它不能確定度為二的頂點有多少:細分任何一條邊都會插入一個度為二的頂點,卻不改變葉數。五頂點星形樹與細分其中一條邊所得的樹都符合條件。
快速檢查
(一棵樹有六片葉、兩個度為三的頂點、一個度為四的頂點,其餘頂點度數為二。這些度數能否出現?)
解答 · 答案
葉數公式要求 ,所以計數相容。要證明存在而不僅是必要條件相容,可以把度為四的頂點與兩個度為三的頂點及兩片葉相連,再在每個度為三的頂點上各接兩片葉。所得連通無圈圖具有指定度數;細分邊可加入度為二的頂點。單憑數值恆等式相容不能證明存在。
常見錯誤
常見錯誤
(證明無圈時先假設路徑唯一)
證明關於樹的結論時,要分清兩個定義性質各自起甚麼作用。連通性保證路徑存在,卻不能單獨保證路徑唯一:三角形相鄰頂點之間有兩條路徑。無圈性保證已有路徑的唯一性,卻不能保證不同分支之間存在路徑。在證明連通圖無圈時先假設路徑唯一,就是循環論證。
單頂點圖同時滿足兩個條件且沒有邊,是邊數歸納證明的起點。對森林,這些推理必須分別應用於每一個連通分支,孤立頂點也不例外。