图的色多项式

本文主要是介绍图的色多项式，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

色多项式 \(P(G, t)\) 的值是在图 \(G\) 中顶点的不同的 \(t\) 着色数目，是关于 \(t\) 的多项式.

特殊图的色多项式

当 \(\mathrm{card}(V) = 1\) 时，\(P(G, t) = t\).

当 \(G\) 为一条链时，\(P(G, t) = t \cdot (t-1)^{\mathrm{card}(V(G))-1}\).

当 \(G\) 为完全图时，\(P(G, t) = A_t^{t-\mathrm{card}(V(G))}\).

给定图 \(G\) 与 \(e \in E(G)\)，则 \(P(G, t) = P(G - e, t) - P(G / e, t)\).

其中 \(G / e\) 表示合并 \(e\) 连接的两个顶点.

证明

设 \(e = (u, v)\)，考虑图 \(G - e\)：

即 \(P(G - e, t) = P(G, t) + P(G / e, t)\)，移项后即为上式，\(\mathrm{Q.E.D}\).

这篇关于图的色多项式的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！