图着色问题

fungarwai

有关知识：https://en.wikipedia.org/wiki/Chromatic_polynomial

如邻接矩阵为

\begin{pmatrix}0 & 1 & 0\\1 & 0 & 1\\0 & 1 & 0\end{pmatrix}



$P(P_3,t)=t(t-1)^2$

问题是如何单从邻接矩阵计算出该图的色多项式。

Lwins_G

Calculating the chromatic polynomial of a graph is at least an NP-complete problem.

kastin

染色问题确实很迷人。
楼主的例子很简单，直接根据组合原理中的乘法公式就能得出那个多项式。
不过更复杂的图，就比较困难了，一般需要将图进行分解，主要有递推法和理想子图法。楼主给的链接中也说得很清楚了，常用的是用递推法求色多项式。

记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种色彩将顶点与边染色的方法数有多少？