查看“︁布鲁克斯定理”︁的源代码

{{Cleanup-jargon|time=2021-12-16T14:47:52+00:00}}

[[图论]]中，'''布鲁克定理'''（{{lang-en|'''Brooks' theorem'''}}）<ref>{{citation
 | last = Brooks | first = R. L. | authorlink = R. Leonard Brooks
 | journal = {{tsl|en|Mathematical Proceedings of the Cambridge Philosophical Society||Mathematical Proceedings of the Cambridge Philosophical Society}}
 | pages = 194–197
 | title = On colouring the nodes of a network
 | volume = 37
 | doi = 10.1017/S030500410002168X
 | year = 1941| issue = 2 }}</ref> 描述了图的[[图着色问题|着色数]]与图中[[度 (图论)|最大度数]]的关系，提供了图着色数的一个上界。定理斷言，若[[连通图]]''G''中，每個頂點都不多於Δ個鄰居，且''G''不是[[完全图]]或[[环 (图论)|奇环]]，则''G''可以被Δ-着色，即''G''可以被染成Δ种颜色，使得相邻点颜色互不相同。

== 背景 ==

=== 图染色数 ===
{{main|圖着色問題}}
考慮為<math>G</math>的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图<math>G</math>中任意两个顶点<math>u,v</math>，如果<math>uv\in E(G)</math>，那么<math>u,v</math>所染成的颜色不同。

对于图<math>G</math>，如果存在一个<math>k</math>种颜色的恰当染色方案，称<math>G</math>可染<math>k</math>色（或「<math>k</math>可着色」）。在所有满足条件的<math>k\in \mathbb{Z_+}</math>中，称最小的那个<math>k</math>稱為染色數<math>\chi(G)</math>。

=== 图最小染色数和图最大度数关系 ===
圖<math>G</math>的最大[[度 (圖論)|度]]記作<math>\Delta (G)</math>。对于任意图<math>G</math>，<math>\chi(G)\le \Delta(G)+1</math>始终成立。但是这个上界并不足够紧。而布鲁克斯定理提供了一个更紧的上界。

图着色问题有一个[[貪心算法|贪心染色法]]（{{lang|en|greedy coloring}}）<ref>{{citation
 | last = Mitchem | first = John
 | doi = 10.1093/comjnl/19.2.182
 | issue = 2
 | journal = {{tsl|en|The Computer Journal||The Computer Journal}}
 | mr = 0437376
 | pages = 182–183
 | title = On various algorithms for estimating the chromatic number of a graph
 | volume = 19
 | year = 1976
 }}</ref>，将颜色标号为<math>1,2,..., \Delta(G) +1</math>，将图''G''的顶点排序为<math>v_{1},v_{2},...,v_{n}</math>，按顺序对顶点<math>v_{i}</math>进行染色。染<math>v_i</math>時，其邻居至多有<math>\Delta(G)</math>個，所以已染色的鄰居中，至多衹用了<math>\Delta(G)</math>種色，尚有某種色未用，可选择該種色作为<math>v_{i}</math>的着色。

根据布鲁克斯定理，不等式<math>\chi(G)\leq \Delta(G)+1</math>取等当且仅当''G''为完全图或奇环。当''G''为完全图时，<math>\chi(G)=n</math>，<math>\Delta(G)=n-1</math>，当''G''为奇环时，<math>\chi(G)=3</math>，<math>\Delta(G)=2</math>，均满足<math>\chi(G)=\Delta(G)+1</math>。

== 定理敍述 ==
如果<math>G</math>是一个[[连通图]]，而且<math>G</math>不是[[環 (圖論)|奇环]]<math>C_{2n+1}</math>或者[[完全圖|完全图]]<math>K_n</math>，那么<math>\chi(G)\le \Delta(G)</math>。其中<math>\chi(G)</math>是图<math>G</math>的最小着色数，<math>\Delta(G)</math>是图<math>G</math>中点的最大度数。

== 定理证明 ==
此處给出[[洛瓦兹·拉兹洛]]<ref>{{citation
 | last = Lovász | first = L. | author-link = László Lovász
 | doi = 10.1016/0095-8956(75)90089-1
 | journal = {{tsl|en|Journal of Combinatorial Theory||Journal of Combinatorial Theory}} | series = Series B
 | pages = 269–271
 | title = Three short proofs in graph theory
 | volume = 19
 | year = 1975| issue = 3 }}</ref>的一个证明（亦見諸<ref>{{cite book |author1=Douglas B.West |title=Introduction to Graph Theory |date=2002 |publisher=Pearson Enducation |isbn=81-7808-830-4}}</ref>）。

记<math>k=\Delta(G)</math>。当<math>k=0,1</math>的时候，<math>G</math>是完全图。当<math>k=2</math>的时候，由于<math>G</math>不是奇环，那么<math>G</math>要么是一条路径<math>P</math>，或者偶环<math>C_{2n}</math>。此时<math>\chi(G)=2=\Delta(G)</math>。所以，衹需从<math>k\ge3</math>开始考虑。分下列三種情況：

=== ''G''不是''k''正则图 ===

选择''G''中度小于''k''的点<math>v_0</math>最后染色。由於<math>G</math>連通，有某種排序方式使得除<math>v_0</math>之外，每个节点都有一个邻点排在它的后面：例如从<math>v_0</math>出发对图''G''进行[[深度优先搜索|深度优先遍历]]，按照[[深度优先搜索|DFS序]]的逆序排列''G''的节点。故只有小于等于''k'' - 1个邻点排在它前面，这样，只有小于等于''k'' - 1个邻点排在它前面，而<math>d(v_0)\leq k-1</math>，故也只有小于等于''k'' - 1个邻点排在它前面，按該次序的貪心染色最多衹用''k''種色。

若要避免術語「DFS」，可以构造下列集合<math>\{S_i\}</math>直到里面包含<math>G</math>中所有顶点：

:<math>\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}</math>

然后可以用上述贪心染色算法对图<math>G</math>进行染色。染色顺序为：先染<math>S_l</math>中的点，再染<math>S_{l-1}</math>中的点，一直这么下去直到染完<math>S_0</math>中的点。这种算法使用<math>l</math>种颜色就能完成。当染到点<math>u\in S_i(i\neq 0)</math>時，<math>u</math>在<math>S_{i-1}</math>中至少有一个邻居，所以<math>u</math>邻居中至多只有<math>k-1</math>个被染色过，所以能对<math>u</math>进行染色。

当染点<math>v_0</math>的时候，由于<math>d(v_0)<k</math>，<math>v_0</math>邻居中至多只有<math>k-1</math>个被染色过，所以同样能对<math>v_0</math>进行染色。所以用<math>k</math>种颜色对<math>G</math>恰当染色。

=== ''G''是''k''正则图但有割点 ===

假设[[割点]]为<math>u</math>，那么<math>G'=G-\{u\}</math>就不是连通图，设<math>G'</math>有<math>t</math>个[[連通分量 (圖論)|連通分量]]<math>G_1,G_2, \dots, G_t</math>。对于任意一个连通分支<math>G_i</math>，考虑<math>H_i=G_i\cup\{u\}</math>。由于<math>u</math>在<math>H_i</math>的度數小於<math>k</math>，<math>\Delta(H_i)<k</math>。由前述贪心染色算法可知，<math>H_i</math>可染<math>k</math>色。然后只需令这些染色方案中<math>u</math>所染的颜色一样（如果不一样，将所有点染的颜色重新排列一下），就能拼成<math>G</math>的染色方案，所以可用<math>k</math>种颜色对<math>G</math>恰当染色。

===''G''是''k''正则图且無割点===

由于<math>G</math>中没有割点，<math>G</math>是[[雙連通圖|2连通图]]。斷言可以找到一个顶点<math>u </math>，使得它有两个邻点<math>v_{1},v_{2}</math>，满足<math>v_{1},v_{2}</math>不相邻，且<math>G-\{v_{1},v_{2}\}</math>连通。如果这样的<math>u,v_{1},v_{2}</math>存在，就可以先將<math>v_{1},v_{2}</math>染成同色，然後貪心地為其他點染色，使<math>u</math>最後染。这样貪心染法衹用不超過<math>k</math>種色，因为除<math>u</math>之外的点，只有小于等于<math>k-1</math>个邻点排在它前面，而<math>u</math>又有兩個邻点<math>v_{1},v_{2}</math>同色，故<math>u</math>的鄰域衹用前<math>k-1</math>種色，尚有餘下顏色可用。以下說明為何有此種<math>u,v_{1},v_{2}</math>。

如果<math>G</math>是3连通的，則可以選取距離為2的兩點<math>v_1, v_2</math>（因為<math>G</math>不是完全圖），及其公共鄰點<math>u</math>。如此有<math>v_1 v_2\notin E(G)</math>，又由于<math>G</math>是3连通的，<math>G-\{v_1,v_2\}</math>是连通图，即為所求。

僅剩<math>G</math>是2连通但不是3连通的情況。此時有頂點<math>u</math>使<math>G - u</math>僅為1連通，考慮<math>G - u</math>各個{{le|雙連通分支|biconnected component}}，之間以割點連接，組成一棵樹。因為<math>G-u</math>不是2連通，該樹至少有兩個叶区块（{{lang|en|leaf block}}），設為<math>B_1, B_2</math>。又因为<math>G</math>无割点，所以<math>G-u</math>的每一个叶区块中，必有某個非割點與<math>u</math>相邻。於是，可以在<math>B_1, B_2</math>中各取<math>u</math>的鄰點<math>v_1, v_2</math>，使<math>v_{1},v_{2}</math>不是<math>G-u</math>的割点。如此，<math>v_{1},v_{2}</math>不相邻（否則<math>B_1, B_2</math>屬同一雙連通分支），且<math>G-\{u,v_{1},v_{2}\}</math>连通。因为<math>k \ge 3</math>，所以<math>G-\{v_{1},v_{2}\}</math>连通。證畢。

== 参考文献 ==
<references />
*{{cite book |author1=John Harris,Jeffry L. Hirst,Michael Mossinghoff |last1=Rigo |first1=Michel |title=Advanced graph theory and combinatorics |date=2008 |location=London, UK |isbn=978-0-387-79711-3 |pages=90-92}}
*{{cite book |author1=Adrian Bondy,U.S.R. Murty |last1=Bondy |first1=J. A. |title=Graph theory |url=https://archive.org/details/graphtheorygradu00bond |date=2008 |publisher=Springer |location=New York |isbn=978-1-84628-969-9 |pages=[https://archive.org/details/graphtheorygradu00bond/page/n363 359]-363}}
{{图论}}
[[Category:图染色]]
[[Category:组合数学]]
[[Category:理论计算机科学]]
[[Category:数学定理]]