主題
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 多項式

在 中探索

參考文獻

Biggs, N. L. 代數圖論，第二版。 英國劍橋：劍橋大學出版社，pp. 73, 97, 和 101, 1993.Godsil, C. 和 Royle, G. "秩多項式" 和 "秩多項式的評估"。§15.9-15.10 在 代數圖論。 紐約：施普林格出版社，pp. 355-358, 2001.

在 上被引用

秩多項式

請引用為

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

學科分類