3类图完美匹配计数公式的嵌套递推求法*

唐保祥，任韩

(1. 天水师范学院数学与统计学院，甘肃 天水 741001；2. 华东师范大学数学系，上海 200062)

图的匹配计数理论是图论研究的重要内容之一，在过去的几十年中，它是快速发展的组合论中许多重要思想的源泉，其研究成果已经在多个领域得到应用，引起了一些学者的广泛研究，得到了许多特殊图类完美匹配的计数公式[1-9]。遗憾的是，Valiant[1]1979年证明了，1个图(即使是偶图)的完美匹配计数是NP-难问题。因此，要得到1个图的完美匹配的数目是很困难的。本文使用了嵌套递推的方法给出了3类新图的完美匹配数目的计算公式，所给方法，适合结构比较复杂的图类完美匹配数的求解。

1 基本概念

定义1 若图G的2个完美匹配M1和M2中有一条边不同，则称M1和M2是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 结果及其证明

定理1f(n)表示图2-nD4的完美匹配的数目，则

证明 为了求f(n)，先定义一个图G1，并求其完美匹配的数目。删除图2-nD4的顶点x1,x2,x3,x4得到的记为G1，如图4所示。易知图G1有完美匹配。α(n)表示图G1的完美匹配的数目。

图4 C1图Fig.4 Figure of C1

先求α(n)。设图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有完美匹配。设图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)。

因为M2=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)

容易计算α(1)=4;由α(n)的定义可知α(0)=2;由式(1)得α(2)=12; 由式(2)得f(1)=12，f(2)=32。解线性递推式(7)，得

定理2g(n)表示图2-nC6,3的完美匹配的数目，则

证明显然图2-nC6,3有完美匹配。设图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)。

因为M2=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的完美匹配的数目，则

h(n)=2·3n-1

证明为了求h(n)，先定义2个图G2和G3，并求其完美匹配的数目。将路u1u2的端点u1,u2分别与顶点u11,u16连接得到的记为G2，如图6所示;将路u1u2的端点u1,u2分别与顶点u16,u15连接得到的记为G3，如图7所示。

图6 G2图Fig.6 Figure of G2

图7 G3图Fig.7 Figure of G3

易知图G2和G3都有完美匹配，且G2≅G3，故图G2和G3的完美匹配数相等。β(n)表示图G2的完美匹配的数目。设图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有完美匹配。设图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。