主题
Search

匹配多项式

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

图 G 中的 k-匹配 是一个包含 k 条边的集合，其中任意两条边都没有公共顶点（即，大小为 k 的 独立边集）。设 Phi_k 为图 G 中 k-匹配 的数量，其中 Phi_0(G)=1 且 Phi_1(G)=m 为图 G 的边数。那么，匹配多项式定义为

mu(x)=sum_(k=0)^(nu(G))(-1)^kPhi_kx^(n-2k),
(1)

其中 n=|G| 是图 G 的 顶点数 (Ivanciuc 和 Balaban 2000, p. 92; Levit 和 Mandrescu 2005)，nu(G) 是匹配数（满足 nu(G)<=|_n/2_|，其中 |_x_| 是向下取整函数）。

匹配多项式也称为无环多项式 (Gutman 和 Trinajstić 1976, Devillers 和 Merino 2000)、匹配缺陷多项式 (Lovász 和 Plummer 1986) 以及参考多项式 (Aihara 1976)。

一个更自然的多项式可能是匹配生成多项式，它直接编码了图 G 的独立边集数量，并定义为

M(x)=sum_(k=0)^(nu(G))Phi_kx^k,
(2)

但 mu(x) 已经牢固确立。幸运的是，两者通过以下公式相关：

mu(x)=x^nM(-x^(-2))
(3)

(Ellis-Monaghan 和 Merino 2008；笔误已更正)，因此

M(x)=(-i)^nx^(n/2)mu(ix^(-1/2)).
(4)

匹配多项式与独立多项式密切相关。特别是，图 G 的匹配生成多项式等于 G 的线图的独立多项式 (Levit 和 Mandrescu 2005)。

匹配多项式具有非零的 a_0 系数（或者等价地，对于一个具有 n 个节点的图，匹配生成多项式的次数为 n）当且仅当该图具有完美匹配。

可以使用以下方法获得许多命名图的预计算匹配多项式，以变量 x 表示：GraphData[graph,"MatchingPolynomial"][x].

下表总结了一些常见图类的匹配多项式的闭合形式。其中，He_n(x) 是修正的 埃尔米特多项式，H_n(x) 是通常的 埃尔米特多项式，L_n(x) 是拉盖尔多项式，U(a,b,z) 是第二类合流超几何函数，L^^_n(x) 是卢卡斯多项式，s=sqrt(1-6x^2+x^4)，t=sqrt(x^2-4)，以及 u=sqrt(1-6x^2+x^4)。

图mu(x)
书图 S_(n+1) square P_2(x-1)^(n-2)(x+1)^(n-2)[n^2x^2+(x^2-1)^3+n(-1+2x^2-2x^4)
蜈蚣图((-1+v+x^2)^(n+1)-(-1-v+x^2)^(n+1))/(2^(n+1)v)
完全图 K_nHe_n(x)
=2^(-n/2)H_n(x/(sqrt(2)))
完全二分图 K_(n,n)(-1)^nn!L_n(x^2)
=U(-n,1,x^2)
圈图 C_ni^nL^^_n(-ix)
空图 K^__nx^n
齿轮图((n+tx)(-2-tx+x^2)^n+(-n+tx)(-2+tx+x^2)^n)/(2^nt)
舵轮图((n+s)x(-1-s+x^2)^n-(n-s)x(-1+s+x^2)^n)/(2^ns)
梯子横档图 nP_2(x-1)^n(x+1)^n
平底锅图((x+t)^n(tx-1)+(x-t)^n(tx+1))/(2^nt)
路径图 P_n((x-t)^(n+1)-(x+t)^(n+1))/(2^(n+1)t)
星图 S_nx^(n-2)(x^2-n+1)
日瓣图 C_n circledot K_12^(-n)((-1+x^2-sqrt(1-6x^2+x^4))^n+(-1+x^2+sqrt(1-6x^2+x^4))^n)
轮图 W_n(x(n+x^2-5)[(x-t)^n-(t+x)^n]+t(n+x^2-1)[(x-t)^n+(t+x)^n])/(2^(n+1)t)

下表总结了一些简单图类的独立多项式的递推关系。

反棱柱图4p_n(x)=(x-2)^2p_(n-1)(x)-(2x^2-1)p_(n-2)(x)+(x^2+2)p_(n-3)(x)-p_(n-4)(x)
书图 S_(n+1) square P_23p_n(x)=3p_(n-1)(x)-3p_(n-2)(x)+p_(n-3)(x)
蜈蚣图2p_n(x)=(x-1)(x+1)p_(n-1)(x)-x^2p_(n-2)(x)
(2n)-交叉棱柱图3p_n(x)=-2(x^2-2)^2p_(n-2)(x)+(x-1)(x+1)(x^2-5)p_(n-1)(x)+4p_(n-3)(x)
圈图 C_n2p_n(x)=xp_(n-1)(x)-p_(n-2)(x)
齿轮图4p_n(x)=2(x^2-2)p_(n-1)(x)-(x^4-4x^2+6)p_(n-2)(x)+2(x^2-2)p_(n-3)(x)-p_(n-4)(x)
舵轮图4p_n(x)=2(x-1)(x+1)p_(n-1)(x)-(x^4+1)p_(n-2)(x)+2(x-1)(x+1)x^2p_(n-3)(x)-x^4p_(n-4)(x)
梯子图 P_2 square P_n3p_n(x)=(-2+x^2)p_(n-1)(x)-x^2p_(n-2)(x)+p_(n-3)(x)
梯子横档图 nP_21p_n(x)=(x-1)(x+1)p_(n-1)(x)
莫比乌斯梯子 M_n4p_n(x)=(x^2-1)p_(n-1)(x)+2(1-x^2)p_(n-2)(x)+(x^2+1)p_(n-3)(x)-p_(n-4)(x)
平底锅图2p_n(x)=xp_(n-1)(x)-p_(n-2)(x)
路径图 P_n2p_n(x)=xp_(n-1)(x)-p_(n-2)(x)
棱柱图4p_n(x)=(x^2-1)p_(n-1)(x)+2(1-x^2)p_(n-2)(x)+(x^2+1)p_(n-3)(x)-p_(n-4)(x)
星图 S_n2p_n(x)=2xp_(n-1)(x)-x^2p_(n-2)(x)
日瓣图 C_n circledot K_12p_n(x)=(x+1)(x-1)p_(n-1)(x)-x^2p_(n-2)(x)
网图4p_n(x)=x^5p_(n-3)(x)-x^4p_(n-4)(x)+(x^2-2)xp_(n-1)(x)-(2x^4-4x^2+1)p_(n-2)(x)
轮图 W_n4p_n(x)=2xp_(n-1)(x)-(x^2+2)p_(n-2)(x)+2xp_(n-3)(x)-p_(n-4)(x)

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

n匹配多项式图
4x^2(-3+x^2)爪图, (4,6)
5(-2+x)(-1+x)x(1+x)(2+x)旗帜图, 3-蜈蚣图
5(-1+x)x(1+x)(-6+x^2)(3,2)-扇图, (4,1)-棒棒糖图
5(-1+x)x(1+x)(-5+x^2)蝴蝶图, 鸢尾图
5x^3(-3+x^2)(5,4), (5,8)
5(-1+x)x(1+x)(-3+x^2)(5,20), 路径图 P_5
5x(6-6x^2+x^4)房子图, 完全二分图 K_(2,3)
5x(2-5x^2+x^4)板球图, (5,15)
5x(2-4x^2+x^4)叉图, (5,14)

对于任何图 G，匹配多项式 mu(x) 只有实零点。

另请参阅

特征多项式, Hosoya 指数, 独立边集, 匹配, 匹配生成多项式, 匹配数, 完美匹配

使用 Wolfram|Alpha 探索

参考文献

Aihara, J. "A New Definition of Dewar-Type Resonance Energies." J. Amer. Chem. Soc. 98, 2750-2758, 1976.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 92-94, 2000.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. http://arxiv.org/abs/0806.4699.Godsil, C. D. Algebraic Combinatorics. Chapman and Hall, 1993.Godsil, C. D. and Gutman, I. "On the Theory of the Matching Polynomial." J. Graph Theory 5, 137-144, 2006.Gutman, I. "Polynomials in Graph Theory." In Chemical Graph Theory: Introduction and Fundamentals (Ed. D. Bonchev and D. H. Rouvray). New York: Abacus Press, 1991.Gutman, I. and Trinajstić, N. "Graph Theory and Molecular Orbitals, XIV. On Topological Definition of Resonance Energy." Acta Chimica Academiae Scientiarum Hungaricae 91, 203-209, 1976.Ivanciuc, O. and Balaban, A. T. "The Graph Description of Chemical Structures." Ch. 3 in Topological Indices and Related Descriptors in QSAR and QSPR (Ed. J. Devillers and A. T. Balaban). Amsterdam, Netherlands: Gordon and Breach, pp. 59-167, 2000.Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 (Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.Lovász, L. and Plummer, M. D. Matching Theory. Amsterdam, Netherlands: North-Holland, 1986.Lundow, P. H. "Enumeration of Matchings in Polygraphs." Department of Mathematics, Umea University. Research report. 1998. http://www.theophys.kth.se/~phl/Text/1factors2.ps.gz. Lundow, P. H. "GrafPack." http://www.theophys.kth.se/~phl/Mathematica/.Sloane, N. J. A. Sequences A046741 and A096713 in "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 中被引用

匹配多项式

请按如下方式引用

Weisstein, Eric W. "Matching Polynomial." 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/MatchingPolynomial.html

主题分类