图着色问题
本帖最后由 fungarwai 于 2014-5-17 19:22 编辑有关知识：https://en.wikipedia.org/wiki/Chromatic_polynomial
如邻接矩阵为
\begin{pmatrix}0 & 1 & 0\\1 & 0 & 1\\0 & 1 & 0\end{pmatrix}
http://bbs.emath.ac.cn/forum.php?mod=attachment&aid=NTQzNHw0NzhjY2YyZXwxNDAwMzI1MTY4fDg2ODZ8NTQzNA%3D%3D&noupdate=yes
$P(P_3,t)=t(t-1)^2$
问题是如何单从邻接矩阵计算出该图的色多项式。 Calculating the chromatic polynomial of a graph is at least an NP-complete problem. 染色问题确实很迷人。
楼主的例子很简单，直接根据组合原理中的乘法公式就能得出那个多项式。
不过更复杂的图，就比较困难了，一般需要将图进行分解，主要有递推法和理想子图法。楼主给的链接中也说得很清楚了，常用的是用递推法求色多项式。
记G-e表示从图G中仅仅删除边e，G+e从图G中增加边e，G/e表示将图G中的边e所关联的两个顶点合并为一个点，并删除该边。
1. 减边法
P(G,k)=P(G-e,k)-P(G/e,k) (递推直到全部为零图)
如果边比较少，那么这个递推层数就会较少，计算量就小，因而这个公式适合求稀疏图的色多项式。
这个递推公式的意义非常直观，当删除一条边的时候，该边所关联的两个顶点就能够同色了，因此总的染色方法会多出一部分，多出的方法数就是同色的情况数，因此要减去同色的情况（即两顶点合并的情况）。
2. 加边法
将上式右端第二项移到左边，于是有了加边法
P(G,k)=P(G+e,k)+P(G/e,k)(递推直到全部为完全图)
边比较多的话，可增加的边就会少些，于是递推层数就少，计算量就小，因而这个公式适合求稠密图的色多项式。
由于边和顶点互为对偶关系，所以上述问题如果进一步深化，可以问两个更复杂点的问题：
1）若相邻边也不能同色，问用t种色彩将顶点与边染色的方法数有多少？
2）若相邻边也不能同色，且不能同与之关联的顶点同色，问用t种色彩将顶点与边染色的方法数有多少？
页:
[1]