動機
圖著色歸約必須把邏輯約束轉化為局部的邊約束。僅僅說一個構件「表示一個子句」,並沒有回答真正重要的問題:該構件終端上的哪些顏色分配可以擴張為一個合法著色?
我們構造一個小型子句構件,並逐一檢驗它所有的終端情形。再配合一個為三種顏色命名的三角形,以及為每個變量設置的一對頂點,便得到一個由 3-SAT 至圖三著色問題的完整多項式時間歸約。
定義
定義 4.3.1
(合法三著色)
圖的一個合法三著色(proper three-coloring)是給無向圖的每個頂點指定三種顏色之一,使得相鄰頂點的顏色不同。該判定問題詢問這樣的著色是否存在。
由每個子句恰有三個文字出現的 3-CNF 公式出發。容許文字重複,因此只含一個或兩個文字的子句可以透過重複已有文字補足,而不改變其真值。空子句是即時不可滿足的情形,可以映射到一個固定的不可三著色的圖。3-SAT 的 NP 完全性是引入的起始定理。
定義 4.3.2
(調色板三角形與變量對)
建立一個由調色板頂點 構成的三角形。在任何合法三著色中,這三個頂點獲得三種互不相同的顏色。我們也用這些名稱來稱呼它們的顏色;對三種實際顏色重新命名不影響可著色性。對每個變量 ,建立頂點 與 ,把它們彼此相連,並把兩者都與 相連。於是它們必須按某種次序分別獲得 與 ,從而編碼一個真值及其相反值。
定義 4.3.3
(子句構件)
對於文字頂點為 的子句,加入四個全新的內部頂點 以及九條邊
每個子句都有自己的內部頂點。三個終端名稱 可以指代重複的或互補的文字頂點;證明只使用它們實際獲得的顏色。
定理
定理 4.3.4
(子句構件性質)
設 各自被染成 或 ,則四個內部頂點可以被合法著色,當且僅當 中至少有一個的顏色為 。
定理 4.3.5
(三著色是 NP 完全的)
該構造把公式映射為一個圖,此圖可三著色恰好當公式可滿足。因此圖三著色問題是 NP 完全的。
證明:全假的子句無法著色
證明
(全假模式迫使矛盾)
設 。由於 與 相鄰且 ,故 必須取顏色 。同理 。頂點 與 相鄰且 ,所以 。頂點 與 、 以及 相鄰,因此沒有可用的顏色。該構件無法被合法著色。
由於三角形的存在,三種調色板顏色互不相同。該論證並不依賴它們的外部名稱:在任一合法著色之後,把調色板頂點 的顏色稱為假色,對 與 亦同。
概念視角結構
著色等同於映到三角形的同態
圖的合法三著色,等同於從頂點到三角形三個頂點的保持鄰接的映射:相鄰頂點必須映到不同、因而相鄰的三角形頂點。這樣看,構造中的調色板三角形就是目標圖的一個副本,把一個頂點連到某一個調色板頂點,只是禁止它取那個像;連到其中兩個,才把它的像釘在第三個上。子句構件隨後對它三個終端的像施加一個關係,而定理說明這個關係是「至少有一個為 」。
證明:其餘每種終端分配都可以擴張
證明
(其餘七種模式的明確擴張)
下表對每個至少含一個真終端的分配給出一個合法的內部著色。各列依次列出 的顏色。
| F | F | T | G | G | T | F |
| F | T | F | G | F | G | T |
| F | T | T | G | F | T | F |
| T | F | F | F | G | T | G |
| T | F | T | F | G | T | G |
| T | T | F | F | F | T | G |
| T | T | T | F | F | T | G |
每一行都可以對照九條邊來檢驗: 與 都不同於 ; 不同於 ; 分別不同於 ;並且三條內部邊 的兩個端點顏色不同。結合全假子句的論證,此表即證明了構件性質。
證明透視
構件的每條邊用在哪裏
在全假模式中,各條邊構成一條強制鏈。當 時,邊 與 令 只能取顏色 ;同理 與 令 。然後 與 迫使 ,最後 經 、 與 同時遇上三種顏色。九條邊各有分工: 把構件接到調色板, 接上終端, 連結內部頂點。
不顯而易見的是,單一個為真的終端恰好在它所接觸的頂點處截斷這條鏈: 為真使 可取 , 為真使 可取 , 為真使 可取 。表格檢驗每一種截斷都留下一個一致的著色。沒有表格,論證只說明了假子句被拒絕,卻沒有說明被滿足的子句會被接受。
證明:公式與圖的等價性
證明
(可滿足性與三著色性相符)
給定一個滿足賦值,先用三種不同的顏色為調色板三角形著色。對每個變量,按賦值把其正文字頂點染成 或 ,並把負文字頂點染成相反的顏色。變量邊是合法的。每個子句至少有一個真終端,故選取表中對應的行為它的四個全新內部頂點著色。由於不同的子句構件只共享文字頂點和調色板頂點,這些選擇互不衝突。整個圖因而被合法地三著色。
反之,設該圖有一個合法三著色。調色板三角形使用三種不同的顏色。每個變量對中的兩個頂點彼此相鄰且都與 相鄰,所以其中一個文字頂點的顏色為 ,另一個為 。令變量為真,當且僅當其正頂點被染成 。每個子句構件都有合法的內部著色,因此由構件性質,其終端不可能全為 。於是在所得賦值下,每個子句中至少有一個文字為真。故公式可滿足。
對於 個變量與 個子句,該圖有 個頂點,在去除重複邊之前至多有 條邊。它可以由顯式給出的公式在多項式時間內構造出來。對於給定的三著色,只需檢查每個頂點的顏色並比較每條邊的兩個端點,即可驗證,所以三著色屬於 NP。由 3-SAT 出發的歸約證明了 NP 困難性,從而完成 NP 完全性的論證。
例題詳解
例題 4.3.6
(一個真終端)
對終端顏色 ,表中給出 。特別地, 不同於 、 與 ,所以它的三條關聯約束都得到滿足。
例題 4.3.7
(所有終端皆假)
對 ,被迫的顏色為 與 。頂點 與三種調色板顏色的頂點都相鄰,無法著色。這正是該構件必須拒絕的邏輯情形。
例題 4.3.8
(重複的文字)
單位子句 可以寫成 。若 ,則它的三個終端全為假,構件不可能著色。若 ,則行 給出合法的擴張。把同一個文字頂點用於三個終端角色並不改變論證。
例題 4.3.9
(變量及其否定)
文字頂點 與 都與 相鄰,所以兩者都不能使用顏色 。它們之間的邊迫使其中一個使用 ,另一個使用 。正是這一圖約束使得提取出的真值賦值保持一致。
常見錯誤
反例模式
缺少邊 CD 的構件會接受假子句
聲稱:邊 是多餘的,構件只用八條邊便可。用模式 來檢驗。強制的顏色仍然是 (由 得出)以及 (由 與 得出)。 與 及 相鄰,所以去掉 之後 是允許的,即使 亦然。其餘每條邊都合法,所以三個終端皆假的子句也可以著色。為不可滿足的公式 構造的圖便會是三可著色的,因為終端全是那個假文字頂點的子句不再被拒絕。正是邊 使全假模式失敗。
常見錯誤
(預先固定實際的顏色名稱)
這個歸約並不預先指定固定的實際顏色名稱。三角形強制三種不同的顏色;在選定一個著色之後,才以調色板頂點為這三種顏色命名。把三種顏色整體置換,得到另一個合法著色,而相對於調色板,所編碼的真值賦值並無改變。
常見錯誤
(把困難性與屬於 NP 當作同一項聲稱)
NP 困難性與屬於 NP 是兩項獨立的聲稱。圖的構造把困難性由 3-SAT 傳過來;在多項式時間內檢查一個給定的著色,則確立屬於 NP。單憑其中一項都不是完整的 NP 完全性證明。
高效地閱讀構件表
這張表不應被當作七個互不相關的猜測。若 ,則最後四行都使用 、 與 ;例外是 的兩行使用 ,因為 與 相鄰。在每個列出的行中,終端邊與內部邊是分別檢驗的。這種組織方式使人更容易看出,即使某些終端角色指代同一個文字頂點,這些見證依然有效。
例如,對 ,取 。終端邊是合法的:、,並且 。調色板邊是合法的,因為 且 。最後有 、 與 。檢驗完這九條邊之後,不再有任何隱藏的約束。
見證表之所以能證明可擴張,是因為它涵蓋了除 以外的全部七種真值模式。並不需要為每種模式列出所有可能的內部著色。反過來,證明全假模式失敗本身並不能證明所有滿足的模式都可擴張;歸約同時用到這兩個半部分。
一個完整的小公式
考慮 。把單位子句補足為 與 。變量構件迫使兩個文字頂點中恰有一個的顏色為 。於是三次連接到該假文字上的子句構件,其終端模式為 ,無法著色。因此所構造的圖不可三著色,與該公式不可滿足相吻合。
對於公式 ,取 且 。給每個相反的文字頂點賦予相反的真值顏色。該子句的終端模式為 ,表中給出一個合法的內部著色。這樣,由滿足賦值就構造出了圖著色的見證,而無需在所有圖著色中搜尋。
驗證規模與證書
調色板貢獻三個頂點與三條邊。每個變量貢獻兩個頂點與三條邊:一條變量對之間的邊,以及每個文字頂點各向 連的一條邊。每個子句貢獻四個全新頂點與九條列出的邊。即使一個子句重複某個文字,這仍然只是常數個新增部分;把圖表示為簡單圖時可以去掉重複邊,而不改變合法著色性。
著色證書為每個圖頂點指定三個標籤之一。驗證器先檢查每個標籤是否有效,再掃描邊表,若某條邊的兩個端點顏色相同則拒絕。這所需的時間關於顯式列出的頂點與邊是多項式的。驗證器不需要知道滿足賦值,也不必反向執行歸約就能檢驗該證書。
反向的蘊涵對於困難性證明仍然是必不可少的。若不可滿足的公式所對應的圖竟有合法著色,則著色算法就會對一個為假的源實例回答是。由調色板與變量構件中提取賦值,再對每個子句使用全假不可著色的結論,即排除了這種可能。
子句長度的規範化
含兩個文字的子句 可以替換為 ,單位子句 可以替換為 。重複不改變子句的真值。當終端角色重複時,構件表依然有效,因為它只應用於由共享頂點實際誘導出的終端顏色模式。
若公式含有空子句,則它不可滿足。一個固定的否實例是四個頂點的完全圖:任意兩個頂點都相鄰,所以需要四種互不相同的顏色。若公式沒有子句,則它可滿足;所構造的調色板與變量構件只要賦予任意真值即可著色。這些情形使映射在所述的輸入約定下是全函數。
加入全能頂點,就能把三著色問題變成 k 著色問題。
通往推廣的路徑
從三種顏色到 k 種顏色
加入全能頂點,就能把三著色問題變成 k 著色問題。
對 ,在圖 中加入 個新頂點,它們彼此相鄰,也與 的每個頂點相鄰。新頂點使用 種互不相同、且 的頂點不能使用的顏色,所以擴大後的圖可 著色,恰好當 可三著色。因此對每個固定的 , 著色問題都是 NP 完全的。改變的只是調色板;子句構件並未重用。
總結
調色板三角形給出真值顏色,變量對強制相反的真值,而四頂點的子句構件可著色恰好當至少有一個終端為真。把這些構件組合起來,便得到一個多項式時間的 3-SAT 歸約以及可驗證的著色證書。
練習
快速檢查
(為甚麼變量對中的兩個文字頂點都不能取顏色 ?)
留意調色板頂點 。
解答 · 答案
兩者都與調色板頂點 相鄰,所以合法著色禁止兩個端點取顏色 。
快速檢查
(在終端顏色為 的子句構件中,為甚麼必須 ?)
除了終端以外,還有哪些頂點與 、 相鄰?
解答 · 答案
兩者都與調色板頂點 以及一個顏色為 的終端相鄰,只剩下 。
快速檢查
(驗證表中 那一行裏,與 關聯的各條邊。)
查看表中該行 的顏色。
解答 · 答案
該行 。頂點 與 、 及 都不同,滿足它的三條關聯邊。
快速檢查
(為甚麼所構造圖的合法著色能給出滿足賦值?)
運用變量對與構件性質。
解答 · 答案
每個變量對使用相反的真值顏色,定義出一個一致的賦值。每個子句構件只有在至少一個終端為 時才可著色,所以每個子句都為真。