動機
在最大度頂點處,每條關聯邊都需要不同的顏色。這給出了邊著色的一個下界;但貪心地選取顏色可能會卡住,即使每個頂點都還有未用的顏色。下一條邊兩端可用的顏色可能並不相同。
扇在保持正常性的同時移動未著色邊的位置。雙色路徑則改變哪些顏色可用。二者的結合需要小心:一次路徑互換可能破壞扇的某個條件。下面的證明準確指出這個條件,並說明哪段扇前綴仍然可用。
本節把二部圖的結果推廣到每個簡單圖,給出構造性上界、取得該上界的例子與初等實現的代價。它不判定某個圖是否只用最大度種顏色便已足夠,也不把簡單圖的結論推廣到任意平行邊。
比較證明見 Misra 與 Gries 的構造性論述。這裏明確追蹤變化的扇關係並核算初等實現。
定義
定義 10.3.1
(部分邊著色與缺失顏色)
設 為 個頂點的有限簡單無向圖,最大度為 。正常部分邊著色是指給某些邊賦予顏色,使得在同一頂點處關聯的、已著色的不同邊顏色互不相同;其餘的邊保持未著色。若一個頂點的當前已著色關聯邊都沒有使用某種顏色,則稱該顏色在該頂點處缺失。
使用固定的、含 種顏色的顏色集。即使一個頂點的所有關聯邊都已著色,它處仍至少有一種缺失顏色。在帶有未著色關聯邊的頂點處至少有兩種缺失顏色,不過證明只需要選定其中一種缺失顏色。
固定一條未著色邊 。以 為中心的順序扇是由互不相同的鄰點構成的列表 ,並且對每個 ,邊 已著色,其顏色在 處缺失。扇的任一前綴仍是扇。圖是簡單圖,所以每個扇鄰點唯一確定一條中心邊。
若不存在新的鄰點 ,使得中心邊 已著色、且其顏色在當前最後一個頂點處缺失,則稱該順序扇是極大的。這裏的極大指的是這張特定列表不能再延長,而不是指在所有列表中扇頂點數最多。
對於兩種不同的顏色 ,由這兩種顏色的已著色邊構成的子圖在每個頂點處度數至多為二。它的連通分支是交替路徑、偶數長度的交替圈以及孤立頂點。在整個一個連通分支上互換 與 的顏色,仍然保持正常部分邊著色。
定理/命題
定理 10.3.2
(扇可以搬運未著色邊而不產生衝突)
設 是一個扇,並且顏色 在 與 處都缺失。對 從一到 ,把 的顏色移到 上,同時隨著空位前進而把它從 上移除。然後用 給最後的空位 著色。
所得的部分著色是正常的,並且恰好多了一條已著色邊。只有被選中的中心邊發生了變化;其他未著色邊不受影響。
定理 10.3.3
(一次雙色路徑互換總能產生可用的扇前綴)
對於每條未著色邊及其極大順序扇,取 在中心處缺失、 在最後一個頂點處缺失。要麼 已經在中心處缺失;要麼在包含中心的連通分支上互換 之後,得到一個扇前綴,它的最後一個頂點與中心處都缺失 。
前綴的選取取決於某個特定的前驅頂點是否在該路徑上。互換之後不加區分地旋轉舊的扇,並不屬於該定理的內容。
定理 10.3.4
(最大度的下界至多需要多一種顏色)
每個有限簡單圖都滿足
其中 是正常邊著色所需的最少顏色數。無邊圖的 與 均為零。反覆進行扇/路徑插入即可構造出滿足上界的著色。
藉助帶下標的鄰接表和頂點-顏色關聯表,直接實現需要 時間和 儲存空間,其中 為邊數。這些只是初等的字操作界,並不是經過優化的邊著色運行時間,也不是最小顏色集的判定算法。
證明思路或證明
沿著扇移動空位
證明
(扇的旋轉)
起初 是空位。 上的顏色在 處缺失,於是把它從 上移除並放到 上。在 處,該顏色只是在兩條關聯邊之間移動,從不會重複出現。在 處它原本缺失,而在 處把它移除不會產生衝突。
繼續向前進行。即將移動的顏色在原著色中於其接收方扇頂點處缺失。之前的空位移動並沒有把該顏色引入那裏:之前的每個接收方都是不同的頂點,而當前的接收方只是清除了它自己的中心邊。因此每一步移動都保持正常。等價地說,最終的旋轉使每個接收方得到其後繼原先的顏色,並移除最後一條中心邊的顏色。
在 處,旋轉前後出現的顏色集合不變。在最後一個扇頂點處,唯一變化的關聯邊被清除。因此原來在兩處都缺失的顏色 ,旋轉後在該處仍然缺失。把它放在最後的空位上,已著色邊數增加一,這就證明了第一個定理。只有一個頂點的扇則直接給原來的邊著色。
延長扇,直到每條可能的下一條中心邊都得到處理
證明
(延長為極大扇)
從只含 的列表開始。每當從 出發的某條已著色邊到達列表之外的鄰點,並且其顏色在當前最後一個頂點處缺失,就把該鄰點添加進去。每個添加的頂點都是新的,所以該過程至多添加 的度數那麼多個頂點後停止。所得列表在上述延長意義下是極大的。
選取在 處缺失的顏色 ,以及在最後一個頂點 處缺失的顏色 。若 在 處也缺失,則整個扇立即可用,無需路徑互換。否則 與 不同。由於部分著色是正常的,在 處關聯的 色邊是唯一的。
極大性蘊含這條 色邊是已著色扇邊之一:若其鄰點在扇之外,則由於 在 處缺失,該鄰點可以被添加。把它記作 ,其中 ,並令 。扇的條件說明 在 處缺失。注意 不同於最後一個頂點。
從中心出發進行互換,並追蹤唯一受威脅的條件
證明
(路徑互換及其兩種情形)
設 為包含 的 連通分支。在 處有一條 色邊而沒有 色邊,所以 在該分支中的度數為一。一個有限連通、最大度為二且帶有這樣一個端點的圖是簡單路徑,而不是圈。它的第一條邊顏色為 。沿 互換這兩種顏色。結果仍是正常的,並且 現在在 處缺失。
互換之前,沒有扇邊的顏色是 ,因為 在 處缺失。只有 的顏色是 。因此其他每條扇邊的顏色都在 這一對之外。它們的邊顏色及其在前驅處的缺失狀態在互換後保持不變。唯一可能需要修復的扇關係,是涉及 及前驅 的那一個。
分兩種情形。
若 不在 上,則它仍然缺失 。終止於 的前綴不含 ,所以它的全部扇關係都屬於未變化的那些。該前綴可用,其最後一個頂點 與中心 處都缺失 。旋轉這個前綴即完成。
若 在 上,則互換之前它缺失 。這樣的頂點不可能是一條非平凡 路徑的內部頂點,因為內部頂點各有一條每種顏色的邊。因此它是 以外的另一個端點。它關聯的路徑邊顏色為 ,互換後 在那裏缺失。同時,中心邊 的顏色由 變成 ,所以它的顏色現在在 處缺失。先前受威脅的扇關係得到恢復。
最後一個頂點 在互換前缺失 。若它屬於 ,則它也會是一個端點。但 的兩個端點是 與 ,都不同於 。因此最後一個頂點在 之外,仍然缺失 。現在所有扇關係都成立,所以整個扇可用。旋轉它,並用 給其最後的空位著色。
證明透視
一個例外關係決定前綴的選取
簡單性、極大性與正常性各在一處用到。極大性把 處唯一的 色邊放進扇內,成為某條 ,其中 ;沒有它,這條邊可能通往列表之外的頂點。正常性加上 在 處缺失,使 成為其 分支的端點,所以 是路徑;它也保證沒有扇邊顏色為 ,而顏色為 的只有 。因此互換恰好只可能破壞一個扇關係,即 與 之間的那一個。
分類依據是 是否在 上。若不在,終止於 的前綴根本不用 。若在, 缺失 ,所以它不可能是內部頂點,只能是另一個端點;互換把 變成顏色 ,並在 處空出 ,於是該關係得到修復。端點計數完成第二種情形: 只有 與 兩個端點,所以同樣缺失 的 不在路徑上,仍然缺失 。簡單性使每個扇頂點只對應一條中心邊;若有平行邊,上界本身便會失效,見下面的反例。
這樣就完成了所有情形,而無需假設路徑互換會保持任意一個扇。每次插入都保持正常性,並增加一條已著色邊。從沒有已著色邊開始,重複有限次便可用固定的顏色集給整個圖著色。最大度頂點要求其關聯邊顏色互不相同,這就證明了下界。無邊的情形不用任何顏色,也無需插入。
直接實現的代價核算
證明
(直接實現的代價)
對每個頂點和每種顏色集中的顏色,儲存該顏色的唯一關聯邊,或者一個表示不存在的標記。同時儲存邊的端點、顏色以及鄰接表。該表有 個條目,支持常數時間的缺失顏色檢測,以及交替路徑的下一條邊查詢。
延長扇時,掃描至多 個中心鄰點,檢測該邊是否已著色、其鄰點是否在扇之外、其顏色是否在當前末端處缺失。至多 次延長,或者最後一次失敗的掃描,總計 的工作量。求兩種缺失顏色需要對顏色集做線性掃描。
交替路徑至多包含 個頂點。保留它的邊列表和成員標記,清除表中相關的舊條目,然後寫入互換後的顏色及其條目。先清除可以避免把臨時的表衝突誤認為最終著色中的衝突。這需要線性的路徑工作量。檢查 的成員關係,選取前綴,並沿至多 條扇邊移動空位,同時更新表條目。
因此一次插入的代價為 ,初始化的代價為 。共有 次插入。所儲存的表、列表、路徑和扇給出了所述的儲存界。
例題詳解
例題 10.3.5
(三角形已經需要額外的一種顏色)
三角形的最大度為二。它的三條邊中任意兩條共享一個頂點,所以三條邊需要互不相同的顏色。它的邊色數為三,恰好比最大度大一。
當兩條邊已著上不同的顏色後,第三條邊的兩個端點處所缺失的顏色,在較小的雙色顏色集中可能並不相同。該定理全程使用三種顏色,從而使重新著色的保證成為可能。頂點著色與邊著色是兩個不同的問題,即使這個小圖碰巧在兩者中都需要三種顏色。
例題 10.3.6
(不經任何雙色互換也可以旋轉扇)
設中心為 ,取邊 為空位, 為顏色一, 為顏色二。設顏色一在 處缺失,顏色二在 處缺失,顏色三在 與 處都缺失。列表 是一個扇。
把一移到 並清除 ;把二移到 並清除 ;用三給 著色。此時 處的關聯顏色為一、二、三,並且接收方端點處具有所需的缺失顏色。扇頂點處的其他關聯邊可以存在,只要這些缺失顏色的條件成立即可。
例題 10.3.7
(奇數階完全圖給出一個無窮的緊族)
對於 個頂點的完全圖,其中 ,最大度為 ,邊數為 。一個顏色類是一個匹配,至多含 條邊。因此覆蓋所有邊至少需要 種顏色。
已證明的上界恰好提供這麼多種顏色,所以它的邊色數恰為 。相比之下,四個頂點的完全圖有一個三色邊著色,由匹配 ;;以及 給出。在那裏,最大度所給的三種顏色的顏色集已經足夠。
概念視角算法
局部重新著色操作在改變路線的同時保持進度
已著色邊的數目是全局進度度量。扇的旋轉移動空位,交替路徑交換可用顏色,二者都不改變這一數目。最後的共同缺失顏色使邊數增加一。該不變量保證,即使最初選定的完整扇必須被縮短,這一進度也不會丟失。
常見錯誤
反例模式
平行邊使簡單圖的上界失效
在三個頂點的三角形的每條邊上放置兩條平行邊。最大度為四,但它的六條邊中任意兩條都共享一個端點。每個顏色類至多含一條邊,所以需要六種顏色,超過了五。一般簡單圖的結論不適用於這個多重圖。
常見錯誤
(只互換分支的一部分)
不要只互換雙色連通分支的一個起始部分,除非已證明其端點條件;整個連通分支一起互換才能保持正常性。在路徑 上,設 為顏色 、 為顏色 ;只互換 ,便使 有兩條顏色為 的邊。
常見錯誤
(互換後旋轉整個扇)
不要在沒有檢查例外關係的情況下旋轉互換之前的完整扇。當 不在 上時,邊 現在的顏色是 ,而沒有任何保證說 在 處缺失。旋轉經過 時會把 移到 上,可能在 處重複;只有終止於 的前綴是安全的。
常見錯誤
(多一種顏色不是分類)
多用一種顏色的構造,本身並不能確定哪些圖可以不用這多出的一種顏色。算法在 與 上同樣使用 種顏色,但 只需三種, 則需要五種。
總結
順序扇搬運一條未著色的中心邊。極大性把最後一個頂點處的缺失顏色定位在某條扇邊上,而一次交替路徑互換要麼留下一個可用前綴,要麼留下修復後的整個扇。反覆插入以明確的初等工作量證明了最大度加一的上界,而奇數階完全圖與平行邊反例分別說明了該上界的緊性與適用範圍。
練習
快速檢查
(解釋為甚麼僅含初始頂點的極大扇總能讓該邊直接用該頂點處的某種缺失顏色著色。)
若所選的缺失顏色在中心處出現,請考察其鄰點。
解答 · 答案
選取在唯一的扇頂點處缺失的顏色 。若 在 處出現,則它唯一的關聯邊不可能是空位邊。它的另一個端點會是一個新的扇鄰點,且 在舊的最後一個頂點處缺失,這與極大性矛盾。因此 在 處也缺失,可以直接給空位邊著色。該論證用到了簡單圖中通向那個原鄰點的邊是唯一的。
快速檢查
(在路徑互換的證明中,為甚麼在互換之前,前驅 與最後一個扇頂點不可能同時位於中心的交替路徑上?)
兩者都缺失 ,而中心已經佔據了一個端點。
解答 · 答案
互換之前,中心缺失 而擁有 ,所以它是一條非平凡路徑的一個端點。該路徑上任何其他缺失 的頂點必然是它的另一個端點;內部頂點兩種顏色都有。前驅 與最後一個頂點是不同的,所以它們不可能同時佔據那一個端點。
快速檢查
(求五圈與五個頂點的完全圖的邊色數。給出與定理上界相匹配的下界。)
一個顏色類是一個匹配;對於圈,還要考慮奇偶性。
解答 · 答案
五圈的度為二,不能用兩種顏色做邊著色:繞圈一周會迫使顏色交替,然後使起點處的第一條與最後一條關聯邊得到相同的顏色。由定理知三種顏色足夠。五個頂點的完全圖有十條邊,每個匹配至多有兩條邊,所以它至少需要五種顏色。它的最大度為四,而定理給出五,達到了這個下界。