主题
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)

另请参阅

循环指标, 图环, 哈密顿环, 路径多项式

使用 Wolfram|Alpha 探索

请引用为

Weisstein, Eric W. "环多项式." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CyclePolynomial.html

主题分类