色多项式
在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。
色多项式formula_1的值是在图formula_2中顶点的不同的formula_3-着色数目，是关于formula_3的多项式。
例如当图formula_2为一点时，formula_6。
性质.
给定formula_7阶图formula_2，色多项式formula_9是关于formula_3的多项式，且满足以下性质：
特别的，设formula_2有formula_18个连通分量，分别为formula_19，那么
递推公式.
给定图formula_2与formula_23，那么
formula_24
其中formula_25代表边收缩：令formula_26所连接的两个顶点计为formula_27和formula_28，而边收缩会使顶点formula_27和formula_28合并成一个新的顶点formula_31，并使原本与formula_27和formula_28相连的所有边都连到formula_31。
证明 假设formula_26所连接的两个顶点为formula_27和formula_28，考虑图formula_38。
所以图formula_38的不同着色方式数目为
formula_54
加点或减点.
若点formula_28在图formula_2上与其它所有点连边，则所有点的颜色都与该点的颜色互异，记除去顶点formula_28的图为formula_58。
formula_59
formula_60
在图formula_2的一边formula_26上添加点formula_28所得图记为formula_64，两端点着同色时有formula_65种着色法，两端点着不同色是有formula_66种着色法。
formula_67
补图.
若formula_2为有formula_7个顶点的图，且它的独立数<3，
formula_70
其中formula_71表示阶乘幂，formula_72为图formula_73中所含的完全子图formula_74的个数。
如右图，formula_73中有5个顶点，6条边，2个三角形，所以formula_76
生成维基百科快照图片，大概需要3-30秒！
如果网站内容有侵犯您的版权
请联系：pinbor@iissy.com
请联系：pinbor@iissy.com
Copyright ©2014 iissy.com, All Rights Reserved.