4類圖完美匹配數(shù)目的顯式表達(dá)式

唐保祥，任韓

1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅天水 741001

2.華東師范大學(xué)數(shù)學(xué)系，上海 200062

4類圖完美匹配數(shù)目的顯式表達(dá)式

唐保祥1，任韓2

1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅天水 741001

2.華東師范大學(xué)數(shù)學(xué)系，上海 200062

1 引言

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

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

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

2 結(jié)果及其證明

圖12 -nDC4圖

圖2 G1圖

圖32 -nW6圖

圖42 -2nDC4圖

圖52 -nT4圖

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

圖6 G2圖

圖7 G3圖

3 結(jié)論

圖的完美匹配計(jì)數(shù)是圖論和組合數(shù)學(xué)中的一個(gè)重要課題，有著廣泛的應(yīng)用前景。Lovász L和lummer M曾提出完美匹配計(jì)數(shù)的一個(gè)猜想：任何2-邊連通3-正則圖都有指數(shù)多個(gè)完美匹配。本文結(jié)論驗(yàn)證了Lovász L和Plummer M猜想在這4類圖上的正確性。本文方法是求解許多特殊圖類完美匹配數(shù)目的有效方法，用此方法還可以求出一些圖的所有Hamilton圈的數(shù)目[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]張福基，陳榮斯.六角系統(tǒng)克庫勒結(jié)構(gòu)的計(jì)數(shù)[J].新疆大學(xué)學(xué)報(bào)：自然科學(xué)版，1986，3（3）：10-14.

[8]張福基，陳治柏.廣義渺位苯圖的完美匹配數(shù)的計(jì)算[J].新疆大學(xué)學(xué)報(bào)：自然科學(xué)版，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]王洪偉.二部圖匹配強(qiáng)迫數(shù)的譜[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2009，44（12）：30-35.

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

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

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

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

[17]唐保祥，任韓.3類圖完美匹配的計(jì)數(shù)[J].南京師大學(xué)報(bào)：自然科學(xué)版，2012，35（1）：16-21.

[18]唐保祥，任韓.6類圖完美匹配的數(shù)目[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，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

匹配計(jì)數(shù)理論是圖論的核心內(nèi)容之一，此問題有很強(qiáng)的物理學(xué)、計(jì)算機(jī)科學(xué)和化學(xué)背景；但是，一般圖的完美匹配計(jì)數(shù)問題卻是NP-難問題。用劃分、求和、再嵌套遞推的方法給出了4類圖完美匹配數(shù)目的顯式表達(dá)式；所給出的方法，可以計(jì)算出相同結(jié)構(gòu)重復(fù)出現(xiàn)的許多圖的所有完美匹配的數(shù)目。

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

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.

國家自然科學(xué)基金（No.11171114）。

唐保祥（1961—），男，副教授，研究方向：圖論和組合數(shù)學(xué)。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