主題
Search

流多項式

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

設 C^*(u) 表示連通圖 連通圖 G 上無處為零的 u-流的數量，其中圖 G 的頂點數 n，邊數 m，以及連通分量數 c。 這個量被稱為圖 G 的流多項式，由下式給出

C^*(u)=(-1)^mR(-1,-u)
(1)
=(-1)^(m-n+c)T(0,1-u),
(2)

其中 R(x,y) 是秩多項式，T(x,y) 是 Tutte 多項式 (擴充套件自 Biggs 1993, p. 110)。

圖 g 的流多項式可以在 Wolfram 語言 中使用以下命令計算FlowPolynomial[g, u].

平面圖 G 的流多項式 C_G^*(u) 與其對偶圖 G^* 的色多項式相關，關係如下

C_G^*(u)=u^(-1)pi_(G^*)(u).
(3)

橋圖的流多項式為 0，因此，節點數 >=2 的樹的流多項式也為 0。

下表總結了一些特殊圖類的流多項式。

圖流多項式
書圖 S_(n+1) square P_2((u-1)[(-1)^(n+1)+(u-1)^n])/u
圈圖 C_nu-1
梯子圖 P_2 square P_n(u-1)(u-2)^(n-1)
稜柱圖 Y_n(-1)^n-(u-2)^n+(u-3)^n+[(-1)^n(u-3)+(u-3)^n]u
網圖0
輪圖 W_n(-1)^(n+1)(u-2)+(u-2)^(n-1)

下表總結了一些特殊圖類的線性遞推關係。

圖階數遞推關係
反稜柱圖4
書圖 S_(n+1) square P_22p_n(u)=(u-2)p_(n-1)(u)+(u-1)p_(n-2)(u)
梯子圖 P_2 square P_n1p_n(u)=(u-2)p_(n-1)(u)
稜柱圖 Y_n3p_n(u)=2(u-3)p_(n-1)(u)+(-u^2+7u-11)p_(n-2)(u)-(u-3)(u-2)p_(n-3)(u)
輪圖 W_n2p_n(u)=(u-3)p_(n-1)(u)+(u-2)p_(n-2)(u)

另請參閱

色多項式, 秩多項式, Tutte 多項式

使用 探索

參考文獻

Biggs, N. L. Algebraic Graph Theory, 2nd 版. Cambridge, England: Cambridge University Press, 頁 110-111, 1993.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 2008 年 6 月 28 日. http://arxiv.org/abs/0803.3079.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 頁 370, 2001.

在 中被引用

流多項式

請按如下方式引用

Weisstein, Eric W. "Flow Polynomial." 來自 —— 資源。 https://mathworld.tw/FlowPolynomial.html

學科分類