Chromatic Polynomial
染色
考查无向图G = (V, E)。所谓G的一个k-染色（coloring），是从V到[1, k]的一个映射：
π: V ® {1, 2, ..., k}
而且满足
" v, u Î V, π(v) ≠ π(u) if (v, u) ∈ E
简而言之，就是将所有顶点归入不超过k个等价类，且保证相邻顶点不属同类。
色多项式
若将图G和k视作变量，则可用函数CP(G, k)表示图G的k-染色（方案）数。
而对任一图G，该函数都是k的多项式形式，称作色多项式（chromatic polynomial）。
以下即为若干典型实例。
1）对于包含n个顶点、不含任何边的图Sn，有
CP(Sn, k) = kn
2）对于完全图Kn，有
CP(Kn, k) = 0, if k < n
CP(Kn, k) = k! / (k-n)!, if k ³ n
3）对于二部图（bipartition）B(2, 3)，有
CP(B(2, 3), 1) = 0
CP(B(2, 3), 2) = 2
CP(B(2, 3), 3) = 30
CP(B(2, 3), k) = k5 - 6*k4 + 15*k3 - 17*k2 + 7*k
4）对于5阶环C5，有
CP(C5, 1) = P(2, C5) = 0；
CP(C5, 3) = 30
CP(C5, k) = k5 - 5*k4 + 10*k3 - 10*k2 + 4*k
减除与收缩
考查任意边e = (u, v) Î E。
G在e处经减除（subtraction）操作所得的新图记作：G\{e} = (V, E\{e})。简而言之，也就是将边e从图G中“抹除”。
G在e处经收缩（contraction）操作所得的新图记作：G/{e} = (V', E')。其中
V' = (V\{v, u}) È {w}
E' = ( { (s, t) Î E | s, t Ï {v, u} }
È { (w, t) | (v, t} Î E }
È { (s, w) | (s, u} Î E }
)
\ { (v, u) }
简而言之，亦即收缩边e，直到v和u“粘连”为同一顶点w；而与之关联的边除e外依然保留。
递归
[引理] 对于图G中的任何一条边e，都有：CP(G, k) = CP(G\{e}, k) - CP(G/{e}, k)
算法框架
根据以上性质，不难导出色多项式算法的基本框架如下：
CPoly chrompoly(G) {
if (G is SIMPLE enough)
return (chormpolyTrivial(G));
else
return (chormpoly(G\{e}) - chormpoly(G/{e}));
}
任务
试编写一个程序，对于给定的图G, 计算并输出其对应的色多项式CP(G, k)。
输入
采用（下）三角邻接矩阵方式表示图G，格式为：
| n | |||||||
|
|
|
|
|
|
|
|
|
|
a1,0 |
|
|
|
|
|
|
|
|
a2,0 |
a2,1 |
|
|
|
|
|
|
|
a3,0 |
a3,1 |
a3,2 |
|
|
|
|
|
|
... |
... |
... |
... |
|
|
|
|
|
an-2,0 |
an-2,1 |
an-2,2 |
... |
an-2,n-3 |
|
|
|
|
an-1,0 |
an-1,1 |
an-1,2 |
... |
an-1,n-3 |
an-1,n-2 |
|
其中n = |V|为顶点总数，顶点从0到n-1编号；ai,j表示顶点i和j之间有无联边，有则为1，没有为0。
这里是一些输入图数据的实例。
你也可以使用一个工具，在指定结点与边的数目之后，随机生成一个图。例如：
% gg.exe 20 25 > random-20-25.grf
输出
计算出的多项式，具体形式参见random-20-25.out。
例子
% chrompoly.exe random-20-25.grf > random-20-25.out
评分
我们将随机生成若干张图（n<=40, e<=60），对你的程序进行测试。
具体评分标准如下：
0. 计算结果不对，或者速度不到基准程序的1/4，计0分；
1. 计算正确，且速度达到基准程序的1/4以上，获1/3的分；
2. 计算正确，且速度达到基准程序的1/2以上，获2/3的分；
3. 计算正确，且速度达到基准程序的2/3以上，获满分；
x. 速度最快的前五人，可获得适当的加分奖励。