2類圖完美匹配數(shù)目的解析式*

唐保祥，任 韓

(1. 天水師范學院數(shù)學與統(tǒng)計學院, 甘肅 天水 741001；2. 華東師范大學數(shù)學系, 上海 200062)

2類圖完美匹配數(shù)目的解析式*

唐保祥1，任 韓2

(1. 天水師范學院數(shù)學與統(tǒng)計學院, 甘肅 天水 741001；2. 華東師范大學數(shù)學系, 上海 200062)

匹配計數(shù)理論是圖論研究的重要內(nèi)容之一，而且是一個有生機和活力的研究領(lǐng)域。它不僅有很強的應用背景，而且在過去的幾十年中，它是快速發(fā)展的組合論中許多重要思想的源泉。但是，一般圖的完美匹配計數(shù)問題卻是NP-難問題。用劃分，求和，再遞推的方法給出了2類圖完美匹配數(shù)目的計算公式，所給出的方法，可以計算出許多類圖的所有完美匹配的數(shù)目。

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

圖的完美匹配計數(shù)理論有很強的物理學和化學背景，其研究成果已經(jīng)在多個領(lǐng)域得到應用。由于得到應用領(lǐng)域的支持，并與其他理論課題發(fā)生密切聯(lián)系，受到眾多學者的關(guān)注[1-11]。但是，Valiant在1979年證明了，圖(即使是偶圖)的完美匹配計數(shù)問題是NP-難問題。一般地，要給出一個圖完美匹配的數(shù)目是非常困難的。本文給出了2類美匹配數(shù)目的計算公式，所給方法，適合相同結(jié)構(gòu)重復出現(xiàn)的很多圖完美匹配數(shù)目的求解。

1 概 念

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

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

圖1 2-nT4圖Fig.1 Figure of 2-nT4

圖2 1-nT2圖Fig.2 Figure of 1-nT2

2 結(jié)果及其證明

定理1f(n)表示圖2-nT4的完美匹配的數(shù)目，則

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

圖3 G1圖Fig.3 Figure of G1

(1)

綜上所述，

(2)

把(1)式代入(2)式得

(3)

由(2)式得

(4)

(3)式-2×(4)式得

(5)

易知f(1)=8，g(1)=10。故由(2)式，得f(2)=72。故遞推式(5)的通解為

證畢。

大多數(shù)存在完美匹配的2邊連通圖有指數(shù)多個完美匹配[6-11]。下面定理給出了一類有2n+1完美匹配的2邊連通圖。

定理2σ(n)表示圖1-nT2的完美匹配的數(shù)目，則σ(n)=2n+1。

證明 圖1-nT2顯然存在完美匹配。圖1-nT2含邊u03u02，u03u14的完美匹配的

圖1-nT2的完美匹配可劃分如下3種情形：

情形1 圖1-nT2包含邊u03u02,u14u13的完美匹配數(shù)為1。

情形2 圖1-nT2包含邊u03u14,u02u13的完美匹配數(shù)為1。

情形3 由σ(n)的定義，圖1-nT2包含邊u03u14,u02u01的完美匹配數(shù)為σ(n-1)。

所以，得遞推關(guān)系式

(6)

易知σ(1)=3，所以(6)式得σ(n)=2n+1。證畢。

[1]ZHANGHP,ZHANGFJ.Perfectmatchingsofpolyominographs[J]. Graphs and Combinatorics, 1997, 13(3): 259-304.

[3] KARDOS F, KRL D, MISKUF J, et al. Fullerene graphs have exponentially many perfect matchings [J]. Journal of Mathematical Chemistry, 2008, 46(2): 443-447.

[4] ZHANG H P. The connectivity of Z-transformation graphs of perfect matchings of polyominoes [J]. Discrete Mathematics, 1996, 158(1/2/3): 257-272.

[6] 張蓮珠. 渺位四角系統(tǒng)完美匹配數(shù)的計算[J]. 廈門大學學報(自然科學版), 1998, 37(5): 629-633.

[7] 林泓, 林曉霞. 若干四角系統(tǒng)完美匹配數(shù)的計算[J]. 福州大學學報(自然科學版), 2005, 33(6): 704-710.

[8] YAN W G, ZHANG F J. Enumeration of perfect matchings of a type of Cartesian products of graphs [J]. Discrete Applied Mathematics, 2006, 154(1): 145-157.

[9] 唐保祥，任韓. 6類圖完美匹配的數(shù)目[J]. 中山大學學報(自然科學版), 2012, 51(1): 12-16.

[10] 唐保祥，任韓. 4 類圖完美匹配數(shù)目的遞推求法[J]. 數(shù)學雜志, 2015, 353(2): 626-634.

[11] 唐保祥，任韓. 3類特殊圖完美對集數(shù)的計算[J]. 南開大學學報(自然科學版), 2014, 47(5): 11-16.

The analytic formula of the number of perfect matchings of two types of graphs

TANGBaoxiang1,RENHan2

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

Matching counting theory is an important part of graph theory and also a active research field. It has not only many applications background, and also the source of many important ideas developed during the rapid growth of combinatorics during the last several decades. But the problem of counting the number of perfect matchings for general graphs is NP-hard. By applying differentiation, summation and re-recursion calculation, several counting formulas of the perfect matchings for two specific types of graphs are given. By the method presented in this paper, the number of all perfect matchings of many graphs can be calculated.

perfect matching; ladder; linear recurrence relation; characteristic equation

10.13471/j.cnki.acta.snus.2016.04.003

2015-11-03

國家自然科學基金資助項目(11171114)

唐保祥(1961年生)，男；研究方向：圖論和組合數(shù)學;E-mail:tbx0618@sina.com

O157.5

A

0529-6579(2016)04-0015-03