主題
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

參見

色數, 色多項式

使用 探索

參考文獻

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，出自“整數序列線上百科全書”。

在 上引用

色不變數

請引用為

Weisstein, Eric W. “色不變數。” 來自 Web 資源。 https://mathworld.tw/ChromaticInvariant.html

學科分類