引言
我們假設讀者熟悉有限簡單無向圖、頂點的度、路徑,以及將圖中的一些邊替換為另一些邊的想法。
問題很容易提出:給定一個有限整數列,例如 ,是否存在一個簡單圖,其頂點的度恰好是這些數?如果存在,怎樣構造這樣的圖?
有些序列因明顯的原因不可能實現,有些則需要更細緻的分析。Havel–Hakimi 定理能解決每一種情形:它把長度為 的序列的問題化為長度為 的同類問題。這個化簡是構造性的,因此只要存在符合要求的圖,它也能給出一個。
可圖化序列
本節中的圖都是有限簡單無向圖,沒有自環或重邊。記 為一個有 個帶標號頂點的集合。
定義 8.2.1
(可圖化序列與實現)
設 , 是整數列。如果存在頂點集為 的簡單圖 ,滿足
則稱 可圖化。這樣的 稱為 的一個實現。
定義中有三點值得注意。
- 空序列可圖化。 當 時,空圖沒有頂點,關於其頂點的所有條件均空真成立。
- 全零序列可圖化。 長度為 的 由 個頂點且沒有邊的圖實現。
- 標號有意義,但重新標號不改變可圖化性。 第 項 指定頂點 的度。若 是 的置換,則 可圖化當且僅當 可圖化:只需重新標記一個實現的頂點。因此排序不改變可圖化性;但如果要構造原標號下的實現,就必須記錄每一項對應的頂點。
含負數的序列不可圖化,因為度數計算的是邊數,至少為 。
兩個必要條件
假設 可圖化, 是它的一個實現, 有 條邊。
命題 8.2.2
(度數的必要條件)
若 可圖化,而它的實現 有 條邊,則
所以各項之和是偶數;並且
證明
(數邊的端點與可能的鄰點)
握手定理給出的奇偶性。 每條邊對其兩個不同端點的度各貢獻 ,所以各度數之和是邊數的兩倍。
度的界。 簡單圖的頂點 只能與另外 個頂點相鄰,且每個最多相連一次。
兩者都是必要條件。單獨滿足任一條件不充分,同時滿足兩者也不充分。
反例模式
各項有界且和為偶數,仍不可圖化
取 ,。各項之和為偶數 ,每項都介於 和 之間,兩個必要條件均成立。
假設 是一個實現。頂點 的度為 ,故它與 全部相鄰; 同理,與 全部相鄰。於是 同時與 和 相鄰,故 ,這與 矛盾。所以 不可圖化。
由此可見,奇偶性與度界只是局部的計數約束,可圖化性還取決於大度數之間如何相互影響:兩個大度頂點會迫使其他頂點與它們相連。
Havel–Hakimi 定理
直覺是貪心的:先滿足需求最大的頂點,並把它連接到剩餘需求最大的頂點,因為後者往往最難在之後滿足。固定這些邊後,這個頂點的需求已經滿足,可以刪除,剩下一個較短的剩餘需求序列。
定理 8.2.3
(Havel–Hakimi 定理)
設 ,整數列 滿足
定義長度為 、指標為 的剩餘序列 :
也就是說,刪除 ,並把接下來的 項各減 。那麼 可圖化當且僅當 可圖化。特別地,如果 含有負數,則 不可圖化。
條件 保證 ,因此 都存在。剩餘序列不一定有序;排序不改變可圖化性,因此再次使用定理前可先排序。
證明
記 ,,則 。證明只用到 的以下性質: 中每個頂點的度,至少與 外每個頂點的度一樣大。
證明
(加入頂點;換邊後再刪去)
逆向( 可圖化 可圖化)。 設 是 在 上的一個實現,即 。因為 可圖化,其各項非負。在 中加入新頂點 ,再加入 條邊 ,其中 ,得到 。
新邊的另一端互不相同,因此它們互不相同;,因此沒有自環; 是新頂點,因此這些邊原先不存在。所以 是簡單圖。在 中, 的度為 ;每個 的度是 ;其他頂點的度仍為 。故 實現 。
正向( 可圖化 可圖化)。 首先證明 存在一個實現滿足 ,其中 表示 的鄰居集合。
關鍵步驟:一次換邊。 設 是 的任意實現,且 。由於 ,存在 ,也存在 。於是 ,;又因為 而 ,所以 。
令 ,。無論 是否為邊,兩個度數都減去相同的修正量,因此
現在 不含 (沒有自環),不含 (由定義),也不含 (因為 ),故 。另一方面,,所以 。因此 在 內的鄰居組成 ,其大小為 。
所以 。存在頂點 滿足:
- 與 相鄰;
- 與 不相鄰;
- 。
四個頂點 兩兩不同。在 中:
- 和 是邊;
- 和 不是邊。
刪去 和 ,加入 和 ,得到 。
仍是簡單圖: 且 ,所以新邊不是自環;它們原先都不存在,且彼此不同。各頂點的度不變:
- 失去鄰居 ,得到鄰居 ;
- 失去 ,得到 ;
- 失去 ,得到 ;
- 失去 ,得到 。
所以 仍實現 。
進展。 的鄰居只發生兩處變化:移除 ,加入 。原先已在 中的鄰居都保留,且
最多為 ,因此重複換邊,至多經過 次便得到 的一個實現 ,滿足 。
刪除。 從 刪除 。每個 恰好失去一個鄰居,其他頂點不失去鄰居。所得簡單圖的頂點集為 ,各頂點度為 。因此 可圖化。特別地,若 可圖化,則 不含負項。
證明透視
最大度數的選擇用在哪裏
逆向只是記帳:一個連到 的新頂點恰好把先前減去的度數加回去。全部內容都在正向,而且集中在一步:保持度數不變的換邊,把邊 換成 。
「 由剩餘度數最大的頂點組成」這個假設只用了一次,就是 。它的作用是找出第四個頂點 :由於 , 在 以外必有一個鄰點不是 的鄰點。沒有這個不等式, 未必存在。在關於減去較小項的練習中,取 與路徑 ,選 、 便得 ,無法換邊。
四個頂點互異,以及兩條邊、兩條非邊的模式,保證 仍是簡單圖且度數不變。每次換邊使 增加一,而它至多為 ,所以過程終止。論證說明的是:貪心選出的鄰域總能成為某個實現的一部分,而不是每個實現都包含它。
相同度數、終止性與構造算法
相同度數。 如果有多個項等於 ,可以任意選一個對應頂點作為 。如果 且邊界處有相同項,即 ,可以任選剩餘度數最大的 個頂點減一。證明只用到 中每個頂點的度至少與 外的每個頂點一樣大。因此「可否圖化」的判斷不依賴如何處理相同項,但構造出的圖可能不同。
帶標號實現算法。 維護一個由(剩餘度數,頂點標號)組成的列表,以及初始為空的邊集 。
- 輸入檢查。 如果某項為負,或某項超過 ,則拒絕。如果 ,接受並輸出 。
- 若所有剩餘度數均為 ,則接受並輸出 ;這包括列表已變空的情形。
- 按剩餘度數從大到小排列各對。設第一對為 ,當前有 對;若 ,則拒絕。
- 移除 。對其後的 對 ,分別將 改為 ,並把邊 加入 。
- 若出現負的剩餘度數,則拒絕;否則返回步驟 2。
終止性。 每次執行步驟 4 都使列表縮短一項,故至多執行 次。
正確性。 對列表長度歸納,每一步應用定理。還需注意:
- 是簡單圖的邊集。 一旦移除就不會再出現,因此該步記錄的每條邊都把 連到一個不同的、仍在列表中的頂點。沒有邊被重複記錄。
- 給出正確的度數。 固定頂點 ,設它被移除時剩餘度數為 。它此前已得到 條邊,在自身步驟中再得到 條,總計 條。若 從未被移除,接受時其剩餘度數為 ,因此它已得到全部 條邊。
輸入檢查之後,步驟 3 實際上不會觸發:不變量是當前列表長度為 時,每個剩餘項至多為 。初始時這正是輸入的度界。若最大項 ,則每個剩餘項至多為 ,故至多為 ;若 ,所有其他項都減一,也至多為 。所以在下一次長度為 時仍滿足該界;步驟 5 另行拒絕負數。保留步驟 3 的檢查並無妨礙。
運行時間。 將大小至多為 的度數的比較和算術運算視為單位開銷,添加每條邊的均攤開銷為常數。每次使用耗時 的比較排序;每次還需要 次減一和插邊操作,且至多執行 次。總耗時為
輸出至多有 條邊,也在此上界內。這是一個簡單的多項式上界,我們不聲稱它最優。
概念視角組合
以不等式作憑證,而非逐步刪點
對總和為偶數的非遞增序列,可圖化也等價於一組共 條不等式,即 Erdős–Gallai 條件:
必要性來自數 上的邊端:這些頂點之間的邊至多貢獻 ,每個外部頂點 至多貢獻 。對 取 ,不等式成為 ,並不成立。算法構造實現;一條不成立的不等式則證明實現不存在。
例題
例題 8.2.4
(可圖化序列及明確的邊集)
設 對應 。度數之和為 ,故若存在實現,它有 條邊。
- 第 1 輪。 移除 (度為 ),將 的剩餘度數各減一。記錄邊 。剩餘:。
- 第 2 輪。 排序為 。移除 ,將 減一,記錄 。剩餘:。
- 第 3 輪。 排序為 。移除 ,將 減一,記錄 。剩餘 ,全為零,接受。
邊集為
檢查各頂點的度:
- 與 相鄰,度為 。
- 與 相鄰,度為 。
- 與 相鄰,度為 。
- 與 相鄰,度為 。
- 與 相鄰,度為 。
共有 條邊,正如預期。
下面的互動圖在度序列上逐輪重演帶標號的 Havel–Hakimi 算法,結果是一個已驗證的邊集,或是證明序列不可圖化的負剩餘度數。
重演 Havel–Hakimi 約簡
在一個度序列上逐輪執行帶標號算法。每一輪先排序,移除剩餘度數最大的頂點,把它連到其後剩餘度數最大的頂點並記錄這些邊。運行結束時,得到一個已驗證的邊集,或出現一個負的剩餘度數。
輸入檢查
| 輪次 | 該輪開始時排序後的剩餘序列 | 移除(頂點:剩餘度數) | 剩餘度數減一的頂點 | 記錄的邊 | 該輪後的剩餘序列 |
|---|---|---|---|---|---|
| 沒有 | |||||
頂點 v₁ … vₙ 排列在圓周上,並標示當前一步的剩餘度數;線段表示至今記錄的邊。邊表列出相同的資料。
| 頂點 | 輸入度數 | 已記錄邊中的度數 | 剩餘度數 |
|---|---|---|---|
| v1 | 3 | 0 | 3 |
| v2 | 3 | 0 | 3 |
| v3 | 2 | 0 | 2 |
| v4 | 2 | 0 | 2 |
| v5 | 2 | 0 | 2 |
- 項數 n
- 5
- 各項之和
- 12
- 和為偶數
- 是
- 每項 ≤ n − 1
- 是
- 已到達的輪次
- 0/3
- 至今的邊數
- 0
- 狀態
- 進行中
- 邊集是簡單圖,且其度數等於輸入
- 不適用
輸入檢查通過:每一項都在 0 與 n − 1 = 4 之間。各項之和為 12,是偶數。尚未執行任何一輪。
為何每一輪都安全,以及拒絕證明了甚麼
設 d₁ ≥ … ≥ dₙ ≥ 0 且 d₁ ≤ n − 1。Havel–Hakimi 定理說:d 可圖化當且僅當剩餘序列可圖化,其中剩餘序列是刪除 d₁ 並把其後 d₁ 項各減 1 所得。因此出現負的剩餘度數,就證明該輪開始時的序列不可圖化。
排序不改變可圖化性,但必須帶著標號,所記錄的邊才是原來頂點之間的邊。剩餘度數相同時,本圖保持當前列表的次序,最初的次序即輸入次序。採用另一種處理相同度數的規則可能得到另一個圖,但不會得到另一個判斷。
當所有剩餘度數都變成 0 時,每個頂點恰好得到其輸入度數:在它自己那一輪所記錄的邊,加上之前記錄的邊。本圖在所記錄的邊集上驗證這一點,並檢查沒有邊被記錄兩次。
對 (3,3,1,1),和為 8 且每項至多為 3,但第 2 輪兩次得到 −1。對 (4,4,4,1,1),和為 14,第 2 輪同樣出現負的剩餘度數。和為偶數及 d₁ ≤ n − 1 是必要條件,並不充分。
本圖依照本節的帶標號算法處理至多 8 項、各項為 0 至 7 的序列。當某項超過 n − 1 時在輸入檢查拒絕;和為奇數時不會提早停止,以便看到約簡在哪裏失敗。相同度數的處理:按剩餘度數穩定地由大到小排序,剩餘度數相同的保持當前次序。
例題 8.2.5
(偶數和序列因出現負項而被拒絕)
再看 。
- 第 1 輪。 移除 (度為 ),將 減一,得到 。
- 第 2 輪。 排序為 。由於 ,通過度界檢查。移除 並將 減一,得到 。
出現負項,所以 不可圖化。由定理, 也不可圖化,與前面的直接論證一致。
負項的具體含義是:若要滿足 和 ,則 和 將不得不接受超過其要求數量的邊。
例題 8.2.6
(同一序列的非同構實現)
令 。
- 第 1 輪。 移除 ,將 減一,記錄 。
- 第 2 輪。 排序後先是 (各為 ),再是 (各為 )。移除 ,將 減一,記錄 。
- 第 3 輪。 的剩餘度數均為 。移除 ,將 減一,記錄 。
- 第 4 輪。 剩餘 。移除 ,將 減一,記錄 。剩餘項全為零,接受。
輸出是兩個不相交的三角形,頂點分別為 和 。
六邊形圈 也實現 。這個圈是連通的,而兩個三角形組成的圖不連通,因此二者不同構。
可圖化序列不能決定甚麼
須區分三個概念。
- 可圖化性。 它是序列的一個是非性質,定理能判定它。
- 帶標號的實現。 即使每個標號頂點的度固定,也可能有多個實現。 恰有三個帶標號實現,分別對應 的三個完美匹配。這三個帶標號圖不同,但互相同構。
- 同構類型。 度數的多重集不能唯一決定圖的同構類型,前面關於同一列表的非同構實現的例子已經說明。反過來, 和 的多重集相同,但標號不同;它們分別由路徑 和 實現,作為帶標號圖不同,作為圖則同構。
可以:同一帶標號序列的任意兩個實現,都可透過有限次保持度數的換邊互相轉化。
自然延伸的下一個問題
任意兩個實現能否透過換邊互相轉化?
可以:同一帶標號序列的任意兩個實現,都可透過有限次保持度數的換邊互相轉化。
正向證明已完成大部分工作。設 與 都實現 ,換邊可把兩者各自變成 的鄰域恰為 的實現。刪去 後得到 的兩個實現;對 歸納,它們可由不涉及 的換邊連接。再把作用在 上的換邊倒序還原,便得到從 到 的換邊序列。特別地,前面兩個不相交的三角形與六邊形圈也是這樣連接的。
常見錯誤
前文已遇到兩種錯誤:誤以為奇偶性和度界已經充分, 已給出反例;以及容許自環或重邊,而本節所有圖都排除它們。
常見錯誤
(減錯項)
定理要求把接下來的 個最大項減一。關於減去較小項的練習說明,若減去較小的項,可能錯誤地拒絕一個可圖化序列。
常見錯誤
(忘記重新排序)
剩餘序列可能不再有序,下一輪必須從最大項開始。在第一個例題中,剩餘 必須重新排序,第二輪才會把 減一。
常見錯誤
(換錯邊)
換邊是刪除 和 ,加入原先不存在的 和 。刪除 沒有意義,因為它不是邊。
練習
快速檢查
(判斷 是否可圖化。)
解答
各項和為偶數 ,各項均不超過 。
- 第 1 輪。 刪除 ,把接下來的四項減一,得到已排序的 。
- 第 2 輪。 刪除 ,把接下來的三項減一,得到 。
出現負項,所以原序列不可圖化。
也可直接論證:五個頂點中有兩個度為 ,它們均與所有其他頂點相鄰。於是剩餘每個頂點的度至少為 ,但 。
快速檢查
(證明 可圖化。用算法構造帶標號實現,並檢查每個度數。)
解答
- 第 1 輪。 移除 (度為 ),將 減一,記錄 。剩餘 的度均為 。
- 第 2 輪。 移除 ,將 減一,記錄 。剩餘 。
- 第 3 輪。 排序為 。移除 ,將 減一,記錄 。剩餘項全為零,接受。
邊集為
逐一檢查:
- 與 相鄰,度為 。
- 與 相鄰,度為 。
- 與 相鄰,度為 。
- 與 相鄰,度為 。
- 與 相鄰,度為 。
共有 條邊,與度數和 一致。
快速檢查
(設 。證明任何由 個兩兩不同整數組成的序列都不可圖化。)
解答
假設 可圖化且 個項兩兩不同。每項均屬於恰有 個元素的集合 。由於這 項不同,集合中的每個數都出現。特別地,存在頂點 的度為 ,頂點 的度為 ;由於 ,二者不同。
與所有其他頂點相鄰,包括 。因此 ,矛盾。
快速檢查
(序列 可圖化,請證明。然後將 連到 和 ,而不是連到剩餘度數最大的頂點,證明所得剩餘序列不可圖化,並解釋為何這不與定理矛盾。)
解答
路徑 在 處的度分別為 ,故 可圖化。
現在將 連到 和 ,剩餘序列為 ,即 。對它應用定理得到 ,所以 不可圖化。
這並不矛盾。定理只保證把 連到 個最大度數頂點時的等價性;這裏應連到 和 中的一個。這樣得到 或 ,二者均可圖化。正向證明需要對 、 有 。若 ,集合外的 度嚴格更大,因此換邊論證不適用。