第10章 著色、Clique與頂點覆蓋
10.1 上界要有做法，下界要有理由
正常頂點著色給每個頂點一種顏色，且每條邊的兩端異色。最少所需顏色數稱 χ(G)。Clique（團）是任兩個不同頂點皆相鄰的頂點集，最大大小記 ω(G)。團內顏色全不同，故 χ≥ω。給出合法 k 色配置，只推出 χ≤k；要證恰需 k 色，還須證任何至多 k−1 色的配置都不合法。空頂點圖約定 χ=0；非空無邊圖只需一色。
頂點覆蓋 C 要求每條邊至少一端在 C。補集 S 是獨立集，因為其中任兩點若相鄰，就有一條邊未被 C 覆蓋。反過來，獨立集的補集會覆蓋每條邊。|C|=|V|−|S|，因此最大獨立集大小為 α(G) 時，最小頂點覆蓋大小 τ(G)=|V|−α(G)。一組覆蓋給 τ 的上界；有 k 邊的匹配則給 τ≥k，因為每條匹配邊都需選到一端，而且這些端點互不相同。
「極小覆蓋」是刪掉任何點就不再覆蓋，「最小覆蓋」比較所有覆蓋的大小；同理，不能擴張的團未必是最大的團。小圖可用具體配置和相等的上下界，也可逐一排除更小候選。
10.2 四個例題
例題1 五環的色數高於最大團
五環 AB、BC、CD、DE、AE 沒有三角形，最大團大小 2。若只兩色，沿 A,B,C,D,E 交替使 A、E 同色，違反 AE。改用 A,C 第一色、B,D 第二色、E 第三色，合法，故 χ=3>ω=2。
例題2 四環的三個不同最優值
四環 A,B,C,D,A 可把 {A,C} 與 {B,D} 著兩色；一條邊阻止一色，故 χ=2。沒有三角形且有邊，故 ω=2。{A,C} 覆蓋全邊，而匹配 {AB,CD} 逼至少兩點，所以 τ=2。
例題3 不能刪點的覆蓋仍可能太大
星形 AB、AC、AD。{B,C,D} 覆蓋所有邊，少任一葉就漏該邊，故極小；但只取中心 {A} 也覆蓋，最小大小為 1。
例題4 貪婪著色依賴頂點順序
四點道路 A,B,C,D，按 A、D、B、C 順序每次取可用最小色。A、D 得色 1；B 鄰 A 得 2；C 鄰 B、D 已有 2、1，只能得 3。換成按道路順序就可兩色；貪婪一次不是最優證明。
10.3 練習
- B10-C10-Q01 三角形的 χ、ω 各是多少？
- B10-C10-Q02 三角形最少幾個點才覆蓋所有邊？
- B10-C10-Q03 只有 AB、CD 兩條分離邊時，一點能覆蓋全部嗎？
- B10-C10-Q04 五點道路 A,B,C,D,E，給最大獨立集並證明大小。
- B10-C10-Q05 上題最小頂點覆蓋大小？
- B10-C10-Q06 四點無邊圖的 χ、ω、τ？
- B10-C10-Q07 若找到合法四色配置，能宣布色數等於 4 嗎？
- B10-C10-Q08 若一個圖含四點團，能宣布全圖剛好需要四色嗎？
- B10-C10-Q09 若覆蓋 C 再加入一個頂點，還是覆蓋嗎？
- B10-C10-Q10 星形的葉 B、C 是否都要取才能形成大小 2 的團？
10.4 完整解答
Q01
任兩點相鄰，三點成團，故 ω=3 且至少三色；每點各一色可行，故 χ=3。
Q02
選一點只碰兩邊，另外一邊漏掉；任選兩點皆可，所以最小大小 2。
Q03
不能，一點只會屬於其中一條邊。取 A、C 達到兩點，最少就是 2。
Q04
取 {A,C,E}，任兩點不相鄰。有兩條不交邊 AB、CD，每條至多取一端，再加 E，至多 3 點，所以達最大。
Q05
{A,C,E} 的補集 {B,D} 覆蓋。由最大獨立集大小 3，最小覆蓋為 5−3=2。
Q06
所有點可同色；單點成團但兩點不成團；空集合已覆蓋零條邊。因此依次是 1、1、0。
Q07
不能，只能說 χ≤4。四點道路的四個頂點各用一色也合法，但它可以兩色著色。若要證色數為 4，還須證至多三色無法合法配置。
Q08
只能說至少四色。全圖其他邊可能逼更多色，例如五點完全圖含四點團卻需要五色。
Q09
是。原來每條邊已至少有一端在 C，加入頂點不會移除原有端點。若加入的是 C 原先未含的頂點，集合大小增加 1。
Q10
不是。B、C 互不相鄰，兩葉不能成團；取中心 A 和任一葉才有一條邊，形成大小 2 的團。