跳转到内容

布鲁克斯定理

维基百科,自由的百科全书
(重定向自布鲁克定理

图论中,布鲁克定理(英語: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」,可以构造下列集合直到里面包含中所有顶点:

然后可以用上述贪心染色算法对图进行染色。染色顺序为:先染中的点,再染中的点,一直这么下去直到染完中的点。这种算法使用种颜色就能完成。当染到点時,中至少有一个邻居,所以邻居中至多只有个被染色过,所以能对进行染色。

当染点的时候,由于邻居中至多只有个被染色过,所以同样能对进行染色。所以用种颜色对恰当染色。

Gk正则图但有割点

假设割点,那么就不是连通图,设連通分量。对于任意一个连通分支,考虑。由于的度數小於。由前述贪心染色算法可知,可染色。然后只需令这些染色方案中所染的颜色一样(如果不一样,将所有点染的颜色重新排列一下),就能拼成的染色方案,所以可用种颜色对恰当染色。

Gk正则图且無割点

由于中没有割点,2连通图英语Biconnected graph。斷言可以找到一个顶点,使得它有两个邻点,满足不相邻,且连通。如果这样的存在,就可以先將染成同色,然後貪心地為其他點染色,使最後染。这样貪心染法衹用不超過種色,因为除之外的点,只有小于等于个邻点排在它前面,而又有兩個邻点同色,故的鄰域衹用前種色,尚有餘下顏色可用。以下說明為何有此種

如果是3连通的,則可以選取距離為2的兩點(因為不是完全圖),及其公共鄰點。如此有,又由于是3连通的,是连通图,即為所求。

僅剩是2连通但不是3连通的情況。此時有頂點使僅為1連通,考慮各個雙連通分支英语biconnected component,之間以割點連接,組成一棵樹。因為不是2連通,該樹至少有兩個叶区块(leaf block),設為。又因为无割点,所以的每一个叶区块中,必有某個非割點與相邻。於是,可以在中各取的鄰點,使不是的割点。如此,不相邻(否則屬同一雙連通分支),且连通。因为,所以连通。證畢。

参考文献

  1. ^ Brooks, R. L., On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society英语Mathematical Proceedings of the Cambridge Philosophical Society, 1941, 37 (2): 194–197, doi:10.1017/S030500410002168X 
  2. ^ Mitchem, John, On various algorithms for estimating the chromatic number of a graph, The Computer Journal英语The Computer Journal, 1976, 19 (2): 182–183, MR 0437376, doi:10.1093/comjnl/19.2.182 
  3. ^ Lovász, L., Three short proofs in graph theory, Journal of Combinatorial Theory英语Journal of Combinatorial Theory, Series B, 1975, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1 
  4. ^ Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002. ISBN 81-7808-830-4.