圖論中,布魯克定理(英語:Brooks' theorem)[1] 描述了圖的着色數與圖中最大度數的關係,提供了圖着色數的一個上界。定理斷言,若連通圖G中,每個頂點都不多於Δ個鄰居,且G不是完全圖或奇環,則G可以被Δ-着色,即G可以被染成Δ種顏色,使得相鄰點顏色互不相同。
背景
圖染色數
考慮為 的頂點染色,而使每邊的兩端不同色。以符號表示,條件是:對於圖 中任意兩個頂點 ,如果 ,那麼 所染成的顏色不同。
對於圖 ,如果存在一個 種顏色的恰當染色方案,稱 可染 色(或「 可着色」)。在所有滿足條件的 中,稱最小的那個 稱為染色數 。
圖最小染色數和圖最大度數關係
圖 的最大度記作 。對於任意圖 , 始終成立。但是這個上界並不足夠緊。而布魯克斯定理提供了一個更緊的上界。
圖着色問題有一個貪心染色法(greedy coloring)[2],將顏色標號為 ,將圖G的頂點排序為 ,按順序對頂點 進行染色。染 時,其鄰居至多有 個,所以已染色的鄰居中,至多衹用了 種色,尚有某種色未用,可選擇該種色作為 的着色。
根據布魯克斯定理,不等式 取等當且僅當G為完全圖或奇環。當G為完全圖時, , ,當G為奇環時, , ,均滿足 。
定理敍述
定理證明
此處給出洛瓦茲·拉茲洛[3]的一個證明(亦見諸[4])。
記 。當 的時候, 是完全圖。當 的時候,由於 不是奇環,那麼 要麼是一條路徑 ,或者偶環 。此時 。所以,衹需從 開始考慮。分下列三種情況:
G不是k正則圖
選擇G中度小於k的點 最後染色。由於 連通,有某種排序方式使得除 之外,每個節點都有一個鄰點排在它的後面:例如從 出發對圖G進行深度優先遍歷,按照DFS序的逆序排列G的節點。故只有小於等於k - 1個鄰點排在它前面,這樣,只有小於等於k - 1個鄰點排在它前面,而 ,故也只有小於等於k - 1個鄰點排在它前面,按該次序的貪心染色最多衹用k種色。
若要避免術語「DFS」,可以構造下列集合 直到裡面包含 中所有頂點:
-
然後可以用上述貪心染色算法對圖 進行染色。染色順序為:先染 中的點,再染 中的點,一直這麼下去直到染完 中的點。這種算法使用 種顏色就能完成。當染到點 時, 在 中至少有一個鄰居,所以 鄰居中至多只有 個被染色過,所以能對 進行染色。
當染點 的時候,由於 , 鄰居中至多只有 個被染色過,所以同樣能對 進行染色。所以用 種顏色對 恰當染色。
G是k正則圖但有割點
假設割點為 ,那麼 就不是連通圖,設 有 個連通分量 。對於任意一個連通分支 ,考慮 。由於 在 的度數小於 , 。由前述貪心染色算法可知, 可染 色。然後只需令這些染色方案中 所染的顏色一樣(如果不一樣,將所有點染的顏色重新排列一下),就能拼成 的染色方案,所以可用 種顏色對 恰當染色。
G是k正則圖且無割點
由於 中沒有割點, 是2連通圖。斷言可以找到一個頂點 ,使得它有兩個鄰點 ,滿足 不相鄰,且 連通。如果這樣的 存在,就可以先將 染成同色,然後貪心地為其他點染色,使 最後染。這樣貪心染法衹用不超過 種色,因為除 之外的點,只有小於等於 個鄰點排在它前面,而 又有兩個鄰點 同色,故 的鄰域衹用前 種色,尚有餘下顏色可用。以下說明為何有此種 。
如果 是3連通的,則可以選取距離為2的兩點 (因為 不是完全圖),及其公共鄰點 。如此有 ,又由於 是3連通的, 是連通圖,即為所求。
僅剩 是2連通但不是3連通的情況。此時有頂點 使 僅為1連通,考慮 各個雙連通分支,之間以割點連接,組成一棵樹。因為 不是2連通,該樹至少有兩個葉區塊(leaf block),設為 。又因為 無割點,所以 的每一個葉區塊中,必有某個非割點與 相鄰。於是,可以在 中各取 的鄰點 ,使 不是 的割點。如此, 不相鄰(否則 屬同一雙連通分支),且 連通。因為 ,所以 連通。證畢。
參考文獻
- ^ Brooks, R. L., On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society, 1941, 37 (2): 194–197, doi:10.1017/S030500410002168X
- ^ Mitchem, John, On various algorithms for estimating the chromatic number of a graph, The Computer Journal, 1976, 19 (2): 182–183, MR 0437376, doi:10.1093/comjnl/19.2.182
- ^ Lovász, L., Three short proofs in graph theory, Journal of Combinatorial Theory, Series B, 1975, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1
- ^ Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002. ISBN 81-7808-830-4.