動機
頂點著色是把相鄰的頂點分開。邊著色則是把共用一個端點的任務分開:關聯於同一頂點的邊必須獲得不同的顏色。每個高度數頂點即時給出一個下界,但這種局部需求是否就是唯一的障礙,並不顯然。
對二部圖而言,答案是肯定的。一種證明把圖補全為正則二分多重圖,再反覆移除完美匹配。第二種證明逐條插入邊,並沿一條路徑交換兩種顏色來修復衝突。後者正好說明了二分性為何能保證修復不會干擾另一個端點。
第一個證明使用先前已證明的二部圖 Hall 定理;第二個證明則給出一個獨立的直接構造。不滿足二分性假設的一般邊著色定理,在沒有證明的情況下不予引入。
定義
定義 10.2.1
(正常邊著色與最大度數)
設 是有限無向二分多重圖,其兩側指定為 。每條邊在每一側各有一個端點。容許帶標號的平行邊,不容許自環。度數把平行邊分別計入。以 記最大度數;當沒有邊時取 。
正常邊著色是給每條邊指定一種顏色,使得共用某個頂點的邊顏色互不相同。其最小調色板大小稱為邊色數 ;無邊圖的邊色數為零。每個單獨的顏色類都是一個匹配。這一問題不同於對頂點指定顏色。
在使用調色板 的部分正常著色中,若某頂點沒有任何當前已著色的關聯邊具有某顏色,則稱該顏色在該頂點處缺失。固定兩種不同的顏色 。只含這兩種顏色已著色邊的子圖,其度數至多為二;它的各連通分支是路徑、偶交錯圈或孤立點。若某個分支含有缺失其中一種顏色的頂點,則它不可能是圈。
正則補全可以添加虛擬頂點和平行邊。這些添加只服務於證明;在把較大的圖分解為若干匹配之後,需要把每個顏色類限制回原來帶標號的邊。
定理/命題
定理 10.2.2
(二部圖的邊著色達到最大度數這一界)
對每個有限二分多重圖,
等價地,其邊可劃分為 個匹配;在描述固定調色板時容許某些類為空。該陳述包含平行邊與不連通的情形。
定理 10.2.3
(正則二分多重圖可分解為完美匹配)
設有限 -正則二分多重圖滿足 ,則其兩側大小相等,且存在完美匹配。反覆移除完美匹配,可將其分解為 個邊不相交的完美匹配。
每個最大度數為 的有限二分多重圖,都可透過添加頂點與邊,擴充為兩側大小相等的 -正則二分多重圖。限制其分解即可證明邊著色定理。
定理 10.2.4
(雙色路徑修復給出直接算法)
設除一條邊 (其中 )之外,其餘邊已使用 色調色板正常著色。取在 處缺失的顏色 與在 處缺失的顏色 。若二者不同,則包含 的雙色子圖分支不含 。交換該分支上的兩種顏色後, 在兩個端點處都缺失,因此 可著為 。
使用按顏色索引的關聯表,在 個頂點上依次插入全部 條邊需要 次基本操作與 的儲存。這只是一個簡單的構造性界,並非最快的邊著色實現。
證明思路或證明
證明
(度數下界)
每組關聯邊都需要互不相同的顏色,所以 。當最大度數為零時沒有邊,結論由空著色得到。下面給出匹配上界的兩個完整證明。
正則性把 Hall 條件化為度數計數
證明
(正則分解與正則補全)
在 -正則二分多重圖中,按左、右端點對所有邊計數,得 ,所以兩側大小相等。對左側任一子集 ,恰有 條邊離開它,且全部終止於它的鄰域集合。進入該集合的邊總數至多為 。於是 。
已證明的 Hall 定理給出一個飽和左側的匹配,因而由兩側大小相等,該匹配也飽和右側。平行邊不影響鄰域判據:相應簡單二部圖中的匹配,可以對其每一對頂點在原有的邊中任取一條可用邊。移除該完美匹配會使每個頂點的度數減一。反覆運用這一論證直至圖中無邊,即證明了正則分解。
對一般的圖,添加孤立點直到兩側大小都等於 。每個頂點的虧量等於 減去其度數。任一側的虧量之和為 ,所以兩側的總量相等。
若該總量為正,則在每一側各選一個虧量為正的頂點,用一條新添的邊連接它們,必要時容許產生平行邊。兩個虧量各減少一。重複這一步,恰在添加了虧量總數條邊後終止。所有頂點的度數都變為 。分解補全後的圖,並在每個匹配中只保留原圖的邊。這就給出原圖使用所需調色板的一個正常邊著色。
這一存在性證明並不假定正則補全仍是簡單圖。若在添加過程中強求簡單性,將施加不必要的限制,並可能使這一初等構造失效。平行邊的標號對度數計數與最終的限制都沒有影響。
為何雙色修復不會波及另一個端點
證明
(交錯路徑修復)
對於直接證明,按任意順序處理原圖的邊。在插入 之前,每個端點至多有 條已著色的關聯邊,所以各自都有缺失的調色板顏色。若某顏色在兩端都缺失,則立即使用它。否則如定理中那樣選取不同的 。
在 處沒有 邊,所以它所在的雙色分支是一條始於 的路徑,或者是一個孤立點。若 屬於這條路徑,則由於 處缺失 ,該路徑必定以 邊開始,並以 邊結束。交替性使其邊數為偶數。但偶數長度的二分路徑,其兩個端點位於同一側,而 位於相對的兩側。這一矛盾說明 不在該分支中。
在整個分支上交換 與 。在內部頂點處,關聯的兩種分支顏色只是互換;端點處每種顏色仍至多出現一次。依分支的定義,任一這兩種顏色的邊都不會從該分支跨到其補集,而其餘顏色保持不變。因此各處的正常性都得以保持。
因為 原本在 處缺失,所以現在在那裏缺失的顏色是 。頂點 不受影響,仍缺失 。把 賦給新邊。這樣就擴充了部分正常著色,因此對所有邊作歸納即可構造性地證明該定理,包括多重圖的情形。平行邊對可能在別處構成兩條邊的交錯圈,但缺失端點處的分支仍是路徑,奇偶性論證仍然成立。
證明透視
二分性與度數上界在修復中何處用到
修復證明用到三個事實,各在一處。度數上界提供缺失的顏色:插入 之前,每個端點至多有 條已著色的邊,所以 和 各有某種調色板顏色空出。正常性與 的選取決定了分支的形狀: 沒有 邊,且至多有一條 邊,所以 所在的分支是一條由 出發的路徑,絕不是圈。二分性只在奇偶性一步用到。若路徑到達 ,它會在 以 開始、在 以 結束;交錯迫使邊數為偶數,而偶數長的路徑連接同一側的兩個頂點,但 、。
交換是安全的,因為該分支是一個完整的分支:沒有 或 邊離開它,所以交換兩種顏色不會與分支外的邊衝突。於是歸納逐邊完成,而調色板從不增大。在三角形中失效的正是奇偶性這一步:由一個端點出發的路徑可以終於另一個端點。
不必反覆搜尋每個關聯邊的修復實現
證明
(表格實現的成本)
對每個頂點和每種調色板顏色,儲存該顏色的關聯邊的編號,或一個空標記。正常著色使這一表項即使在有平行邊時也是唯一確定的。初始化這些表需要 的工作量。掃描其調色板,可在 時間內找到任一端點處缺失的顏色。
要找出始於 的分支,只需藉表查找沿交替的顏色前進。它是一條至多有 條邊的路徑,因為始於端點的最大度數為二的分支不會重訪頂點。記錄這些邊,清除它們原先的關聯表項,然後賦予互換後的顏色並寫入新的表項。先清除可以避免覆蓋更新過程中仍需使用的表項。分支的搜尋與更新使用 的工作量與臨時路徑儲存。
因此,初始化之後,每次插入邊的成本為 。圖及其顏色標號儲存在 個邊條目中,關聯表儲存在 個條目中。上述界計的是普通陣列存取與有限整數下標;它並不把對任意外部標號的查找隱藏為常數時間操作。
直接算法無須實際構造可能大得多的正則補全。兩個證明透過不同而有用的不變量建立同一個存在性定理:一個對正則圖的每個度數層移除一個完美匹配,另一個則透過局部交錯修復保持正常性。
例題詳解
例題 10.2.5
(完全二部圖 需要三種邊顏色)
對 ,每個左頂點的度數為三,每個右頂點的度數為二。按右頂點的順序,把第一個左頂點的三條邊依次著為一、二、三,把第二個左頂點的三條邊依次著為二、三、一。
每一行使用的顏色互不相同,每個右頂點看到兩種不同的顏色,所以這是一個正常著色,並達到 。正則補全的證明添加一個虛擬左頂點,把它與全部三個右頂點相連,得到三正則圖。其完美匹配所給出的顏色,限制後正為這樣一個有效的三色方案。
例題 10.2.6
(一條交錯路徑釋放出所需的顏色)
設兩側為 與 。已著色的邊為: 著色二, 著色一, 著色二, 著色一。現在插入未著色的邊 。最終圖的最大度數為二。
顏色一在 處缺失,顏色二在 處缺失。 處的雙色分支是路徑 ,它不含 。交換其顏色,使這些邊依次變為一、二、一。此時顏色二在 兩處均缺失,所以把它賦給 。所有度數為二的頂點各看到每種顏色一次,而原有的邊標號與端點都沒有改變。
例題 10.2.7
(平行邊說明邊著色與頂點著色為何不同)
取分處兩側的兩個頂點,用三條帶標號的平行邊將它們相連。其最大度數為三,且三條邊共用兩個端點,所以三種不同的邊顏色既是必要的,也是充分的。
相應的頂點著色問題只需要兩種顏色。平行邊並不增加新的頂點相鄰要求,卻增加了互相爭奪邊顏色的相異關聯邊。不能僅僅因為畫的是同一個圖,就用一個定理中的參數去替代另一個定理中的參數。
概念視角組合
一種邊顏色就是一個匹配層
調色板把邊集劃分為若干組,每組都不重複使用任何端點。正則性使每一層覆蓋每個頂點;非正則的圖則使一些頂點在個別層中處於閒置。度數下界記錄的是局部需求的最大個數,而二分性正好使這些需求可以協調為恰好這麼多個匹配層。
常見錯誤
反例模式
奇圈需要的顏色多於其最大度數
三角形的最大度數為二,卻需要三種邊顏色:它的三條邊中每兩條都相交。更一般地,奇圈無法在閉合處一致地交替使用兩種顏色。三種顏色已經足夠:沿除最後一條邊之外的所有邊交替使用一和二,再給最後一條邊著色三。因此它的邊色數為三,而最大度數為二。
常見錯誤
(在到達另一端點的路徑上交換)
不要在沒有位於二分劃分相對兩側的情形下套用雙色端點論證。在三角形 中,設 著色一、 著色二,以調色板 插入 。顏色二在 處缺失,顏色一在 處缺失,但 所在的分支是路徑 ,它到達了 。交換後 為顏色二、 為顏色一,於是 改為缺失一、 改為缺失二:衝突只是轉移了。
常見錯誤
(顏色類不一定是完美匹配)
在非正則圖中,顏色類是一個匹配,但不一定是完美匹配。兩條邊的路徑有 ;它的兩個顏色類各是一條邊,各漏掉三個頂點中的一個。只有正則補全的各層才是完美匹配。
常見錯誤
(把虛擬邊也報告出來)
正則補全中所用的虛擬邊,在報告原圖的著色之前必須移除。對 ,補全加入一個與全部三個右頂點相連的左頂點,而三個完美匹配各用到一條這樣的新增邊。報告的著色是限制到六條原有邊上的著色。
總結
對有限二分多重圖,最大度數正為邊著色所需的顏色數。Hall 定理證明了正則圖的完美匹配分解,而雙色路徑交換給出直接的增量算法。二部圖的奇偶性排除了修復中的衝突;奇圈則說明了該假設以及它區別於頂點著色的必要性。
練習
快速檢查
(利用行與列下標的規則,給出 的一個顯式三邊著色。)
使用下標零、一、二,並在模三下計算。
解答 · 答案
把每一側用下標零、一、二標號。給邊 著色 。沿固定的一行,三個列值使每種顏色恰好出現一次;沿固定的一列,三個行值也是如此。因此關聯邊的顏色總是互不相同。度數為三的下界證明了最優性。
快速檢查
(對有 個葉子的星圖,求其邊色數與頂點色數。當 很大時,說明二者的差異。)
所有邊都交於中心,但任意兩片葉子不相鄰。
解答 · 答案
星圖的最大度數為 ,所以它需要 種邊顏色,在中心處每條邊各佔一種。它恰需要兩種頂點顏色:一種給中心,另一種給全部葉子。由於至少有一條邊,一種頂點顏色是不可能的。當 很大時,邊的調色板增大,而頂點的調色板仍為二,直接說明了這兩種約束的不同。
快速檢查
(解釋為甚麼始於缺失某一顏色的頂點的雙色交錯分支不可能是圈,並說明存在平行邊時的情形。)
在使用任何奇偶性論證之前,先考察起始頂點在該分支中的度數。
解答 · 答案
正常性容許任一所選顏色在其關聯邊中至多出現一次。因此缺失其中一種顏色,會使該頂點在該子圖中的度數為零或一。含有這樣的頂點的連通分支是孤立點或路徑,因為其所有頂點的度數至多為二。它不可能是圈,因為圈的所有頂點在分支中的度數都是二。由兩條平行邊構成的二邊圈,其兩個端點的度數同樣是二,所以它不可能含有缺失顏色的頂點。隨後的二分奇偶性論證適用於所得的路徑。