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

唐保祥，任 韓

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

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

唐保祥1，任 韓2

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

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

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

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

1 概 念

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

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

圖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個(gè)圖G1和G2，并求其完美匹配的數(shù)目。將長(zhǎng)為1的路u1u2的端點(diǎn)u1和u2分別與圖2-nT4的頂點(diǎn)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ù)多個(gè)完美匹配[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ì)算[J]. 廈門(mén)大學(xué)學(xué)報(bào)(自然科學(xué)版), 1998, 37(5): 629-633.

[7] 林泓, 林曉霞. 若干四角系統(tǒng)完美匹配數(shù)的計(jì)算[J]. 福州大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 51(1): 12-16.

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

[11] 唐保祥，任韓. 3類特殊圖完美對(duì)集數(shù)的計(jì)算[J]. 南開(kāi)大學(xué)學(xué)報(bào)(自然科學(xué)版), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(11171114)

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

O157.5

A

0529-6579(2016)04-0015-03