主題
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 指數, 獨立邊集, 匹配, 匹配生成多項式, 匹配數, 完美匹配

使用 探索

參考文獻

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."

在 中被引用

匹配多項式

請按如下方式引用

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

主題分類