4類圖完美匹配數目的顯式表達式

唐保祥，任韓

1.天水師范學院數學與統計學院，甘肅天水 741001

2.華東師范大學數學系，上海 200062

4類圖完美匹配數目的顯式表達式

唐保祥1，任韓2

1.天水師范學院數學與統計學院，甘肅天水 741001

2.華東師范大學數學系，上海 200062

1 引言

匹配計數理論是圖論研究的重要內容之一，在過去的幾十年中，它是快速發展的組合論中許多重要思想的源泉，其研究成果已經在多個領域得到應用[1-5]。此問題引起一些學者的廣泛研究，也得到了許多特殊圖類完美匹配的計數公式[6-13]。遺憾的是，Valiant證明了一個圖（即使是偶圖）的完美匹配計數是NP-難問題[5]。因此，不存在計算圖的完美匹配圖數目的一般方法，要得到一個圖的完美匹配的數目是很困難的。文獻[14-18]用劃分、求和、再遞推的方法給出了一些圖類完美匹配的計數公式。本文在此基礎上，使用了嵌套遞推的方法給出了4類新圖的完美匹配數目的計算公式，本文方法適合相同結構重復出現的，結構比較復雜的圖類完美匹配數的求解。

定義1若圖G的兩個完美匹配M1和M2中有一條邊不同，則稱M1和M2是G的兩個不同的完美匹配。

定義2兩條長為n的路為P1=u1u2…un+1，P1=ν1ν2…νn+1，分別連接路P1與P2的頂點ui與νi(i=1,2,…,n+1)所得到的圖，稱為長為n的梯子，記為Tn。

2 結果及其證明

圖12 -nDC4圖

圖2 G1圖

圖32 -nW6圖

圖42 -2nDC4圖

圖52 -nT4圖

證明為了求σ(n)，先定義2個圖G2和G3，并求其完美匹配的數目。將長為1的路u1u2的端點u1和u2分別與圖2-nT4的頂點u12和u13，u13和u14各連接一條邊，得到的圖分別記為G2和G3，如圖6和7所示。易知圖G2和G3均有完美匹配；β(n)和γ(n)分別表示圖G2和G3的完美匹配的數目，顯然G2?G3，所以β(n)=γ(n)。

圖6 G2圖

圖7 G3圖

3 結論

圖的完美匹配計數是圖論和組合數學中的一個重要課題，有著廣泛的應用前景。Lovász L和lummer M曾提出完美匹配計數的一個猜想：任何2-邊連通3-正則圖都有指數多個完美匹配。本文結論驗證了Lovász L和Plummer M猜想在這4類圖上的正確性。本文方法是求解許多特殊圖類完美匹配數目的有效方法，用此方法還可以求出一些圖的所有Hamilton圈的數目[14]。

[1]Pauling L.The nature of chemical bond[M].New York：Cornell University Press，1939.

[2]Kasteleyn P W.Graph theory and crystal physics[M]//Harary F.Graph Theory and Theoretical Physics.London：Academic Press，1967：43-110.

[3]Hall G G.A graphic model of a class of molecules[J].Int J Math Edu Sci Technol，1973，4（3）：233-240.

[4]Swinborne-Sheldrake R，Herndon W C，Gutman T.Kekule structures and resonance energies of benzennoid hydrocarbons[M]// Tetrahedron Lett.Oxford：Pergamon-Elsevier Science Ltd，1975：755-758.

[5]Valiant L G.The complexity of computing the permanent[J]. Theoretical Compute Science，1979，8（2）：189-201.

[6]Lovász L，Plummer M.Matching theory[M].New York：North-Holland Press，1986.

[7]張福基，陳榮斯.六角系統克庫勒結構的計數[J].新疆大學學報：自然科學版，1986，3（3）：10-14.

[8]張福基，陳治柏.廣義渺位苯圖的完美匹配數的計算[J].新疆大學學報：自然科學版，1986，3（3）：6-10.

[9]Zhang Heping.The connectivity of Z-transformation graphs of perfect matchings of polyominoes[J].Discrete Mathematics，1996，158：257-272.

[10]Zhang Heping，Zhang Fuji.Perfect matchings of polyomino graphs[J].Graphs and Combinatorics，1997，13：259-304.

[11]Yan Weigen，Zhang Fuji.Enumeration of perfect matchings of a type of Cartesian products of graphs[J].Discrete Applied Mathematics，2006，154：145-157.

[12]王洪偉.二部圖匹配強迫數的譜[J].山東大學學報：理學版，2009，44（12）：30-35.

[13]江蓉，王守中，任海珍.兩類2-共振的六角系統的刻畫[J].河北大學學報：自然科學版，2009，29（4）：342-350.

[14]唐保祥，任韓.幾類圖完美匹配的數目[J].南京師大學報：自然科學版，2010，33（3）：1-6.

[15]唐保祥，李剛，任韓.3類圖完美匹配的數目[J].浙江大學學報：理學版，2011，38（4）：16-19.

[16]唐保祥，任韓.2類圖完美匹配的數目[J].西南師范大學學報，自然科學版，2011，36（5）：16-21.

[17]唐保祥，任韓.3類圖完美匹配的計數[J].南京師大學報：自然科學版，2012，35（1）：16-21.

[18]唐保祥，任韓.6類圖完美匹配的數目[J].中山大學學報：自然科學版，2012，51（2）：40-44.

TANG Baoxiang1,REN Han2

1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui,Gansu 741001,China
2.Department of Mathematics,East China Normal University,Shanghai 200062,China

Matching counting theory is at the core of graph theory,since it is origins from both physics,computer science and chemistry.But the problem of counting the number of perfect matching for general graphs is NP-hard.By applying differentiation,summation and re-nested recursive calculation,several counting formulas of the perfect matching for four specific types of graphs are given.By the presented method,the number of all perfect matching of many graphs that the same structure is repeated can be calculated.

perfect matching;linear recurrence relation;characteristic equation

匹配計數理論是圖論的核心內容之一，此問題有很強的物理學、計算機科學和化學背景；但是，一般圖的完美匹配計數問題卻是NP-難問題。用劃分、求和、再嵌套遞推的方法給出了4類圖完美匹配數目的顯式表達式；所給出的方法，可以計算出相同結構重復出現的許多圖的所有完美匹配的數目。

完美匹配；線性遞推式；特征方程

A

O157.5

10.3778/j.issn.1002-8331.1206-0203

TANG Baoxiang,REN Han.Explicit formulae for number of perfect matching in four types of graphs.Computer Engineering and Applications,2013,49（19）：44-48.

國家自然科學基金（No.11171114）。

唐保祥（1961—），男，副教授，研究方向：圖論和組合數學。E-mail：tbx0618@sina.com

2012-06-12

2012-08-10

1002-8331（2013）19-0044-05

CNKI出版日期：2012-09-25http://www.cnki.net/kcms/detail/11.2127.TP.20120925.1000.028.html