3類圖完美匹配計(jì)數(shù)公式的嵌套遞推求法*

唐保祥，任韓

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

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

1 基本概念

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

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

圖2 2-nC63圖Fig.2 Figure of 2-nC63

圖3 3-nC6圖Fig.3 Figure of 3-nC6

2 結(jié)果及其證明

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

證明 為了求f(n)，先定義一個(gè)圖G1，并求其完美匹配的數(shù)目。刪除圖2-nD4的頂點(diǎn)x1,x2,x3,x4得到的記為G1，如圖4所示。易知圖G1有完美匹配。α(n)表示圖G1的完美匹配的數(shù)目。

圖4 C1圖Fig.4 Figure of C1

先求α(n)。設(shè)圖G1的完美匹配集合為M，圖G1含邊u11v11，u11u21的完美匹配集合分別為M1，M2，則M1∩M2=?，所以M=M1∪M2，故α(n)=M=M1+M2。

求M1?M∈M1，u11v11,v12v14,v13u12∈M，由α(n)的定義知，M1=α(n-1)。

求M2情形1M21?M2，?M∈M21，u11u21,v11v14,v12v13,u12u22,v21v24,v22v23∈M，故由α(n)的定義知，M21=α(n-2)。

情形2M22?M2，?M∈M22，u11u21,v11v14,v12v13,u12u22,v21v22,v24v23∈M，故由

α(n)的定義知，M22=α(n-2)。

情形3M23?M2，?M∈M23，u11u21,v11v12,v14v13,u12u22,v21v24,v22v23∈M，故由

α(n)的定義知，M23=α(n-2)。

情形4M24?M2，?M∈M24，u11u21,v11v12,v14v13,u12u22,v21v22,v24v23∈M，故由

α(n)的定義知，M24=α(n-2)。

綜上所述，

α(n)=α(n-1)+4α(n-2)

(1)

再求f(n)。易知圖2-nD4有完美匹配。設(shè)圖2-nDC4的完美匹配集合為M，圖2-nD4含邊x4x1，x4x2，x4x3的完美匹配集合分別為M1，M2，M3，則Mi∩Mj=?(1≤i

求M1?M∈M1，x4x1,x2x3∈M，由α(n)的定義知，M1=α(n)。

求M2情形1M21?M2，?M∈M21，x4x2,x1u11,x3u12,v11v14,v12v13∈M，由α(n)

的定義知，M21=α(n-1)。

情形2M22?M2，?M∈M22，x4x2,x1u11,x3u12,v11v12,v14v13∈M，由α(n)的定

義知，M22=α(n-1)。

因?yàn)镸2=M21∪M22，M21∩M22=?，所以M2=M21+M22=2α(n-1)。

求M3?M∈M3，x4x3,x1x2∈M，由α(n)的定義知，M3=α(n)

綜上所述，

f(n)=2α(n)+2α(n-1)

(2)

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

f(n)=4α(n-1)+8α(n-2)=

4α(n-1)+4α(n-2)+4α(n-2)=

2f(n-1)+4α(n-2)

(3)

再由式(2)，得

2f(n-1)=4α(n-1)+4α(n-2)

(4)

式(3)-(4)，得

f(n)=4f(n-1)-4α(n-1)

(5)

由式(5)得

f(n-1)=4f(n-2)-4α(n-2)

(6)

式(3)+(6)，得

f(n)=f(n-1)+4f(n-2)

(7)

容易計(jì)算α(1)=4;由α(n)的定義可知α(0)=2;由式(1)得α(2)=12; 由式(2)得f(1)=12，f(2)=32。解線性遞推式(7)，得

定理2g(n)表示圖2-nC6,3的完美匹配的數(shù)目，則

證明顯然圖2-nC6,3有完美匹配。設(shè)圖2-nC6,3的完美匹配集合為M，圖2-nC6,3含邊u11u12,u11u16的完美匹配集合分別為M1，M2，則M1∩M2=?，M=M1∪M2，故g(n)=M=M1+M2。

求M1?M∈M1，u11u12,u13u14,u15u16∈M，由g(n)的定義知，M1=g(n-1)。

求M2情形1M21?M2，?M∈M22，u11u16,u15u14,u12u13∈M，故由g(n)的定義知，M21=g(n-1)。

情形2M22?M2，?M∈M22，u11u16,u15u14,u12u26,u13u25,u21u22,u24u23∈M，故由g(n)的定義知，M22=g(n-2)。

因?yàn)镸2=M21∪M22，M21∩M22=?，所以

M2=M21+M22=g(n-1)+g(n-2)

因此，

g(n)=2g(n-1)+g(n-2)

(8)

圖5 2-2C63圖Fig.5 Figure of 2-2C63

易知g(1)=2，由圖5知g(2)=5。

解線性遞推式(8)，得

定理3h(n)表示圖3-nC6的完美匹配的數(shù)目，則

h(n)=2·3n-1

證明為了求h(n)，先定義2個(gè)圖G2和G3，并求其完美匹配的數(shù)目。將路u1u2的端點(diǎn)u1,u2分別與頂點(diǎn)u11,u16連接得到的記為G2，如圖6所示;將路u1u2的端點(diǎn)u1,u2分別與頂點(diǎn)u16,u15連接得到的記為G3，如圖7所示。

圖6 G2圖Fig.6 Figure of G2

圖7 G3圖Fig.7 Figure of G3

易知圖G2和G3都有完美匹配，且G2?G3，故圖G2和G3的完美匹配數(shù)相等。β(n)表示圖G2的完美匹配的數(shù)目。設(shè)圖G2的完美匹配集合為M，圖G2的含邊u1u11，u1u2的完美匹配集合分別為M1，M2，則M1∩M2=?，故M=M1∪M2，β(n)=M=M1+M2。

求M1?M∈M1，u1u11,u2u16,u15u14∈M，由β(n)的定義知，M1=β(n-1)。

求M2?M∈M2，u1u2∈M，由h(n)的定義知，M2=h(n)。故

β(n)=h(n)+β(n-1)

(9)

再求h(n)。易知圖3-nC6有完美匹配。設(shè)圖3-nC6的完美匹配集合為M，圖3-nC6含邊u16u11,u16u15的完美匹配集合分別為M1，M2，則M1∩M2=?，所以M=M1∪M2，故h(n)=M=M1+M2。

求M1?M∈M1，u16u11,u15u14∈M，由β(n)的定義知，M1=β(n-1)。

求M2?M∈M2，u16u15,u11u12∈M，由β(n)的定義知，M2=β(n-1)。

所以，

h(n)=2β(n-1)

(10)

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

h(n)=2h(n-1)+2β(n-2)

(11)

由式(10)，得

h(n-1)=2β(n-2)

(12)

再由式(11)和式(12)，得

h(n)=3h(n-1)=3n-1h(1)

易知h(1)=2，所以h(n)=2·3n-1。