圖論中,布魯克定理(英語: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」,可以構造下列集合
直到裡面包含
中所有頂點:
![{\displaystyle {\begin{aligned}S_{0}&={v_{0}}\\S_{1}&=N(v_{0})\\S_{2}&=N(S_{1})-S_{1}-S_{0}\\\dots \\S_{l}&=N(S_{l-1})-S_{l-1}-S_{l-2}\dots -S_{0}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e24afb01a4b1612cfd84fb543737774035850dc4)
然後可以用上述貪心染色算法對圖
進行染色。染色順序為:先染
中的點,再染
中的點,一直這麼下去直到染完
中的點。這種算法使用
種顏色就能完成。當染到點
時,
在
中至少有一個鄰居,所以
鄰居中至多只有
個被染色過,所以能對
進行染色。
當染點
的時候,由於
,
鄰居中至多只有
個被染色過,所以同樣能對
進行染色。所以用
種顏色對
恰當染色。
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.