主题
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.net.cn/FlowPolynomial.html

学科分类