跳转到内容

布鲁克斯定理

维基百科,自由的百科全书

图论中,布鲁克定理(英语: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.