動機
圖把連接的模式與它碰巧被畫成的樣子區分開來。樹刻劃了連通所有頂點所需的最少連接,而廣度優先搜尋則按到源點的距離來組織一般的圖。這兩個主題都體現了離散數學的一個核心方法:用局部不變量證明整體性質。
定義
定義 5.1.1
(圖、路徑、圈與樹)
有限簡單無向圖 具有有限的頂點集,其邊是由兩個不同頂點組成的無序對,且沒有重複的邊。路徑由互不相同的頂點組成,相鄰頂點之間有邊相連;其長度為邊的數目。圈包含至少三個互不相同的頂點,相鄰頂點之間有邊相連,並有一條邊回到起點。若任意兩個頂點之間都有路徑,則稱圖為連通。樹是連通且不含圈的圖;森林是不含圈的圖。頂點的度是與其關聯的邊的數目。
我們容許只有一個頂點的圖作為樹。在整個樹的定理中,。把每條邊在其兩個端點處各計算一次,便得到握手恆等式 。特別地,度為奇數的頂點個數是偶數,因為把該恆等式模 約化,所計算的正是這些頂點。
定理/命題
定理 5.1.2
(樹的等價描述)
對於有 個頂點的有限簡單圖,下列條件等價:它是一棵樹;任意兩個不同頂點之間恰有一條路徑;它連通且恰有 條邊;它無圈且恰有 條邊。
定理 5.1.3
(廣度優先搜尋求出無權距離)
在以鄰接表表示的有限圖中,從 出發,令 ,並把 放入先進先出隊列。重複地取出隊首頂點 ;對於 的每個尚未被發現的鄰點 ,令 ,記錄父頂點 ,並把 加到隊尾。恰好是從 可達的頂點被發現,而且每個標號都等於從 出發的一條最短路徑的長度。若計入對所有頂點記錄的初始化,運行時間為 。
證明思路
證明
(唯一路徑、葉與森林的邊數)
在連通無圈圖中,同一對端點之間若有兩條不同的路徑,它們就會包含一個圈,所以路徑是唯一的。反過來,圈給出了其上兩個頂點之間的兩條不同路徑;因此路徑唯一蘊含無圈與連通。
至少有兩個頂點的樹有葉,即度為一的頂點。取一條最長路徑:其端點若還有額外的鄰點,該鄰點要麼使路徑可以延長,要麼產生一個圈。刪去該葉後剩下的仍是樹。從一個頂點出發作歸納,即得恰有 條邊。每個有限連通圖都有生成樹:只要還有圈,就刪去圈上的一條邊,這樣連通性得以保持;該過程終止時得到一棵樹。因此,有 條邊的連通圖已經等於它的生成樹。最後,對於有 個連通分支的森林,在每個分支中應用樹的邊數公式,得到 。若 ,則 ,等價性證畢。
證明
(實際父路徑與隊列不變量)
至於 BFS,每個被發現的頂點的標號都對應一條經由父邊得到的、從源點出發的實際路徑,所以該標號不可能小於最短距離。隊列中的標號是不減的:在處理標號為 的頂點時,新加入隊列的標號為 ,排在所有已在隊列中、標號為 或 的頂點之後。這個不變量在初始時成立,並且在每次取出與加入之後都保持成立。
現在考慮一條最短路徑 。由歸納, 以標號 被發現。當它被處理時,由隊列不變量, 要麼剛被賦予標號 ,要麼已經有不超過 的標號。由於最短路徑的前綴仍是最短路徑,其距離為 ;而由實際路徑給出的上界迫使等號成立。於是每個可達頂點被發現時都帶有其真實距離。不可達的頂點不可能獲得父頂點路徑。每個頂點只進入隊列一次,每條無向邊被掃描兩次,由此得到複雜度的界。
證明透視
兩個不等式,兩個不同的理由
證明從兩邊比較每個標號與真實距離,而兩個方向依賴不同的事實。不等式 只需要每個標號都由父頂點的路徑延長一條邊而得;無論以甚麼次序發現頂點都成立,包括使用堆疊。反方向才用到先進先出:由於隊列中的標號不減,而每個新標號都比正在處理的標號大一,在處理 時已被發現的頂點,必定是由標號至多為 的頂點發現的,所以其標號至多為 。
歸納沿一條固定的最短路徑進行;最短路徑的前綴仍是最短路徑,正是這一點使 處的歸納假設成為距離 。可達性與時間界來自同一套記錄:只有可達頂點會獲得父頂點路徑,而每個頂點只進入隊列一次,所以每個鄰接表只掃描一次。
例題詳解
例題 5.1.4
(度數計算可以檢測不可能性)
無論怎樣繪圖,有限圖都不可能恰有三個奇數度頂點。這三個奇數的貢獻會使度數和為奇數,與握手恆等式矛盾。這個條件是必要的,但對於實現任意給定的度數列並不充分:在四個頂點上,度數 是不可能的,因為簡單圖的最大度為 。
例題 5.1.5
(單憑邊數不能確定是樹)
一個三角形加上一個孤立頂點,有 且 ,但它不連通而且含有圈。因此邊數必須與連通性或無圈性其中之一同時出現。去掉三角形的一條邊後,得到有兩個分支、兩條邊的森林,與 相符。
例題 5.1.6
(追蹤 BFS 及其父頂點的選擇)
取邊 。從 出發並先掃描 再掃描 ,BFS 把 標為 , 標為 , 標為 。 所記錄的父頂點是 。若先掃描 ,父頂點則可能是 ,但距離保持不變。儘管原圖含有圈 ,父邊仍在可達頂點上構成一棵樹。
樹的每條邊在結構上都是必要的
從樹中刪去一條邊,其兩個端點就不能再連通:這兩個端點之間若存在另一條路徑,它與被刪去的邊合起來就會在原來的樹中構成一個圈。因此刪除使圖不連通。它恰好產生兩個分支,因為原來的任何路徑都可以在這一條邊處被切開,分成位於兩側的兩部分。這樣的邊稱為橋。
反過來,圈上的邊不是橋。刪去後,該圈的其餘部分仍然連接其端點,凡是用到這條邊的路徑都可以沿圈的其餘部分改道。因此在連通圖中,圈的存在指明了一條可以刪去而不損失連通性的邊。這正是不斷刪去圈上的邊最終得到生成樹的局部原因。
在樹的兩個不相鄰頂點之間加入一條邊,恰好產生一個圈。原來的樹在這兩個端點之間有一條路徑;新邊把這條路徑封閉起來。由於原圖無圈,擴充後的圖中的任何圈都必須使用新邊,去掉新邊後剩下的就是原來那條唯一的路徑。這同時給出了新圈的存在性與唯一性。在思考網絡的逐步構建時,這個結果很有用,而且不依賴任何圖形的畫法。
搜尋森林涵蓋不連通的圖
從一個源點出發的 BFS 沒有理由發現其他連通分支中的頂點。要探索整個圖,可在當前隊列變空之後,從某個尚未被發現的頂點開始新的搜尋。如此重複,直至每個頂點都被發現。每次搜尋為一個分支生成一棵父頂點樹;這些父邊合起來構成一個生成森林。
因此分支數也就是搜尋根的數目。沒有關聯邊的頂點成為一棵單頂點的父頂點樹,仍須計入這個數目。對每個頂點初始化記錄,正是所述時間界含有頂點項的原因,即使圖的邊很少也是如此。一個有大量孤立頂點的圖仍然需要花工夫逐一識別它們。
鄰接表的假設解釋了邊這一項。每個頂點的鄰點可以在與其度成正比的時間內掃描完,而各頂點的度之和等於邊數的兩倍。若用鄰接矩陣,即使度很小,尋找鄰點也可能需要掃描整整一行。因此直接的矩陣實現所需時間是頂點數的二次函數。數學上的距離定理依然成立,但計算上的界取決於表示方式。
最短距離的一個簡短證書
搜尋的輸出可以在不重演隊列的情況下加以驗證。在已到達的頂點上,檢查:源點的標號為零;每個其他頂點都有一個標號小一的父頂點;父連結能到達源點;並且已到達頂點之間的每條邊使標號的變化至多為一。此外還要檢查沒有邊離開所聲稱的已到達集合。父連結提供了具有所記錄長度的實際路徑,而邊的條件則為任何競爭路徑提供了下界。
證明
(父路徑給上界,邊不等式給下界)
要看出下界,沿任意一條從源點出發的路徑走。在第一個頂點處標號為零,每經過一條邊,標號至多增加一。因此經過給定數目的邊之後,終點的標號不大於該數目。於是每條源點路徑的長度都至少等於其終點的標號。父頂點路徑達到了這個界,所以標號恰好是最短距離。檢查沒有邊離開已到達集合,則保證了被遺漏的頂點確實不可達。
證明透視
最短路徑需要上界和下界
每項局部檢查各有其作用。父頂點條件(標號小一、父連結到達源點)為每個已到達頂點構造一條實際路徑,其長度等於其標號:這是上界。邊的條件說明沿每條邊標號至多變化一,所以沿任何源點路徑,終點標號不大於所用的邊數:這是下界,而且它約束每條競爭路徑,不只是父頂點樹中的路徑。源點標號為零為兩個界提供起點。
封閉性檢查,即沒有邊離開已到達集合,使下界能夠涵蓋所有源點路徑:若缺少它,路徑可能走出帶標號的集合,而邊的條件在那裏不起作用,被遺漏的頂點也可能其實可達。僅有一棵看似合理的父頂點樹只能證明可達性,並不能證明最短路徑。
距離層與二分圖
若圖的頂點可以分成兩個集合,使得每條邊都連接不同集合中的頂點,則稱該圖為二分圖。在一個連通分支中,BFS 提示了一種候選劃分:把距離為偶數的頂點放在一側,距離為奇數的頂點放在另一側。若每條邊都跨越這個劃分,它就是一個有效的二分劃分。若有一條邊連接了距離奇偶性相同的頂點,則該分支不可能有二分劃分。
證明
(奇偶性沿每條路徑被迫確定)
為證明不可能性的斷言,假設存在二分劃分。沿著任意一條路徑,每經過一條邊,所屬的一側就交替一次。從源點出發,每條偶數長度的路徑必終止於源點所在的一側,每條奇數長度的路徑必終止於相反的一側。特別地,每個 BFS 最短距離的奇偶性將決定其所在的一側。於是連接奇偶性相同的頂點的邊就會連接同一側的頂點,與二分劃分的定義矛盾。這證明了該檢驗,而無須假設圖形的畫法或某種特定的父頂點選擇。
對於不連通的圖,要在每個分支中進行檢驗;在每個分支內部,兩側可以單獨對調。三角形不能通過檢驗,因為源點的兩個鄰點具有相同的奇數距離而且彼此相鄰。四圈則通過檢驗,因為它交替的層給出了一個有效的劃分。這些例子也說明,圖的頂點數為偶數本身並不是二分性的條件。
概念視角結構
距離標號組織了幾個問題
同樣的 BFS 層既回答最短距離問題,又提供父頂點路徑,還按奇偶性給出一種二著色的候選。這些是對同一個帶標號結構的相關用法,但每個結論都需要各自的檢驗。距離的正確性來自隊列不變量;二分性則還要求每條邊都符合奇偶性。
常見錯誤
常見錯誤
(圖形中的交叉不是頂點)
圖形中邊的交叉並不產生頂點,除非明確把它宣告為頂點。還要區分最短路徑與轉彎最少的路徑或視覺上最短的曲線:這裏每條邊的長度都是一。
常見錯誤
(把隊列換成堆疊)
FIFO 隊列是必不可少的。把它換成堆疊就得到深度優先搜尋,它可能首先沿著較長的路徑發現某個頂點。
常見錯誤
(在帶權圖上使用 BFS)
帶權圖需要不同的距離論證:一條權很大的邊可能比幾條權很小的邊更差。若 、,BFS 經直接邊把 標為 ,但最便宜的路線 費用只有 。BFS 的定理假設所有邊的成本相等。
總結
樹在任意兩個頂點之間有唯一的路徑,而且邊數恰比頂點數少一。這些計數需要結構性的假設。BFS 保持著隊列分層的不變量,使得首次發現時就給出無權最短距離;父頂點的選擇可以不同,而距離保持不變。
練習
快速檢查
(證明:有十個頂點、三個連通分支的森林有七條邊。)
孤立頂點算作單頂點的分支。
解答 · 答案
設各分支的大小為 ,其和為 。每個分支都是樹,所以有 條邊,當 時為 條。相加得 條邊。不同分支之間沒有邊,所以所有的邊都已被計入。
快速檢查
(給出一個圖,使深度優先發現可能記錄下一條非最短的源點路徑,並說明 BFS 給出的不同距離。)
請指明鄰點的次序,使搜尋沒有歧義。
解答 · 答案
取邊 。設深度優先搜尋從 出發先遞歸探索 再探索 ,然後從 探索 ,再從 探索 。它首次發現 時經過的路徑長度為 ,儘管邊 給出的距離是 。BFS 在處理 時同時發現 ,因此令 。
快速檢查
(在邊為 的圖上從 開始執行 BFS,按字母順序掃描鄰點。記錄標號與父頂點,並用奇偶性檢驗判斷它是否為二分圖。)
檢查每一條邊,而不只是父邊。
解答 · 答案
處理 時發現 與 ,標號為 ,父頂點為 。處理 時發現 ,標號為 ,父頂點為 ; 已被發現。處理 時發現 ,標號為 ,父頂點為 ; 已被發現。標號為 、、。父邊 都連接奇偶性不同的頂點,但邊 連接兩個標號為 的頂點。因此該圖不是二分圖;事實上 構成三角形,是一個奇圈。