^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
^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
^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
^Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002. ISBN 81-7808-830-4.
Rigo, Michel. Advanced graph theory and combinatorics. London, UK. 2008: 90–92. ISBN 978-0-387-79711-3.|author1=和|last1=只需其一 (帮助)
Bondy, J. A. Graph theory. New York: Springer. 2008: 359-363. ISBN 978-1-84628-969-9.|author1=和|last1=只需其一 (帮助)
二月 09, 2023
布鲁克斯定理, 此條目包含過多行話或專業術語, 可能需要簡化或提出進一步解釋, 2021年12月16日, 請在討論頁中發表對於本議題的看法, 並移除或解釋本條目中的行話, 图论中, 布鲁克定理, 英語, brooks, theorem, 描述了图的着色数与图中最大度数的关系, 提供了图着色数的一个上界, 定理斷言, 若连通图g中, 每個頂點都不多於Δ個鄰居, 且g不是完全图或奇环, 则g可以被Δ, 着色, 即g可以被染成Δ种颜色, 使得相邻点颜色互不相同, 目录, 背景, 图染色数, 图最小染色数和图最大度数关系,. 此條目包含過多行話或專業術語 可能需要簡化或提出進一步解釋 2021年12月16日 請在討論頁中發表對於本議題的看法 並移除或解釋本條目中的行話 图论中 布鲁克定理 英語 Brooks theorem 1 描述了图的着色数与图中最大度数的关系 提供了图着色数的一个上界 定理斷言 若连通图G中 每個頂點都不多於D個鄰居 且G不是完全图或奇环 则G可以被D 着色 即G可以被染成D种颜色 使得相邻点颜色互不相同 目录 1 背景 1 1 图染色数 1 2 图最小染色数和图最大度数关系 2 定理敍述 3 定理证明 3 1 G不是k正则图 3 2 G是k正则图但有割点 3 3 G是k正则图且無割点 4 参考文献背景 编辑图染色数 编辑 主条目 圖着色問題 考慮為G displaystyle G 的頂點染色 而使每邊的兩端不同色 以符號表示 條件是 对于图G displaystyle G 中任意两个顶点u v displaystyle u v 如果u v E G displaystyle uv in E G 那么u v displaystyle u v 所染成的颜色不同 对于图G displaystyle G 如果存在一个k displaystyle k 种颜色的恰当染色方案 称G displaystyle G 可染k displaystyle k 色 或 k displaystyle k 可着色 在所有满足条件的k Z displaystyle k in mathbb Z 中 称最小的那个k displaystyle k 稱為染色數x G displaystyle chi G 图最小染色数和图最大度数关系 编辑 圖G displaystyle G 的最大度記作D G displaystyle Delta G 对于任意图G displaystyle G x G D G 1 displaystyle chi G leq Delta G 1 始终成立 但是这个上界并不足够紧 而布鲁克斯定理提供了一个更紧的上界 图着色问题有一个贪心染色法 greedy coloring 2 将颜色标号为1 2 D G 1 displaystyle 1 2 Delta G 1 将图G的顶点排序为v 1 v 2 v n displaystyle v 1 v 2 v n 按顺序对顶点v i displaystyle v i 进行染色 染v i displaystyle v i 時 其邻居至多有D G displaystyle Delta G 個 所以已染色的鄰居中 至多衹用了D G displaystyle Delta G 種色 尚有某種色未用 可选择該種色作为v i displaystyle v i 的着色 根据布鲁克斯定理 不等式x G D G 1 displaystyle chi G leq Delta G 1 取等当且仅当G为完全图或奇环 当G为完全图时 x G n displaystyle chi G n D G n 1 displaystyle Delta G n 1 当G为奇环时 x G 3 displaystyle chi G 3 D G 2 displaystyle Delta G 2 均满足x G D G 1 displaystyle chi G Delta G 1 定理敍述 编辑如果G displaystyle G 是一个连通图 而且G displaystyle G 不是奇环C 2 n 1 displaystyle C 2n 1 或者完全图K n displaystyle K n 那么x G D G displaystyle chi G leq Delta G 其中x G displaystyle chi G 是图G displaystyle G 的最小着色数 D G displaystyle Delta G 是图G displaystyle G 中点的最大度数 定理证明 编辑此處给出洛瓦兹 拉兹洛 3 的一个证明 亦見諸 4 记k D G displaystyle k Delta G 当k 0 1 displaystyle k 0 1 的时候 G displaystyle G 是完全图 当k 2 displaystyle k 2 的时候 由于G displaystyle G 不是奇环 那么G displaystyle G 要么是一条路径P displaystyle P 或者偶环C 2 n displaystyle C 2n 此时x G 2 D G displaystyle chi G 2 Delta G 所以 衹需从k 3 displaystyle k geq 3 开始考虑 分下列三種情況 G不是k正则图 编辑 选择G中度小于k的点v 0 displaystyle v 0 最后染色 由於G displaystyle G 連通 有某種排序方式使得除v 0 displaystyle v 0 之外 每个节点都有一个邻点排在它的后面 例如从v 0 displaystyle v 0 出发对图G进行深度优先遍历 按照DFS序的逆序排列G的节点 故只有小于等于k 1个邻点排在它前面 这样 只有小于等于k 1个邻点排在它前面 而d v 0 k 1 displaystyle d v 0 leq k 1 故也只有小于等于k 1个邻点排在它前面 按該次序的貪心染色最多衹用k種色 若要避免術語 DFS 可以构造下列集合 S i displaystyle S i 直到里面包含G displaystyle G 中所有顶点 S 0 v 0 S 1 N v 0 S 2 N S 1 S 1 S 0 S l N S l 1 S l 1 S l 2 S 0 displaystyle begin aligned S 0 amp v 0 S 1 amp N v 0 S 2 amp N S 1 S 1 S 0 dots S l amp N S l 1 S l 1 S l 2 dots S 0 end aligned 然后可以用上述贪心染色算法对图G displaystyle G 进行染色 染色顺序为 先染S l displaystyle S l 中的点 再染S l 1 displaystyle S l 1 中的点 一直这么下去直到染完S 0 displaystyle S 0 中的点 这种算法使用l displaystyle l 种颜色就能完成 当染到点u S i i 0 displaystyle u in S i i neq 0 時 u displaystyle u 在S i 1 displaystyle S i 1 中至少有一个邻居 所以u displaystyle u 邻居中至多只有k 1 displaystyle k 1 个被染色过 所以能对u displaystyle u 进行染色 当染点v 0 displaystyle v 0 的时候 由于d v 0 lt k displaystyle d v 0 lt k v 0 displaystyle v 0 邻居中至多只有k 1 displaystyle k 1 个被染色过 所以同样能对v 0 displaystyle v 0 进行染色 所以用k displaystyle k 种颜色对G displaystyle G 恰当染色 G是k正则图但有割点 编辑 假设割点为u displaystyle u 那么G G u displaystyle G G u 就不是连通图 设G displaystyle G 有t displaystyle t 个連通分量G 1 G 2 G t displaystyle G 1 G 2 dots G t 对于任意一个连通分支G i displaystyle G i 考虑H i G i u displaystyle H i G i cup u 由于u displaystyle u 在H i displaystyle H i 的度數小於k displaystyle k D H i lt k displaystyle Delta H i lt k 由前述贪心染色算法可知 H i displaystyle H i 可染k displaystyle k 色 然后只需令这些染色方案中u displaystyle u 所染的颜色一样 如果不一样 将所有点染的颜色重新排列一下 就能拼成G displaystyle G 的染色方案 所以可用k displaystyle k 种颜色对G displaystyle G 恰当染色 G是k正则图且無割点 编辑 由于G displaystyle G 中没有割点 G displaystyle G 是2连通图 英语 Biconnected graph 斷言可以找到一个顶点u displaystyle u 使得它有两个邻点v 1 v 2 displaystyle v 1 v 2 满足v 1 v 2 displaystyle v 1 v 2 不相邻 且G v 1 v 2 displaystyle G v 1 v 2 连通 如果这样的u v 1 v 2 displaystyle u v 1 v 2 存在 就可以先將v 1 v 2 displaystyle v 1 v 2 染成同色 然後貪心地為其他點染色 使u displaystyle u 最後染 这样貪心染法衹用不超過k displaystyle k 種色 因为除u displaystyle u 之外的点 只有小于等于k 1 displaystyle k 1 个邻点排在它前面 而u displaystyle u 又有兩個邻点v 1 v 2 displaystyle v 1 v 2 同色 故u displaystyle u 的鄰域衹用前k 1 displaystyle k 1 種色 尚有餘下顏色可用 以下說明為何有此種u v 1 v 2 displaystyle u v 1 v 2 如果G displaystyle G 是3连通的 則可以選取距離為2的兩點v 1 v 2 displaystyle v 1 v 2 因為G displaystyle G 不是完全圖 及其公共鄰點u displaystyle u 如此有v 1 v 2 E G displaystyle v 1 v 2 notin E G 又由于G displaystyle G 是3连通的 G v 1 v 2 displaystyle G v 1 v 2 是连通图 即為所求 僅剩G displaystyle G 是2连通但不是3连通的情況 此時有頂點u displaystyle u 使G u displaystyle G u 僅為1連通 考慮G u displaystyle G u 各個雙連通分支 英语 biconnected component 之間以割點連接 組成一棵樹 因為G u displaystyle G u 不是2連通 該樹至少有兩個叶区块 leaf block 設為B 1 B 2 displaystyle B 1 B 2 又因为G displaystyle G 无割点 所以G u displaystyle G u 的每一个叶区块中 必有某個非割點與u displaystyle u 相邻 於是 可以在B 1 B 2 displaystyle B 1 B 2 中各取u displaystyle u 的鄰點v 1 v 2 displaystyle v 1 v 2 使v 1 v 2 displaystyle v 1 v 2 不是G u displaystyle G u 的割点 如此 v 1 v 2 displaystyle v 1 v 2 不相邻 否則B 1 B 2 displaystyle B 1 B 2 屬同一雙連通分支 且G u v 1 v 2 displaystyle G u v 1 v 2 连通 因为k 3 displaystyle k geq 3 所以G v 1 v 2 displaystyle G v 1 v 2 连通 證畢 参考文献 编辑 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 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 Lovasz 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 Douglas B West Introduction to Graph Theory Pearson Enducation 2002 ISBN 81 7808 830 4 Rigo Michel Advanced graph theory and combinatorics London UK 2008 90 92 ISBN 978 0 387 79711 3 author1 和 last1 只需其一 帮助 Bondy J A Graph theory New York Springer 2008 359 363 ISBN 978 1 84628 969 9 author1 和 last1 只需其一 帮助 取自 https zh wikipedia org w index php title 布鲁克斯定理 amp oldid 70055043, 维基百科,wiki,书籍,书籍,图书馆,