布鲁克斯定理

圖的色數與最大度之關係

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