色多项式, 此條目需要补充更多来源, 2015年3月7日, 请协助補充多方面可靠来源以改善这篇条目, 无法查证的内容可能會因為异议提出而被移除, 致使用者, 请搜索一下条目的标题, 来源搜索, 网页, 新闻, 书籍, 学术, 图像, 以检查网络上是否存在该主题的更多可靠来源, 判定指引, 在代数图论中, 是乔治, 戴维, 伯克霍夫为了尝试证明四色定理而定义的一种多项式, displaystyle, 的值是在图g, displaystyle, 中顶点的不同的t, displaystyle, 着色数目, 是关于t, d. 此條目需要补充更多来源 2015年3月7日 请协助補充多方面可靠来源以改善这篇条目 无法查证的内容可能會因為异议提出而被移除 致使用者 请搜索一下条目的标题 来源搜索 色多项式 网页 新闻 书籍 学术 图像 以检查网络上是否存在该主题的更多可靠来源 判定指引 在代数图论中 色多项式是乔治 戴维 伯克霍夫为了尝试证明四色定理而定义的一种多项式 色多项式P G t displaystyle P G t 的值是在图G displaystyle G 中顶点的不同的t displaystyle t 着色数目 是关于t displaystyle t 的多项式 例如当图G displaystyle G 为一点时 P G t t displaystyle P G t t 目录 1 例子 2 性质 2 1 递推公式 2 2 加点或减点 2 3 补图 3 参考资料例子 编辑特殊图的色多项式 完全图K n displaystyle K n nbsp t t 1 t 2 t n 1 displaystyle t t 1 t 2 cdots t n 1 nbsp 树T n displaystyle T n nbsp t t 1 n 1 displaystyle t t 1 n 1 nbsp 环C n displaystyle C n nbsp t 1 n 1 n t 1 displaystyle t 1 n 1 n t 1 nbsp 佩特森圖 t t 1 t 2 t 7 12 t 6 67 t 5 230 t 4 529 t 3 814 t 2 775 t 352 displaystyle t t 1 t 2 left t 7 12t 6 67t 5 230t 4 529t 3 814t 2 775t 352 right nbsp 性质 编辑给定n displaystyle n nbsp 阶图G displaystyle G nbsp 色多项式P G t displaystyle P G t nbsp 是关于t displaystyle t nbsp 的多项式 且满足以下性质 1 多项式P G t displaystyle P G t nbsp 的次数为n displaystyle n nbsp t n displaystyle t n nbsp 的系数为1 t n 1 displaystyle t n 1 nbsp 的系数为 E G displaystyle E G nbsp t c t n displaystyle t c dots t n nbsp 的系数不为0且正负交替出现 特别的 设G displaystyle G nbsp 有c displaystyle c nbsp 个连通分量 分别为G 1 G c displaystyle G 1 dots G c nbsp 那么 t 0 t c 1 displaystyle t 0 dots t c 1 nbsp 的系数为0 P G k 1 n P G k displaystyle P G prod k 1 n P G k nbsp 递推公式 编辑 nbsp 对于边uv的边收缩 G uv 示意图 给定图G displaystyle G nbsp 与e E G displaystyle e in E G nbsp 那么 P G k P G e k P G e k displaystyle P G k P G e k P G e k nbsp 其中G e displaystyle G e nbsp 代表边收缩 令e displaystyle e nbsp 所连接的两个顶点计为u displaystyle u nbsp 和v displaystyle v nbsp 而边收缩会使顶点u displaystyle u nbsp 和v displaystyle v nbsp 合并成一个新的顶点w displaystyle w nbsp 并使原本与u displaystyle u nbsp 和v displaystyle v nbsp 相连的所有边都连到w displaystyle w nbsp 证明 2 假设e displaystyle e nbsp 所连接的两个顶点为u displaystyle u nbsp 和v displaystyle v nbsp 考虑图G e displaystyle G e nbsp 当u displaystyle u nbsp 和v displaystyle v nbsp 的颜色相同时 这种着色方式也是G e displaystyle G e nbsp 的一种合理着色方式 反之亦然 所以对图G e displaystyle G e nbsp 将u displaystyle u nbsp 和v displaystyle v nbsp 染上相同颜色的着色方式有P G e k displaystyle P G e k nbsp 种 当u displaystyle u nbsp 和v displaystyle v nbsp 的颜色不同时 这种着色方式也是G displaystyle G nbsp 的一种合理着色方式 反之亦然 所以对图G e displaystyle G e nbsp 将u displaystyle u nbsp 和v displaystyle v nbsp 染上不同颜色的着色方式有P G k displaystyle P G k nbsp 种 所以图G e displaystyle G e nbsp 的不同着色方式数目为 P G e k P G e k P G k displaystyle P G e k P G e k P G k nbsp 加点或减点 编辑 若点v displaystyle v nbsp 在图G displaystyle G nbsp 上与其它所有点连边 则所有点的颜色都与该点的颜色互异 记除去顶点v displaystyle v nbsp 的图为G v displaystyle G v nbsp P G t t P G v t 1 displaystyle P G t tP G v t 1 nbsp P K n t t P K n 1 t 1 t t 1 t 2 t n 1 displaystyle P K n t tP K n 1 t 1 t t 1 t 2 t n 1 nbsp 在图G displaystyle G nbsp 的一边e displaystyle e nbsp 上添加点v displaystyle v nbsp 所得图记为G v e displaystyle G v e nbsp 两端点着同色时有 t 1 P G e displaystyle t 1 P G cdot e nbsp 种着色法 两端点着不同色是有 t 2 P G displaystyle t 2 P G nbsp 种着色法 P G v e t 2 P G t 1 P G e displaystyle P G v e t 2 P G t 1 P G cdot e nbsp 3 补图 编辑 nbsp L G displaystyle overline L overline G nbsp 为G displaystyle G nbsp 的补图的线图的补图 若G displaystyle G nbsp 为有n displaystyle n nbsp 个顶点的图 且它的独立数 lt 3 P G t t n a 1 t n 1 a 2 t n 2 a n 2 t n 2 displaystyle P G t t n a 1 t n 1 a 2 t n 2 a frac n 2 t frac n 2 nbsp 4 其中 t n displaystyle t n nbsp 表示阶乘幂 a i displaystyle a i nbsp 为图L G displaystyle overline L overline G nbsp 中所含的完全子图K i displaystyle K i nbsp 的个数 如右图 L G displaystyle overline L overline G nbsp 中有5个顶点 6条边 2个三角形 所以P G t t 6 5 t 5 6 t 4 2 t 3 displaystyle P G t t 6 5 t 5 6 t 4 2 t 3 nbsp 参考资料 编辑 Whitney Hassler The coloring of graphs Annals of Mathematics JSTOR 1932 688 718 Harris John Hirst Jeffry L Mossinghoff Michael Combinatorics and Graph Theory Undergraduate Texts in Mathematics Springer Verlag New York 98 99 2008 ISBN 978 0 387 79711 3 doi 10 1007 978 0 387 79711 3 林翠琴 图的色多项式的几个递推公式 数学杂志 1987 3 2015 03 07 原始内容存档于2016 03 04 刘儒英 关于图的色多项式 青海师范大学学报 自然科学版 1986 Z1 2015 03 07 原始内容存档于2019 06 16 取自 https zh wikipedia org w index php title 色多项式 amp oldid 72709751, 维基百科,wiki,书籍,书籍,图书馆,