主題
Search

環多項式

下載 Mathematica 筆記本下載 Wolfram 筆記本

人們可能會認為，與匹配生成多項式、獨立多項式等類似，應該定義一個環多項式，其係數是長度為 k 的環的數量。雖然在文獻中似乎沒有定義過這樣的多項式（相反，“環多項式”通常指的是對應於迴圈指標的置換群的多項式），但它們在這項工作中被定義。

因此，環多項式，或許是首次在此處定義，是多項式

C_G(x)=sum_(k=3)^nc_kx^k

其係數 c_k 給出了圖 G 中存在的簡單環的數量，圖 G 有 n 個節點。

由於最小可能的環的長度為 3，環多項式的多項式次數至少為 3。多項式次數 C_G(x) 是 G 的圍長，並且圖是哈密頓圖 當且僅當 次數等於 n。

特別地，c_n 給出了哈密頓環的數量，因此圖是哈密頓圖 當且僅當 c_n!=0。圖是無三角形圖 當且僅當 c_3=0，並且是無方圖 當且僅當 c_4=0。

由於非連通圖中的環計數是其連通分量中環計數的總和，因此環多項式在連通分量上是可加的。

下表總結了一些常見圖類的環多項式的閉合形式。

圖C(x)
書圖 S_(n+1) square P_21/2nx^4[(n-1)x^2+2]
完全二部圖 K_(n,n)1/2sum_(k=2)^(n)(n; k)^2k!(k-1)!x^(2k)
完全圖 K_n1/2sum_(k=3)^(n)(n; k)(k-1)!x^k
圈圖 C_nx^n
齒輪圖(n(x^(2(n+1))-x^4))/(x^2-1)
頭盔圖x^n+(n(x^n-x)x^2)/(x-1)
梯形圖 P_2 square P_nsum_(k=1)^(n)(n-k)x^(2k+2)
=(x^4[x^(2n)+n(x^2-1)-1])/((x^2-1)^2)
莫比烏斯梯形圖 M_nx^(2n)-[x(x+1)]^n-[x(x-1)]^n+(n(x^(2(n+1))-x^4))/(x^2-1)
稜柱圖 Y_n(nx^4(x^(2n-2)-1)+(x^2-1)x^n[(1-x)^n+(1+x)^n])/(x^2-1)
日曬圖 C_n circledot K_1x^n
網圖[x(x+1)]^n-[x(x-1)]^n+(n(x^(2(n+1))-x^4))/(x^2-1)
輪圖 W_nx^(n-1)+(n-1)sum_(k=3)^(n)x^k
=x^(n-1)+((n-1)x(x^2-x^n))/(x-1)

下表總結了一些簡單圖類的環多項式的遞推關係。

圖階數遞推關係
反稜柱圖7p_n(x)=x^(10)p_(n-7)(x)+(3x^2+2x+2)p_(n-1)(x)-(2x^4+1)x^6p_(n-6)(x)+(x^6+2x+2)x^4p_(n-5)(x)+(3x^4-4x^3-5x^2-4x-1)x^2p_(n-4)(x)-(x^4+4x^3+7x^2+4x+1)p_(n-2)(x)-(2x^5-2x^4-4x^3-8x^2-5x-2)xp_(n-3)(x)
書圖 S_(n+1) square P_23p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
齒輪圖4p_n(x)=x^4(-p_(n-4)(x))+2(x^2+1)x^2p_(n-3)(x)+2(x^2+1)p_(n-1)(x)-(x^4+4x^2+1)p_(n-2)(x)
頭盔圖4p_n(x)=x^2(-p_(n-4)(x))-(x^2+4x+1)p_(n-2)(x)+2(x+1)xp_(n-3)(x)+2(x+1)p_(n-1)(x)
梯形圖 P_2 square P_n3p_n(x)=x^2p_(n-3)(x)-(2x^2+1)p_(n-2)(x)+(x^2+2)p_(n-1)(x)
莫比烏斯梯形圖 M_n6p_n(x)=(x-1)(x+1)x^6p_(n-6)(x)-2(x^4-x-1)x^4p_(n-5)(x)+2(x^2+x+1)p_(n-1)(x)-(4x^3+5x^2+4x+1)p_(n-2)(x)+(x^6+3x^4-4x^3-4x^2-4x-1)x^2p_(n-4)(x)-2(x^5-x^4-x^3-4x^2-2x-1)xp_(n-3)(x)
日曬圖 C_n circledot K_11p_n(x)=xp_(n-1)(x)
網圖6p_n(x)=(x-1)(x+1)x^6p_(n-6)(x)-2(x^4-x-1)x^4p_(n-5)(x)+2(x^2+x+1)p_(n-1)(x)-(4x^3+5x^2+4x+1)p_(n-2)(x)+(x^6+3x^4-4x^3-4x^2-4x-1)x^2p_(n-4)(x)-2(x^5-x^4-x^3-4x^2-2x-1)xp_(n-3)(x)

下表總結了一些圖族的前幾個環多項式。

圖 G_nOEISnC_(G_n)(x)
反稜柱圖38x^3+15x^4+24x^5+16x^6
48x^3+10x^4+24x^5+52x^6+56x^7+29x^8
510x^3+10x^4+12x^5+35x^6+100x^7+160x^8+140x^9+56x^(10)
612x^3+12x^4+12x^5+14x^6+48x^7+177x^8+388x^9+498x^(10)+...
雞尾酒會圖 K_(n×2)A1679862x^4
38x^3+15x^4+24x^5+16x^6
432x^3+102x^4+288x^5+640x^6+960x^7+744x^8
完全圖 K_n3x^3
44x^3+3x^4
510x^3+15x^4+12x^5
620x^3+45x^4+72x^5+60x^6
735x^3+105x^4+252x^5+420x^6+360x^7
皇冠圖3x^6
46x^4+16x^6+6x^8
530x^4+130x^6+270x^8+156x^(10)
690x^4+680x^6+3330x^8+7776x^(10)+4800x^(12)
圈圖 C_n3x^3
4x^4
5x^5
6x^6
網格圖 P_n square P_n2x^4
34x^4+4x^6+5x^8
49x^4+12x^6+26x^8+52x^(10)+76x^(12)+32x^(14)+6x^(16)
516x^4+24x^6+61x^8+164x^(10)+446x^(12)+1100x^(14)+2102x^(16)+2436x^(18)+1874x^(20)+900x^(22)+226x^(24)
超立方體圖 Q_nA0854522x^4
36x^4+16x^6+6x^8
424x^4+128x^6+696x^8+2112x^(10)+5024x^(12)+5376x^(14)+1344x^(16)
580x^4+640x^6+6720x^8+68736x^(10)+591200x^(12)+4652160x^(14)+...
(n,n)-國王圖24x^3+3x^4
316x^3+29x^4+52x^5+82x^6+92x^7+61x^8+16x^9
436x^3+79x^4+176x^5+430x^6+1096x^7+2727x^8+6184x^9+12224x^(10)+20404x^(11)+27555x^(12)+...
(n,n)-騎士圖2x^8
34x^4+20x^6+32x^8+68x^(10)+82x^(12)+16x^(14)
422x^4+164x^6+892x^8+3864x^(10)+13042x^(12)+27836x^(14)+37193x^(16)+30144x^(18)+13108x^(20)+2384x^(22)+120x^(24)
梯形圖 P_2 square P_n2x^4
32x^4+x^6
43x^4+2x^6+x^8
54x^4+3x^6+2x^8+x^(10)
65x^4+4x^6+3x^8+2x^(10)+x^(12)
稜柱圖 Y_n32x^3+3x^4+6x^5+3x^6
46x^4+16x^6+6x^8
55x^4+2x^5+5x^6+20x^7+5x^8+10x^9+5x^(10)
66x^4+8x^6+36x^8+36x^10+8x^(12)
77x^4+7x^6+2x^7+7x^8+42x^9+7x^(10)+70x^(11)+7x^(12)+14x^(13)+7x^(14)
(n,n)-皇后圖24x^3+3x^4
336x^3+122x^4+376x^5+976x^6+1984x^7+2761x^8+1960x^9
4124x^3+776x^4+4644x^5+26414x^6+141216x^7+696906x^8+3118200x^9+12423308x^(10)+43071536x^(11)+126154214x^(12)+299319152x^(13)+539006624x^(14)+654614112x^(15)+402364270x^(16)
(n,n)-車圖2x^4
36x^3+9x^4+36x^5+60x^6+72x^7+81x^8+48x^9
432x^3+60x^4+288x^5+1248x^6+4032x^7+11952x^8+34368x^9+91296x^(10)+211968x^(11)+417264x^(12)+670464x^(13)+822528x^(14)+678912x^(15)+284112x^(16)

另請參閱

迴圈指標, 圖環, 哈密頓環, 路徑多項式

使用 探索

請引用為

Weisstein, Eric W. "環多項式." 來自 Web 資源。 https://mathworld.tw/CyclePolynomial.html

主題分類