主题
Search

秩多项式

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

一般图 G 的秩多项式 R(x,y) 定义为函数：

R(x,y)=sum_(S subset= E(G))x^(r(S))y^(s(S)),
(1)

其中，求和是对所有子图（即，边集）进行的，子图 S 的秩 r(S) 和余秩 s(S) 由下式给出：

r(S)=n-c
(2)
s(S)=m-n+c
(3)

对于具有 n 个顶点、m 条边和 c 个连通分量的子图（Biggs 1993, p. 73）。

秩多项式在图的连通分量上是可乘的，因此对于具有连通分量 G_1、G_2、... 的图 G，G 本身的秩多项式由下式给出：

R_G=R_(G_1)R_(G_2)....
(4)

它用 Tutte 多项式 T(x,y) 表示为：

R(x,y)=x^(n-c)T(x^(-1)+1,y+1).
(5)

具有 n 个顶点的一般图 G 的色多项式 pi(x) 和秩多项式通过下式相关：

pi(x)=x^nR(-x^(-1),-1)
(6)

（Biggs 1993, p. 75）。

显然，

R(x,x)=(x+1)^m,
(7)

其中 m 是图的边的数量（Biggs 1993, p. 74）。

下表总结了一些常见图类的秩多项式。

图秩多项式
香蕉树图(1+x)^(nk)
书图 S_(n+1) square P_2([1+3x(x+1)]^n(y-x)+x(y+1){1+x[3+x(3+y)]}^n)/y
蜈蚣图(x+1)^(2n-1)
圈图 C_nx^(n-1)(y-x)+(x+1)^n
齿轮图(x[x^2(y+4)+3x+1-s]^n+x[x^2(y+4)+3x+1+s]^n-2^(n+1)x^(2n+1)+2^nyx^(2n))/x
梯子横档图 nP_2(1+x)^n
平底锅图x^(n-1)(y-x)+(x+1)^(n+1)
路径图 P_n(1+x)^(n-1)
星图 S_n(1+x)^n
太阳花图 C_n circledot K_1(1+x)^n[(1+x)^n+x^(n-1)(y-x)]

下表总结了一些常见图类的秩多项式的递推方程。

图递推关系
书图 S_(n+1) square P_2p_n=(x^2y+6x^2+6x+2)p_(n-1)-(3x^2+3x+1)(x^2y+3x^2+3x+1)p_(n-2)
圈图 C_np_n=(2x+1)p_(n-1)-x(x+1)p_(n-2)
齿轮图p_n=(1+3x+5x^2+x^2y)p_(n-1)-x^2(2+5x+5x^2+y+2xy+2x^2y)p_(n-2)+(x^4(1+x)^2(1+y))p_(n-3)
舵轮图p_n=(x+1)(xy+4x+1)p_(n-1)-x(2x+1)(x+1)^2(y+2)p_(n-2)+x^2(x+1)^4(y+1)p_(n-3)
梯子图 L_np_n=(1+3x+4x^2+x^2y)p_(n-1)-x^2(x+1)^2(y+1)p_(n-2)
平底锅图p_n=(2x+1)p_(n-1)-x(x+1)p_(n-2)
太阳花图 C_n circledot K_1p_n=(x+1)(2x+1)p_(n-1)-x(x+1)^3p_(n-2)
轮图 W_np_n=(1+4x+xy)p_(n-1)-x(2x+1)(y+2)p_(n-2)+x^2(x+1)(y+1)p_(n-3)

非同构图不一定具有不同的秩多项式。下表总结了一些同秩图。

秩多项式图
1空图 K^__n
1+x(3,2), (4,2), (5,2), (6,2), (7,2), (8,2), 路径图 P_2
1+3x+3x^2+x^2y三角形图, (4,6), (5,8), (6,10), (7,12), (8,14)
(1+x)^2(4,3), (5,3), (5,6), (6,3), (7,3), (7,8), (8,3), (8,9), (2,6)-五跳棋图, (4,5)-五跳棋图, (2,3)-骑士图, 2-梯子横档图, 路径图 P_3
(1+x)^3爪状图, (5,4), (5,7), (5,9), (6,4), (6,8), (6,11), (7,4), (7,9), (7,13), (7,58), (8,4), (8,10), (8,15), (8,88), (3,6)-五跳棋图, 3-梯子横档图, 路径图 P_4
(1+x)(1+3x+3x^2+x^2y)爪子图, (5,10), (5,20), (6,12), (6,37), (7,14), (7,60), (8,16), (8,91)
1+4x+6x^2+4x^3+x^3y方格图, C_4, (5,14), (6,22), (7,30), (8,38)
1+5x+10x^2+8x^3+2x^2y+5x^3y+x^3y^2菱形图, (5,15), (6,23), (7,31), (8,39)
1+6x+15x^2+16x^3+4x^2y+15x^3y+6x^3y^2+x^3y^3四面体图, (5,24), (6,58), (7,114), (8,199)

参见

色多项式, 流多项式, 秩矩阵, 可靠性多项式, Tutte 多项式

在 Wolfram|Alpha 中探索

参考文献

Biggs, N. L. 代数图论，第二版。 英国剑桥：剑桥大学出版社，pp. 73, 97, 和 101, 1993.Godsil, C. 和 Royle, G. "秩多项式" 和 "秩多项式的评估"。§15.9-15.10 在 代数图论。 纽约：施普林格出版社，pp. 355-358, 2001.

在 Wolfram|Alpha 上被引用

秩多项式

请引用为

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

学科分类