兩類圖中完美匹配數(shù)的遞推求法

唐保祥， 任 韓

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

圖的完美匹配計數(shù)理論是近幾十年來圖論研究的熱點問題之一，其研究成果已經(jīng)應(yīng)用于多個領(lǐng)域，由于應(yīng)用的廣泛性，以及與其他理論課題的密切聯(lián)系，受到諸多學者的關(guān)注[1-8].但是，一般圖的完美匹配計數(shù)問題是NP-難問題.因此，要算出一個圖完美匹配的數(shù)目是非常困難的事情.不過，對于一些特殊的圖，把要研究的圖的所有完美匹配， 根據(jù)飽和某個頂點的完美匹配進行分類，可計算出一組有相互關(guān)系的遞推式，再根據(jù)這組遞推式之間的相互關(guān)系，可以解出遞推式的通解，從而得所研究圖的完美匹配數(shù)的計算公式[9-15]．

1 基本概念

定義1設(shè)圖G=(V(G)，E(G))有一個1-正則生成子圖，則稱這個生成子圖為圖G的完美匹配.

定義2設(shè)S1和S2是圖G的完美匹配，若S1和S2中有一條邊不同，則稱S1和S2是圖G的兩個不同的完美匹配．

定義3把Petersen圖記為Pi，它的頂點集為V(Pi)={ui1，ui2，ui3，ui4，ui5，vi1，vi2，vi3，vi4，vi5}(i=1，2，…，n)，分別連接Pi與Pi+1的頂點ui2與ui+1，5，ui3與ui+1，4(i=1，2，…，n-1)，得到的圖記為2-nP，見圖1．

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

圖2 2-nC6,4圖Fig.2 Figure of 2-nC6,4

2 主要結(jié)果

定理1設(shè)圖2-nP的完美匹配數(shù)為θ(n)，則

證明容易斷定圖2-nP存在完美匹配.欲求θ(n)的解析式，構(gòu)造圖G1.把路wt的端點w，t分別與圖2-nP的頂點u15，u14連接一條邊，產(chǎn)生的圖記為G1，見圖3．

圖3 G1圖Fig.3 Figure of G1

容易斷定圖G1存在完美匹配.令μ(n)表示圖G1的完美匹配數(shù)，S表示圖G1的完美匹配的集合，按照S中元素匹配頂點w的情況可劃分兩類:S中有邊wt的完美匹配的集合記為S1，S中有邊wu15的完美匹配的集合記為S2，根據(jù)不同完美匹配的定義知，S1∩S2=?，S=S1∪S2，故μ(n)=|S|=|S1|+|S2|.

因為wt∈S1，故wu15，tu14?S1，根據(jù)θ(n)的定義知，|M1|=θ(n).

μ(n)=θ(n)+θ(n-1)+μ(n-1).

(1)

故

故

故

故

根據(jù)θ(n)的定義知，

綜上所述，

θ(n)=4θ(n-1)+2μ(n-1).

(2)

由(1)式，得

μ(n-1)=θ(n-1)+θ(n-2)+μ(n-2).

(3)

把(3)代入(2)式，得

θ(n)=6θ(n-1)+2θ(n-2)+2μ(n-2).

(4)

由(2)式，得

θ(n-1)=4θ(n-2)+2μ(n-2).

(5)

由(4)和(5)式消去μ(n-2)，得

θ(n)=7θ(n-1)-2θ(n-2).

(6)

其中c1，c2是待定的常數(shù)．

圖4 圖G Fig.4 Figure of G

由圖4知，θ(1)=6，μ(1)=8.所以由(2)式，得θ(2)=40.故

定理2設(shè)圖2-nC6，4的完美匹配數(shù)為ψ(n)，則

ψ(n)=25·26n-1.

證明容易斷定圖2-nC6，4存在完美匹配.欲求ψ(n)的解析式，構(gòu)造圖G2.把路xy的端點x，y分別與圖2-nC6，4的頂點u16，u15連接一條邊， 產(chǎn)生的圖記為G2，見圖5．

圖5 G2 圖Fig.5 Figure of G2

容易斷定圖G2存在完美匹配.χ(n)表示圖G2的完美匹配數(shù)，圖G2的完美匹配的集合表示為S，按照S中元素匹配頂點x的情況可分兩類:S中有邊xy的完美匹配的集合記為S1，S中有邊xu16的完美匹配的集合記為S2，根據(jù)不同完美匹配的定義知，

S1∩S2=?，S=S1∪S2，

故χ(n)=|S|=|S1|+|S2|.

因為xy∈S1，故xu61，yu15?S1，由ψ(n)的定義知，|S1|=ψ(n).

Si∩Sj=?(1≤i

所以

所以|S2|=4ψ(n-1)+χ(n-1).故

χ(n)=ψ(n)+4ψ(n-1)+χ(n-1).

(7)

故

故

根據(jù)ψ(n)的定義，

根據(jù)χ(n)的定義知，

故

根據(jù)χ(n)的定義知，

根據(jù)ψ(n)的定義知，

故

根據(jù)ψ(n)的定義知，

ψ(n)=20ψ(n-1)+5χ(n-1).

(8)

由(7)式，得

χ(n-1)=ψ(n-1)+4ψ(n-2)+χ(n-2).

(9)

把(9)式代入(8)式，得

ψ(n)=25ψ(n-1)+20ψ(n-2)+5χ(n-2).

(10)

由(8)式，得

ψ(n-1)=20ψ(n-2)+5χ(n-2).

(11)

由(10)式和(11)式消去χ(n-2)，得

ψ(n)=26ψ(n-1)=…=26n-1ψ(1).

圖6 圖2-1×G6,4的所有完美匹配Fig.6 All preferct matchings of 2-1×G6,4

由圖(6)得，ψ(1)=25.故ψ(n)=25·26n-1.