主题
Search

色不变量

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

连通图 G 的色不变量 theta(G) 是 G 的生成树的数量，这些生成树具有内部活动性 1 和外部活动性 0。

对于非单例图的图（对于单例图，theta(K_1)=1），它也由下式给出

theta(G)=(-1)^n(dpi_G)/(dx)|_(x=1),

其中 n=V(G)=|G| 是 顶点计数，pi_G(x) 是 G 的色多项式。

连通图 G 是可分的 当且仅当 theta(G)=0，并且是串并联图 当且仅当 theta(G)<=1 (Biggs 1993, p. 109)。

除非另有说明，否则在计算诸如有机化学家在将苯环写成六边形时通常会忽略氢原子（Devillers and Balaban 1999, p. 25）。

下表总结了特殊情况（Biggs 1993, p. 110）。

图OEIStheta(G_1), theta(G_2), ...
Andrásfai 图A2803331, 1, 12, 815, 157762, ...
反棱柱图A294152X, X, 11, 38, 112, 309, 828, 2190, 5759, ...
阿波罗网络A0000002, 16, 8192, ...
n×n 黑主教图A2951701, 1, 0, 8, 3528, 18475776, ...
鸡尾酒会图 K_(n×2)A2951662, 1, 11, 362, 21234, 1965624, 264398280, ...
完全二分图 K_(n,n)A0481441, 1, 5, 73, 2069, 95401, 6487445, 610093513, ...
完全三分图 K_(n,n,n)A1825531, 11, 1243, 490043, 463370491, ...
完全图 K_nA0001421, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, ...
2n-交叉棱柱图A295168X, 11, 85, 521, 2869, 15017, 76717, 387425, ...
皇冠图A2951711, 11, 328, 16369, 1181276, ...
立方体连接环图A000000X, X, 2816, ...
空图 K^__nA0000001, 2, -3, 4, -5, 6, -7, 8, -9, 10, ...
斐波那契立方体图A2959271, 0, 0, 1, 36, 58432, ...
折叠立方体图A295172X, 1, 2, 73, 1872172, ...
齿轮图A000027X, X, 2, 3, 4, 5, 6, 7, 8, 9 ...
网格图 P_n square P_nA1825171, 1, 3, 72, ...
网格图 P_n square P_n square P_nA2951731, 11, 156284551, ...
半立方体图A295174X, 1, 1, 2, 362, 1784062800, ...
河内图A2951751, 64, 1073741824, ...
超立方体图 Q_nA2951761, 1, 11, 48253, ...
Keller 图A0000004, 1872172, ...
n×n 国王图A2951771, 2, 48, 31328, 473555616, ...
n×n 骑士图A2951781, 4, -1, 78, 1306725, ...
莫比乌斯阶梯图 M_nA000325X, X, 5, 12, 27, 58, 121, 248, 503, 1014, ...
Mycielski 图 M_nA0000001, 1, 1, 238, ...
奇图 O_nA0000001, 1, 36, ...
置换星图 PS_nA0000001, 1, 1, 87837, ...
棱柱图 Y_nA000295X, X, 4, 11, 26, 57, 120, 247, 502, 1013, ...
n×n 皇后图A2951871, 2, 1308, 1238775828, ...
车补图 K_n square K_n^_A2951861, 0, 98, 787211620, ...
车图 K_n square K_nA295184X, 1, 98, ...
谢尔宾斯基地毯图A2951891, 1, 27, 20346417, ...
谢尔宾斯基四面体图A0000002, 176, ...
太阳图A000142X, X, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, ...
环面网格图 C_n square C_nA295191X, X, 98, 48253, 121790284, ...
转置图A0000001, 1, 5, ...
三角形图A295192X, 1, 1, 11, 3444, 32396796, ...
三角形网格图A2951901, 1, 1, 5, 97, 6739, 1611097, 1295101469, ...
三角形蜂窝钝角骑士图A2951941, -3, 6, 0, 0, 11687, 100231463, ...
三角形蜂窝皇后图A2951951, 1, 11, 3714, 39103200, ...
轮图 W_nA000027X, X, X, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
n×n 白主教图A2952171, 1, 8, 2044, 18475776, ...

封闭形式总结在下表中，其中 L_n 是 卢卡斯数，S(n,k) 是第二类斯特林数，Gamma(z) 是 伽玛函数。

图色不变量公式
反棱柱图L_(2n)-2n-1
完全二分图 K_(n,n)sum_(k=0)^(n-1)(k!)^2[S(n-1,k)]^2
完全图 K_n{1 for n=1; (n-2)! otherwise
完全三分图 K_(n,n,n)sum_(k=1)^(n)sum_(l=1)^(n)(-1)^(k+l+n)(1-k-l)^nGamma(k+l-1)S(n,k)S(n,l)
2n-交叉棱柱图5^n-2^(n+1)(3n+1)
环图 C_n,1
空图 K^__n{1 for n=1; (-1)^nn otherwise
齿轮图2^n-n
舵轮图0
梯形图 P_2 square P_n1
梯子阶图 nP_2{1 for n=1; 0 otherwise
莫比乌斯阶梯图 M_nn-1
扇图0
路径图 P_n{0 for n=1, 2; 1 otherwise
棱柱图 Y_n2^n-n-1
星图 S_n{1 for n=1, 2; 0 otherwise
太阳图(n-2)!
日珥图C_n circledot K_10
网状图0
轮图 W_nn-2

参见

色数, 色多项式

使用 Wolfram|Alpha 探索

参考文献

Biggs, N. L. 代数图论，第二版 Cambridge, England: Cambridge University Press, pp. 107-109, 1993.Devillers, J. 和 Balaban, A. T. (编辑). QSAR 和 QSPR 中的拓扑指标和相关描述符。 Amsterdam, Netherlands: Gordon and Breach, 1999.Sloane, N. J. A. 序列 A000027/M0472, A000142/M1675, A000295/M3416, A000325, 和 A048144，出自“整数序列在线百科全书”。

在 Wolfram|Alpha 上引用

色不变量

请引用为

Weisstein, Eric W. “色不变量。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ChromaticInvariant.html

学科分类