此條目包含過多
行話或專業術語,可能需要簡化或提出進一步解釋。 (2021年12月16日)請在
討論頁中發表對於本議題的看法,並移除或解釋本條目中的行話。
图论中,布鲁克定理(英語:Brooks' theorem)[1] 描述了图的着色数与图中最大度数的关系,提供了图着色数的一个上界。定理斷言,若连通图G中,每個頂點都不多於Δ個鄰居,且G不是完全图或奇环,则G可以被Δ-着色,即G可以被染成Δ种颜色,使得相邻点颜色互不相同。
考慮為
的頂點染色,而使每邊的兩端不同色。以符號表示,條件是:对于图
中任意两个顶点
,如果
,那么
所染成的颜色不同。
对于图
,如果存在一个
种颜色的恰当染色方案,称
可染
色(或「
可着色」)。在所有满足条件的
中,称最小的那个
稱為染色數
。
圖
的最大度記作
。对于任意图
,
始终成立。但是这个上界并不足够紧。而布鲁克斯定理提供了一个更紧的上界。
图着色问题有一个贪心染色法(greedy coloring)[2],将颜色标号为
,将图G的顶点排序为
,按顺序对顶点
进行染色。染
時,其邻居至多有
個,所以已染色的鄰居中,至多衹用了
種色,尚有某種色未用,可选择該種色作为
的着色。
根据布鲁克斯定理,不等式
取等当且仅当G为完全图或奇环。当G为完全图时,
,
,当G为奇环时,
,
,均满足
。
如果
是一个连通图,而且
不是奇环
或者完全图
,那么
。其中
是图
的最小着色数,
是图
中点的最大度数。
此處给出洛瓦兹·拉兹洛[3]的一个证明(亦見諸[4])。
记
。当
的时候,
是完全图。当
的时候,由于
不是奇环,那么
要么是一条路径
,或者偶环
。此时
。所以,衹需从
开始考虑。分下列三種情況:
选择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)
然后可以用上述贪心染色算法对图
进行染色。染色顺序为:先染
中的点,再染
中的点,一直这么下去直到染完
中的点。这种算法使用
种颜色就能完成。当染到点
時,
在
中至少有一个邻居,所以
邻居中至多只有
个被染色过,所以能对
进行染色。
当染点
的时候,由于
,
邻居中至多只有
个被染色过,所以同样能对
进行染色。所以用
种颜色对
恰当染色。
假设割点为
,那么
就不是连通图,设
有
个連通分量
。对于任意一个连通分支
,考虑
。由于
在
的度數小於
,
。由前述贪心染色算法可知,
可染
色。然后只需令这些染色方案中
所染的颜色一样(如果不一样,将所有点染的颜色重新排列一下),就能拼成
的染色方案,所以可用
种颜色对
恰当染色。
由于
中没有割点,
是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.