動機:最遠的頂點究竟有多遠?
連通圖保證任意兩個頂點之間都有路徑,卻不保證從哪裏出發都同樣方便。在一條很長的路徑上,一個端點離另一個端點很遠;從中間的頂點出發,到兩端的距離就比較均衡。要準確比較這些出發位置,我們先固定一個頂點,量度它到所有頂點的距離,再取其中的最大值。接下來才問:選擇哪個出發點,能夠使這個最大值盡可能小?
一般圖中可能有多條路徑互相競爭。樹中任意兩點之間只有一條路徑,分支無法提供捷徑。這個限制使我們能得到完整而明確的結論:任取一條直徑路徑,它的兩個端點就足以確定每個頂點的最遠距離;路徑的中間位置則確定整棵樹的中心。另一種證明會說明,為甚麼不斷同時刪除全部葉頂點,也能找到相同的中心。
距離與幾種不同的極值
本節的圖都是有限、簡單、無向、無權的圖。設 連通且至少有一個頂點。
定義 1.4.1
(連通圖中的距離)
兩點的距離 是所有 – 路徑中最少的邊數,並規定 。連通性保證距離有限。圖明確時可以省略下標。
距離具有對稱性,不同頂點之間的距離為正,並滿足三角不等式
證明時,把從 到 的最短路徑與從 到 的最短路徑接起來,得到長度等於右側的遊走。刪去重複部分後得到一條不更長的路徑。不等式不一定取等號,因為經過 的最佳路線未必是從 到 的最短路線。
定義 1.4.2
(偏心度、直徑、半徑與中心)
頂點的偏心度、圖的直徑、半徑與中心分別定義為
偏心度先固定一個端點再取最大值;直徑容許兩個端點都變化;半徑則是在每個出發點的最壞情況之間,選擇最好的出發點。中心是一個頂點集合,不是距離數值。由於頂點集有限且非空,這些極值都能達到。只有一個頂點的圖,直徑和半徑都是零,唯一的頂點就是中心。對於不連通圖,本節不定義有限的全圖半徑,可以分別研究它的各個連通分支。
定理 1.4.3
(一般連通圖的半徑與直徑界)
任意有限、非空、連通圖都滿足
證明
(直徑端點處的三角不等式)
選擇距離為 的兩個頂點 。對任意 ,三角不等式給出 。對 取最小值,再利用距離是整數,就得到左側。每個偏心度都不超過直徑,因此右側也成立。下面將證明:樹的半徑總能達到這個下界。這是樹的一條額外定理,不是半徑定義本身的內容。
一條直徑如何限制所有分支
設 是非空樹,取一條長度等於直徑 的路徑
記 、。這樣的路徑存在,因為最大距離能夠達到。樹中兩點之間的路徑唯一,所以直徑兩端之間的路徑也是最長簡單路徑。
每個頂點 在 上都有唯一的連接點 :從 走向 時第一次進入 的位置就是它,而且從 到 上任意頂點的路徑都會經過這個連接點。若 已經在 上,連接點就是 。為甚麼路徑 外分支的連接點唯一?刪除 的全部頂點後,任一剩餘連通分支都必須通過某條邊連接回 。如果有兩條不同的連接邊,無論它們在 上的端點相同還是不同,都能結合分支內的路徑及 的一部分構成圈,與樹無圈矛盾。路徑唯一性也說明,到 的路徑必須先經過連接點。
令 。於是到兩端的距離分別是 與 。二者都不能超過直徑,所以
這就是「直徑」一詞隱含的關鍵限制。長分支不能接在 的端點附近,否則它與另一端之間會出現更長的路徑。中間位置容許較長的分支,但分支高度仍同時受兩端約束。
定理 1.4.4
(兩個直徑端點決定全部偏心度)
設 是有限非空樹的任意一條直徑的兩個端點,則對每個頂點 ,
具體地,若 的連接點是 ,且 ,則
證明
(經由連接點估計每個距離)
固定 ,任取 ,分別記它們的連接點下標為 ,到連接點的距離為 。從 到 ,沿 到 ,再走到 ,得到長度為 的遊走。兩個分支重疊時,這條遊走可能往返經過一些邊,但仍然給出距離的上界。若 ,利用 得 ;若 ,利用 得 。因此
另一方面,,,其中至少一個恰好達到上界。對 取最大值,兩個公式都得證。若 ,樹只有一個頂點,各量都是零,證明仍然適用。
證明透視
直徑的極大性在哪裏用上
上界 是全部內容,而它建基於一個不等式。路線 只是一條遊走,所以只給出距離的上界,這一步不需要樹的性質。樹的性質經由連接點的唯一性進入,它使 與 有明確定義。 的極大性則經由分支界 進入,並在兩種情形中各用一次: 連接在 靠 的一側時用 ,靠 的一側時用 。下界毫無代價,因為端點 本身就實現了 與 。在圈上連接點並不唯一,下面四圈的反例正是從這裏逃脫。
推論 1.4.5
(樹的半徑與中心)
設 是有限非空樹 的一條直徑路徑。則 。若 ,中心是 ;若 ,中心是 。
證明
(直徑的中間位置)
偏心度公式把兩種代價分開了:離開直徑的代價是 ,沿直徑選擇位置的代價是 。後者在最接近 的整數位置達到最小值 。直徑外的頂點有 ,不可能達到這個最小值。
因此 。若 ,中心只有 ;若 ,中心是相鄰的兩個頂點 。樹可能有多條不同直徑,但上述論證用任意一條直徑都描述了由偏心度定義的同一個集合 ,所以它們的中間頂點或中間頂點對必定相同。
這裏容許選擇的位置是頂點。長度為五的路徑有兩個中間頂點,它們的偏心度都是三;連接這兩點的邊的內部中點,並不是一個偏心度為二點五的額外頂點。
概念視角算法
兩次搜尋找出直徑及其中點
連接點的估計還表明:離任意頂點最遠的頂點必是某條直徑的端點。因此從任意頂點作廣度優先搜尋,可找到一個滿足 的頂點 ;再從 搜尋,找到最遠的頂點 以及 – 路徑,它就是一條直徑路徑。由上述推論,其中間頂點或中間頂點對就是中心。兩次線性時間的搜尋因此算出與修剪相同的集合。
為甚麼刪除葉頂點不會改變中心
定義 1.4.6
(葉頂點與同時刪除)
葉頂點是度數為一的頂點。若樹 至少有三個頂點,同時刪除它的全部葉頂點,用 表示保留頂點導出的子圖。
至少有一個頂點被保留,否則至少有三個頂點的連通圖中,每個頂點的度數都至多為一,這是不可能的。兩個保留頂點之間的路徑也全部被保留,因為路徑內部的每個頂點至少有兩個鄰點。因此 仍是非空樹,保留頂點之間的距離不變。
定理 1.4.7
(一輪完整刪除使保留頂點的偏心度統一減一)
若樹 至少有三個頂點, 是同時刪去全部葉頂點後的樹,那麼對每個保留頂點 ,
證明
(每個被刪的葉頂點都掛在保留頂點上)
每個被刪去的葉頂點都有一個保留的鄰點,否則兩個相鄰葉頂點就會構成整個連通樹,與頂點數至少為三矛盾。因此對固定的保留頂點 ,到任意被刪頂點的距離至多為 ,到保留頂點的距離至多為 。這證明了 。
為證明等號,在 內選離 最遠的頂點 。若 不止一個頂點,則 ,且 在 中只有一個鄰點;否則可以沿另一個鄰點延長唯一的 – 路徑。但 被保留下來,說明它在 中的度數至少是二,所以它還有一個被刪除的葉鄰點。把這條邊接到路徑末端,就得到從 出發、長度為 的路徑。若 只有一個頂點,它在 中的鄰點全部被刪去,同樣得到結論,此時 。
還需要排除原中心被刪除的可能。設葉頂點 的唯一鄰點是 。從 到其他任意頂點的路徑都先到 。因為還有不同於 的第三個頂點,從 最遠的頂點可以選得不是 。於是 ,葉頂點不會使偏心度最小。原中心全部被保留,而所有保留頂點的偏心度都減少相同的數,因此最小值所在的頂點集合不變,中心也就不變。
證明透視
為甚麼一輪修剪令所有偏心度減少同一個數
頂點數的假設只用了一次:至少有三個頂點時,被刪的葉頂點不會只與另一個葉頂點相鄰,所以每個被刪頂點都經一條邊掛在某個保留頂點上,這給出上界。等號需要在 中最遠頂點之外還有一個被刪的葉頂點;該頂點是 的葉頂點(或唯一頂點),而它在 中度數至少為二。減少量對所有保留頂點相同,所以它們的大小次序和最小值點都不變。被刪的葉頂點則另行排除,因為每個都比其鄰點多一步。
算法與停止條件
如果只剩一個或兩個頂點,就全部返回。單頂點樹的唯一頂點是中心,雙頂點樹的兩個端點都是中心。否則同時刪除一整輪當前葉頂點,再重複。有限非平凡樹至少有兩個葉頂點:取最長路徑的兩個端點即可證明。因此過程一定終止。每輪保持中心不變,所以最終剩下的單頂點或相鄰頂點對恰好是原樹的中心。
使用鄰接表時,先計算當前度數,把葉頂點放入隊列。每輪先記下隊列當前長度,只處理這批頂點;更新保留鄰點的度數,把新出現的葉頂點加入隊列,留到下一輪處理。不能在本輪立即刪除新葉頂點。活動頂點數至多為二時停止,返回所有活動頂點;最後只剩一個頂點時,它的度數是零,也應被返回。每個被刪頂點只掃描一次,鄰接表中總共只有 個條目,因此度數更新、隊列操作和最後一次活動頂點掃描總計需要 工作量、 儲存空間。若每輪重新掃描所有頂點尋找葉頂點,就不能由上述論證得到線性時間界。
例題
例題 1.4.8
(有兩個中心頂點的路徑)
考慮 ,其直徑為五。由 ,按順序得到偏心度 。所以半徑為三,中心是 。第一輪刪除 ,第二輪刪除 ,然後在相鄰頂點對處停止。一個頂點屬於中心,並不表示它是唯一的最佳位置。
例題 1.4.9
(分支可以產生另一條直徑,而不移動中間頂點)
取路徑 ,把 連到 ,再把 連到 。原路徑長六。從 到任意路徑頂點的距離至多為 ;較淺的分支頂點,以及原路徑內部的頂點對,都不會給出更大距離。因此直徑仍為六,– 與 – 都是直徑路徑。公式給出 、、。中心是 ,它也是這兩條直徑的共同中點。分支長度很關鍵:若分支長得多,原路徑就不再是直徑。
例題 1.4.10
(度數並不能決定中心)
從 出發,把 接到 ,把 接到 。四個葉頂點是 ,而 的度數都是三。任意兩葉之間距離至多為三,且 ,所以直徑為三。 的偏心度都是二,每個葉頂點的偏心度都是三。一輪同時刪除四個葉頂點後,剩下中心邊 。再看一條很長的路徑:所有內部頂點的度數都是二,中心卻只有中間的一個或兩個頂點。局部度數並不記錄到遠端的距離。
反例與常見誤解
反例模式
圈會破壞樹的結論
在四圈 上,每個頂點的偏心度都是二。直徑與半徑都為二,四個頂點全是中心。直徑端點 到 的距離都是一,但 。因此,端點偏心度公式、,以及中心只有一個或兩個頂點的結論,都不能推廣到一般連通圖。這個圈沒有葉頂點,刪除葉頂點的算法也無法前進。樹的證明用到了唯一連接路徑,圈並不具備這個性質。
即使在樹中,刪葉規則也有一個容易被忽略的條件。
反例模式
立即刪除新葉頂點可能刪掉中心
在 上,先刪除 ,再刪除剛出現的葉頂點 ,接著刪除 。此時確實只剩兩個頂點,但剩下的是 ,原樹的中心卻是 。任意順序的逐個刪除不保持中心。正確的一輪必須在動手前確定本輪的葉集合:這裏兩輪分別是 與 。
常見錯誤
(直徑數的是邊,不是頂點)
直徑數的是邊,不是頂點:路徑 有六個頂點,直徑卻是五。距離始終由最短路徑定義;只是樹的直徑路徑同時也是最長簡單路徑。葉頂點未必是直徑端點:在第二道練習中,葉頂點 的偏心度是三,小於直徑四。
常見錯誤
(中心使最大距離最小,而非距離總和)
使最大距離最小,與使距離總和最小,是兩個不同的優化問題。在最後一題中,中心 的最大距離是二、距離總和是 ;而 的最大距離是三,距離總和卻較小,為 。
練習
快速檢查
(對路徑 ,求直徑、半徑、中心及 的偏心度,並列出每一輪同時刪除的葉頂點。)
解答 · 答案
直徑為八,半徑為四,中心是 ,且 。各輪依次刪除 、、、,留下 。每輪使用的是該輪開始時的葉頂點。
快速檢查
(在 上把一個新葉頂點 接到 。求中心與 。 是某條直徑的端點嗎?列出刪除輪次。)
解答 · 答案
直徑為四,由 – 達到,中點是 。 到 的距離都是三,因此 。直徑端點的偏心度必須等於直徑,所以這個葉頂點不是任何直徑的端點。先刪除 ,再刪除 ,剩下 。
快速檢查
(證明:任意有限非空連通圖的相鄰頂點都滿足 。它們的偏心度必須不同嗎?)
解答 · 答案
對每個 ,有 。取最大值得到 ;交換 得到另一側不等式。偏心度可以相等:雙頂點樹的兩個頂點偏心度都是一,四圈的全部頂點偏心度都是二。相鄰性限制差值,卻不保證每走一步都嚴格接近中心。
快速檢查
(在非空樹 的頂點 處接上一個新葉頂點 。證明新直徑為 。分別把葉頂點接到 的 與 ,求新中心。)
解答 · 答案
舊頂點之間的距離不變,因為新葉頂點不可能位於它們之間路徑的內部。舊頂點對給出的最大距離是 ;含 的頂點對給出的最大距離是 。所有頂點對都已包含,公式得證。五頂點路徑有 、,所以在 接葉頂點後直徑仍為四,中心仍為 。在 接葉頂點時,,新直徑為五;直徑路徑 的中間頂點是 ,即新中心。直徑公式先給出數值,再用一條直徑路徑確定中心。
快速檢查
(從 出發,在 處接上四個新葉頂點。找出中心,比較從 與從 出發到所有頂點的距離總和。中心一定使距離總和最小嗎?)
解答 · 答案
每個新葉頂點到 的距離是四,任意頂點對距離也不超過四。因此 – 是一條直徑,中心是偏心度為二的 。從 出發的距離總和為 ,最後一項來自四個新葉頂點。從 出發的總和為 。所以中心未必使距離總和最小: 的總和更小,但它的最大距離為三,比 的最大距離二更大。