為甚麼給圖著色?
設共用資源的任務不能同時執行。把任務看作頂點,在有衝突的兩項任務之間連邊,再用顏色表示時段:相鄰頂點必須顏色不同。在這個模型中,所需的最少顏色數就是最少時段數。圖只記錄兩兩衝突;若還有其他排程限制,則需要補充模型。
定義 5.3.1
(合法著色與色數)
設 是有限簡單無向圖。合法的 -著色是映射 ,使每條邊 的兩端滿足 。色數 是可行的最小 ;空圖規定為 。團是任意兩個不同頂點均相鄰的頂點集合。非空圖的最大度記為 。
每個顏色類都是獨立集;顏色多於實際所需時,某些顏色類可以為空,而非空顏色類構成頂點集的劃分。大小為 的團必須使用 種不同顏色,因此 。這只是下界,不一定取等號:其他邊也可能迫使我們增加顏色。
概念視角結構
把著色看作到完全圖的映射
合法 -著色就是圖同態 ,即把每條邊映到邊的頂點映射。 的頂點就是顏色,兩種顏色相鄰當且僅當它們不同,所以「邊映到邊」恰好表示相鄰頂點顏色不同。用這種語言, 是使 存在同態的最小 ,而圖可用兩色著色當且僅當它可映到 。
這個描述可以複合。若 是同態、 是合法著色,則 是 的合法著色,故 。取子圖 的包含映射,得到 ;取 團的包含映射 ,便得到團下界 。
貪心著色
選定次序 。處理 時,給它分配尚未被已著色鄰點使用的最小正整數。之後處理的鄰點會避開 的顏色,因此不會破壞這一步。
定理 5.3.2
(貪心度數界)
任意非空有限簡單圖在任意頂點次序下,貪心著色均合法且至多使用 種顏色。更精確地說,若在所選次序中每個頂點至多有 個較早的鄰點,則至多使用 種顏色。
證明
(計算被禁用的顏色)
處理某頂點時,較早的鄰點至多禁用 種顏色。因此 中至少有一種可用。每條邊都有一個較遲處理的端點;該端點會避開另一端點的顏色,所以最終著色合法。每個頂點的鄰點總數不超過 ,便得到度數界。選擇較好的次序可能改善上界,但不保證得到最優著色。
例題 5.3.3
(奇圈與最優性證明)
在圈 上按順序處理,貪心給出 。前四個頂點交替著色,最後一個頂點看到兩種顏色。三色足夠;兩色不可能,因為沿前四條邊交替後, 與 顏色相同,但二者相鄰。故 ,雖然最大團只有兩個頂點。
兩色與奇圈
定義 5.3.4
(二分圖)
若圖 的頂點集可劃分為 ,且沒有任何邊的兩端同時屬於 或同時屬於 ,便稱 為二分圖。允許其中一類為空。
兩類都是獨立集;給 用顏色 1、給 用顏色 2,就得到合法兩色著色。反過來,任何合法兩色著色的兩個顏色類也給出這樣的劃分。因此二分性和可用兩色著色描述的是同一性質:前者用集合劃分表述,後者用顏色標籤表述。
定理 5.3.5
(二分圖判別法)
有限簡單圖可用兩種顏色合法著色,當且僅當它沒有奇圈。這裏「可用兩色」指兩色的調色板足夠,亦包括無邊圖和空圖。
證明
(廣度優先距離的奇偶性)
在合法兩色著色中,沿路徑顏色交替。若存在奇圈,繞圈回到起點時會得到與原來相反的顏色,矛盾。
反之,假設沒有奇圈。對每個連通分支選根 ,並選定一棵 BFS 父樹。樹中從 到每個頂點的路徑都是最短路徑,記其長度為 ,再按 的奇偶把頂點分為兩類。若 是邊,在到 的最短路徑後接上該邊,就得到 ;交換兩端,同理有 。所以相鄰頂點到根的距離至多相差一;若奇偶性相同,距離必定相等,記為 。
假設存在這樣的邊。兩條樹路徑共用一段從根開始的路徑,直至最後公共祖先;設該祖先到根的距離為 。在此之後,兩段路徑沒有公共頂點,長度各為 。這兩段路徑加上該邊構成長度為 的簡單圈。它是奇圈,矛盾。因此每條邊都連接不同奇偶類。給兩類不同顏色即可;孤立頂點也沒有困難。各連通分支分別處理。
證明透視
沒有奇圈這一假設在哪裏使用
正方向只需要顏色沿每條邊交替。反方向依靠兩個步驟。第一,每條邊上的距離不等式 把「奇偶相同」變成等式 ;單靠奇偶性並不能說明兩條樹路徑等長。第二,停在最後公共祖先,使兩段尾路徑只在該點相交,於是尾路徑、該邊與反向尾路徑構成簡單圈,而不是可能重複頂點的閉遊走。由於 ,有 ;假設恰好只使用一次,用來排除長度為奇數 的這個圈。論證要在每個連通分支分別進行,因為 只在 所在的分支上有定義。
例題 5.3.6
(貪心結果取決於次序)
設邊為 ,即四頂點路徑。按 的次序,貪心得到 。但 、 已是合法著色。因此一次貪心運行只給出上界,不能單憑它證明所用顏色數最少。
用刪除法尋找合適的次序
較早鄰點數的精確界啟發我們選擇次序。假設每個非空子圖內部都有一個度不超過 的頂點。反覆刪除這樣的頂點並記錄次序,直至沒有頂點;然後按相反次序著色。恢復某頂點時,已經恢復的鄰點恰是刪除它時仍留在子圖中的鄰點,最多有 個。因此貪心至多用 色。這裏的度是在當前子圖內計算,不一定等於原圖中的度。
例如森林的每個非空子圖都有度至多為一的頂點:非平凡樹有葉,孤立頂點則度為零。刪除法給出森林的兩色著色。非空無邊森林只需一色;含邊的森林需要兩色。這得到準確答案,但沒有聲稱森林的每個頂點次序都只用兩色;前面的四頂點路徑已否定後者。
例題 5.3.7
(為甚麼必須倒轉刪除次序)
再看路徑 。依次刪除 ,它們在被刪除時的度分別為 。特別是 原本的度為二,但刪除它時,鄰點只剩 。按相反次序 著色,得到 :恢復 和 時,各自只看到 ;恢復 時,只看到 。每個頂點至多有一個較早著色的鄰點,因此可以使用兩色界。
如果直接按刪除次序 著色,反而得到前面使用三色的結果。刪除時的較小度數計算的是刪除後仍留在圖中的鄰點;只有倒轉次序,這些鄰點才會先被著色。因此只記錄較小的剩餘度數、卻不倒轉次序,並不能證明所聲稱的界。
從定理到證據
要核對圖可用 色著色,只須檢查每條邊兩端的顏色。要證明它至少需要 色,則需要另一種證據。 個頂點的團就是一種證據,但五圈說明它不是唯一方法:奇圈排除了兩色,而一個具體的三色著色給出配套上界。要確定準確的色數,兩部分都不可少。嘗試著色失敗,本身不能證明不存在合法著色。
例題 5.3.8
(上下界相遇)
取頂點為 的三角形,加入頂點 ,令它與 相鄰,但不與 相鄰。三角形需要三色。令 ; 可能具有顏色 3 的鄰點是 ,但二者之間沒有邊。因此三色足夠,也達到下界:。只數頂點只能給出較弱的上界四,而只指出三角形只能得到下界。
空圖需要單獨約定: 時,唯一的空著色不使用顏色,故 。非空無邊圖的色數是 。非連通的非空圖的色數等於各連通分支色數的最大值:整個圖的著色限制在每個分支上,仍是合法著色;反之,每個分支的最優著色可以重複使用同一組顏色。因此這裏取最大值,而不是求和。
找到著色或奇圈
廣度優先搜尋(BFS)把奇偶性證明變為可執行的方法。在每個尚未訪問的連通分支中選根,令根的距離為零,逐層訪問鄰點,並在首次發現頂點時記錄其父頂點。根據 BFS 距離的奇偶性給每個頂點著色。如果每條邊連接不同奇偶類,就得到合法兩色著色。如果一條邊的端點奇偶性相同,它們的距離實際上相等,因為相鄰頂點的距離至多相差一。從兩端沿父指針回溯到最後一個公共祖先,兩段樹路徑加上該邊便構成奇圈。
例題 5.3.9
(構造奇圈)
設邊為 ,從 開始 BFS。 的距離是 , 的距離是 , 的距離是 。邊 的兩端奇偶性相同。父路徑分別為 和 ,最後公共祖先是 ;加上 便得到長度為五的圈 。這是不能兩色著色的可核證證據;僅有 BFS 父路徑並不矛盾,必須檢查到邊 才能得到這個結論。
使用鄰接表時,BFS 對每個頂點和每條邊只處理常數次,故運行時間為 。圖不連通時,必須從每個尚未訪問的頂點重新開始:只檢查根所在分支可能漏掉其他分支的奇圈。若使用鄰接矩陣,掃描所有可能鄰點需要 時間。這些是針對所述圖表示的算法界,並不包括取得圖數據的成本。
次序能有多差?
差的貪心次序不只可能多用一種顏色。對於 ,取頂點 ,恰在 時連接 。所有 與所有 分別構成兩個獨立集,給出兩色著色;圖中有邊,所以色數恰為二。現在按 處理。歸納可知 和 均獲得顏色 :每個頂點都從較早的另一類頂點看到所有較小顏色,而 與 不相鄰。因此貪心使用 色,最優解卻只需兩色。這解釋了為甚麼某一次運行的顏色數只是上界,而不是最優性證明。
度數界仍然成立:每個頂點的度是 ,因此這次貪心恰好使用 色。某算法的上界可以達到,並不意味著圖的色數也必須達到該上界。要給出更好的結論,可以尋找更好的次序,或用其他方法構造著色,再配合下界。
只有完全圖與奇圈:其他連通圖都可用不超過最大度的顏色數著色。
自然延伸的下一個問題
哪些連通圖真的需要比最大度多一種顏色?
只有完全圖與奇圈:其他連通圖都可用不超過最大度的顏色數著色。
完全圖 與奇圈(此時 )需要 種顏色。Brooks 定理指出它們是僅有的連通例子:既非完全圖、亦非奇圈的連通圖滿足 。它的證明仍是貪心著色,只是精心選取次序,使最後一個頂點的鄰點中有重複的顏色。這個界仍可能與 相差很遠,正如常見錯誤中的星圖所示。
常見錯誤
常見錯誤
(度數數的是鄰點,不是被禁用的顏色)
鄰點的數量不一定等於被禁用的顏色數。在中心為 、有 個葉的星圖中,中心的度是 ,但所有葉都可以共用一種顏色,因為任意兩片葉之間都沒有邊。給葉用顏色 1,給中心用顏色 2,就得到合法著色。圖中有邊,排除了一色,所以無論 多大,色數都恰好是二。度數界之所以有效,是因為不同禁用顏色的數量至多等於較早鄰點的數量,並不要求這些鄰點彼此顏色不同。
常見錯誤
(可用兩色不等於色數為二)
「可用兩色」表示兩種可用顏色已經足夠,並不要求兩種都出現。非空無邊圖可用兩色,但色數是一;二分圖判別法刻畫的是 ,而 恰好在此之外圖還有邊時成立。
二分圖判別法也容易引出一個看似合理的捷徑,五個頂點的圖就能否定它。
反例模式
排除三角形不等於排除奇圈
聲稱:沒有三角形的圖可用兩色著色。取頂點按循環次序為 的 。每個頂點 恰有兩個鄰點 與 (下標按模 計),而這兩點不相鄰,所以沒有三角形。然而兩色著色會沿 交替為 ,於是 的顏色與 不同,即與 相同,但 是邊。因此 不能兩色著色。修正方法是使用判別法的完整假設:必須排除所有奇圈,而不只是長度為三的奇圈;或者直接給出合法劃分。
練習
快速檢查
(求 時的 ,並說明上下界。)
解答 · 答案
全部 個頂點構成團,至少需要 色;每個頂點用不同顏色可達到 色,所以 。
快速檢查
(圖的最大度為 且含三角形,可得甚麼界?分別舉例達到兩個端點。)
解答 · 答案
三角形給出 ,貪心界給出 。三角形加一個懸掛頂點的最大度為 ,可用三色; 的最大度為 ,需要四色。
快速檢查
(按 的次序對路徑 貪心著色。為甚麼至少需要兩色?)
解答 · 答案
依次為 。圖中有邊,一色不可能,故色數為 。
快速檢查
(圖由互不相連的 、三角形和一個孤立頂點組成。求其色數。)
解答 · 答案
各分支的色數為 。在每個分支重複使用同三種顏色; 給出下界三。因此答案為 ,不是 。
快速檢查
(從 出發的 BFS 父邊為 ,另有邊 。找出奇圈。為甚麼必須利用這條邊,而不能只看父樹?)
解答 · 答案
圈為 ,長度為五。父樹本身沒有圈;額外的邊 把兩條父路徑閉合。
快速檢查
(邊為 的圖的色數是多少?)
解答 · 答案
構成三角形,至少需要三色。令 。由於 不相鄰,這是合法著色,故 。