完美匹配的计数理论在分子化学、晶体物理学和计算机科学中有重要的应用，在图论和组合数学中也有许多丰富而深刻的成果^[1-8]，但仍有许多问题尚待解决.

对于图完美匹配的计数，学者们创造了精巧的计数方法^[1-9].但是，目前还没有计算一般图的完美匹配数目的统一方法.对于一些特殊图，可用嵌套递推的方法得到其完美匹配数目的计算公式^[10-17].本文构造了2类新图 2-2nK₅和2-nZ₅，用递推的方法研究了这2类新图的完美匹配的计数问题，并得到其完美匹配的计数公式，以期得到更多图的完美匹配的数目，为完美匹配的应用提供一定的理论支持.

1.   预备知识

定义1^[10]  设图G是有完美匹配的图，若图G的2个完美匹配N₁和N₂中有1条边不同，则称N₁和N₂是G的2个不同的完美匹配.

定义2  设K₅ⁱ是5个顶点的完全图，V(K₅ⁱ)={u_i1, u_i2, u_i3, u_i4, u_i5}(i=1, 2, …, 2n).分别连接完全图K₅ⁱ与K₅ⁱ⁺¹的顶点u_i2与u_{i+1, 5}、u_i3与u_{i+1, 4}(i=1, 2, …, 2n-1)后得到的图记为2-2nK₅，如图 1所示.

图  1  2-2nK₅图

Figure  1.  Figure of 2-2nK₅

下载: 全尺寸图片 幻灯片

定义3  分别连接5圈u_i1u_i2u_i3u_i4u_i5u_i1与5圈v_i1v_i2v_i3v_i4v_i5v_i1的顶点u_ji与v_ji(j=1, 2, 3, 4, 5), 得到的图记为Z₅ⁱ(i=1, 2, …, n).分别连接图Z₅ⁱ与Z₅ⁱ⁺¹的顶点u_i2与u_{i+1, 5}、u_i3与u_{i+1, 4}(i=1, 2, …, n-1)，得到的图记为2-nZ₅，如图 2所示.

图  2  2-nZ₅图

Figure  2.  Figure of 2-nZ₅

下载: 全尺寸图片 幻灯片

2.   主要结果

定理1  设图 2-2nK₅的完美匹配数为f(2n)，则f(2n)=18·20^n-1.

证明  容易判断图 2-2nK₅有完美匹配.要得到f(2n)的表达式，先定义一个图W₁，并计算其完美匹配数的递推式.把路pq的端点p、q分别与图 2-2nK₅的顶点u₁₅、u₁₄连接一条边，形成的图记为W₁, 如图 3所示.

图  3  W₁图

Figure  3.  Figure of W₁

下载: 全尺寸图片 幻灯片

容易判断图W₁有完美匹配，h(2n)表示图W₁的完美匹配数.记图W₁的完美匹配集合为N，含有边pq、pu₁₅的完美匹配集合分别为N₁、N₂，根据不同完美匹配的定义有N₁∩N₂=Ø，N=N₁∪N₂，故h(2n)=|N|=|N₁|+|N₂|.因为pq∈N₁, 所以pu₁₅, qu₁₄∉N₁, 故由f(2n)的定义知，|N₁|=f(2n).

N₂可分为6类:含有边pu₁₅、qu₁₄、u₁₁u₁₃、u₁₂u₂₅、u₂₁u₂₄的完美匹配集合记为N₂¹; 含有边pu₁₅、qu₁₄、u₁₁u₁₃、u₁₂u₂₅、u₂₁u₂₃、u₂₂u₂₄的完美匹配集合记为N₂²; 含有边pu₁₅、qu₁₄、u₁₁u₁₃、u₁₂u₂₅、u₂₁u₂₂、u₂₃u₂₄的完美匹配集合记为N₂³; 含有边pu₁₅、qu₁₄、u₁₁u₁₂、u₁₃u₂₄、u₂₁u₂₅的完美匹配集合记为N₂⁴; 含有边pu₁₅、qu₁₄、u₁₁u₁₂、u₁₃u₂₄、u₂₁u₂₃、u₂₅u₂₂的完美匹配集合记为N₂⁵; 含有边pu₁₅、qu₁₄、u₁₁u₁₂、u₁₃u₂₄、u₂₁u₂₂、u₂₅u₂₃的完美匹配集合记为N₂⁶.则N₁ⁱ∩N₁^j=Ø(1≤i < j≤6), N₂=$\mathop \cup \limits_{i = 1}^6$N₂ⁱ, 故|N₂|=$\sum\limits_{i = 1}^6 {\left| {N_2^i} \right|}$.

由h(n)的定义, 有:

故

再求f(2n)的递推式. 图 2-2nK₅的完美匹配集合记为N, 按照N中元素饱和顶点u₁₅的情况可分为4类:含有边u₁₅u₁₁的完美匹配集合为N₁, 含有边u₁₅u₁₂的完美匹配集合为N₂, 含有边u₁₅u₁₃的完美匹配集合为N₃, 含有边u₁₅u₁₄的完美匹配集合为N₄, 则N_i∩N_j=Ø(1≤i < j≤4), N=$\mathop \cup \limits_{i = 1}^4$N_i, 故$|N| = \sum\limits_{i = 1}^4 {\left| {{N_i}} \right|}$.

N₁可分为6类:含有边u₁₅u₁₁、u₁₂u₁₄、u₁₃u₂₄、u₂₅u₂₁的完美匹配集合记为N₁¹; 含有边u₁₅u₁₁、u₁₂u₁₄、u₁₃u₂₄、u₂₅u₂₂、u₂₁u₂₃的完美匹配集合记为N₁²; 含有边u₁₅u₁₁、u₁₂u₁₄、u₁₃u₂₄、u₂₅u₂₃、u₂₁u₂₂的完美匹配集合记为N₁³; 含有边u₁₅u₁₁、u₁₄u₁₃、u₁₂u₂₅、u₂₁u₂₄的完美匹配集合记为N₁⁴; 含有边u₁₅u₁₁、u₁₄u₁₃、u₁₂u₂₅、u₂₁u₂₃、u₂₂u₂₄的完美匹配集合记为N₁⁵; 含有边u₁₅u₁₁、u₁₄u₁₃、u₁₂u₂₅、u₂₁u₂₂、u₂₃u₂₄的完美匹配集合记为N₁⁶.则N₁ⁱ∩N₁^j=Ø(1≤i < j≤6), N₁=$\mathop \cup \limits_{i = 1}^6$N₁ⁱ, 故|N₁|=$\sum\limits_{i = 1}^6 {\left| {N_1^i} \right|}$.

由h(2n)的定义，有|N₁¹|=|N₁⁴|=h(2(n-1)); 由h(2n)的定义，有|N₁²|=|N₁³|=|N₁⁵|=|N₁⁶|=f(2(n-1)).故|N₁|=4f(2(n-1))+2h(2(n-1)).

N₂可分为3类:含有边u₁₅u₁₂、u₁₁u₁₄、u₁₃u₂₄、u₂₅u₂₁的完美匹配集合记为N₂¹; 含有边u₁₅u₁₂、u₁₁u₁₄、u₁₃u₂₄、u₂₅u₂₂、u₂₁u₂₃的完美匹配集合记为N₂²; 含有边u₁₅u₁₂、u₁₁u₁₄、u₁₃u₂₄、u₂₅u₂₃、u₂₁u₂₂的完美匹配集合记为N₂³.则N₁ⁱ∩N₁^j=Ø (1≤i < j≤3), N₂=N₂¹∪N₂²∪N₂³, 故|N₂|=|N₂¹|+|N₂²|+|N₂³|.

由h(2n)的定义，有|N₂¹|=h(2(n-1)); 由f(2n)的定义，有|N₂²|=|N₂³|=f(2(n-1)).故|N₂|=h(2(n-1))+2f(2(n-1)).

N₃可分为3类:含有边u₁₅u₁₃、u₁₁u₁₄、u₁₂u₂₅、u₂₁u₂₄的完美匹配集合记为N₃¹; 含有边u₁₅u₁₃、u₁₁u₁₄、u₁₂u₂₅、u₂₁u₂₃、u₂₂u₂₄的完美匹配集合记为N₃²; 含有边u₁₅u₁₃、u₁₁u₁₄、u₁₂u₂₅、u₂₁u₂₂、u₂₃u₂₄的完美匹配集合记为N₂³.则N₁ⁱ∩N₁^j=Ø (1≤i < j≤3), N₃=N₃¹∪N₃²∪N₃³, 故|N₃|=|N₃¹|+|N₃²|+|N₃³|.

由h(2n)的定义，有|N₃¹|=h(2(n-1)), |N₃²|=|N₃³|=f(2(n-1)), 故|N₃|=h(2(n-1))+2f(2(n-1)).

N₄可分为6类:含有边u₁₅u₁₄、u₁₁u₁₃、u₁₂u₂₅、u₂₁u₂₄的完美匹配集合记为N₄¹; 含有边u₁₅u₁₄、u₁₁u₁₃、u₁₂u₂₅、u₂₁u₂₃、u₂₂u₂₄的完美匹配集合记为N₄²; 含有边u₁₅u₁₄、u₁₁u₁₃、u₁₂u₂₅、u₂₁u₂₂、u₂₃u₂₄的完美匹配集合记为N₄³; 含有边u₁₅u₁₄、u₁₁u₁₂、u₁₃u₂₄、u₂₁u₂₅的完美匹配集合记为N₄⁴; 含有边u₁₅u₁₄、u₁₁u₁₂、u₁₃u₂₄、u₂₅u₂₂、u₂₁u₂₃的完美匹配集合记为N₄⁵; 含有边u₁₅u₁₄、u₁₁u₁₂、u₁₃u₂₄、u₂₅u₂₃、u₂₁u₂₂的完美匹配集合记为N₄⁶.则N₄ⁱ∩N₄^j=Ø(1≤i < j≤6), N₄=$\mathop \cup \limits_{i = 1}^6$N₄ⁱ, 故|N₄|=$\sum\limits_{i = 1}^6 {\left| {N_4^i} \right|}$.

由h(2n)的定义，有|N₄¹|=|N₄⁴|=h(2(n-1)); 由f(2n)的定义, 有|N₄²|=|N₄³|=|N₄⁵|=|N₄⁶|=f(2(n-1)), 故|N₄|=2h(2(n-1))+4f(2(n-1)).

综上所述，有

由式(1)，得

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

再由式(2)，得

由式(4)、(5)，得f(2n)=20f(2(n-1)), 故f(2n)=20^n-1f(2×1).

由图 4知f(2×1)=18.所以f(2n)=18·20^n-1.

图  4  图 2-2×1×K₅的所有完美匹配

Figure  4.  All perfect matchings of 2-2×1×K₅

下载: 全尺寸图片 幻灯片

定理2  设图 2-nZ₅的完美匹配数为g(n)，则$g(n) = \frac{{34 + 5\sqrt {34} }}{{68}} \cdot {(6 + \sqrt {34} )^n} + \frac{{34 - 5\sqrt {34} }}{{68}} \cdot {(6 - \sqrt {34} )^n}$.

证明  容易判断图 2-nZ₅有完美匹配.要得到g(n)的表达式，先定义一个图W₂，并计算它的完美匹配数的递推式.把路wt的端点w、t分别与图 2-nZ₅的顶点u₁₅、u₁₄连接一条边，形成的图记为W₂, 如图 5所示.

图  5  W₂图

Figure  5.  Figure of W₂

下载: 全尺寸图片 幻灯片

容易判断图W₂有完美匹配.记ϕ(n)为图W₂的完美匹配数，设图W₂的完美匹配集合为N，含有边wt、wu₁₅的完美匹配集合分别为N₁、N₂，则N₁∩N₂=Ø，N=N₁∪N₂，故ϕ(n)=|N|=|N₁|+|N₂|.

因为wt∈N₁, 所以wu₁₅, tu₁₄∉N₁, 故由g(n)的定义，有|N₁|=g(n).

N₂可分为3类:含有边wu₁₅、tu₁₄、v₁₅v₁₄、u₁₁u₁₂、v₁₁v₁₂、v₁₃u₁₃的完美匹配集合记为N₂¹; 含有边wu₁₅、tu₁₄、v₁₅v₁₄、u₁₁v₁₁、v₁₂u₁₂、v₁₃u₁₃的完美匹配集合记为N₂²; 含有边wu₁₅、tu₁₄、v₁₅v₁₄、u₁₁v₁₁、v₁₂v₁₃的完美匹配集合记为N₂³.则N₂ⁱ∩N₂^j=Ø(1≤i < j≤3), N₂=N₂¹∪N₂²∪N₂³, 故|N₂|=|N₂¹|+|N₂²|+|N₂³|.

由g(n)的定义，有|N₂¹|=|N₂²|=g(n-1);由ϕ(n)的定义，有|N₂³|=ϕ(n-1).则|N₂|=2g(n-1)+ϕ(n-1), 故

再求g(n)的递推式.记图 2-nZ₅的完美匹配集合为N, 图 2-nZ₅分别含有边u₁₅u₁₁、u₁₅v₁₅、u₁₅u₁₄的完美匹配集合为N₁、N₂、N₃, 则N_i∩N_j=Ø(1≤i < j≤3), N=N₁∪N₂∪N₃，故g(n)=|N|=|N₁|+|N₂|+|N₃|.

N₁可分为3类:含有边u₁₅u₁₁、v₁₅v₁₁、v₁₄v₁₃、u₁₄u₁₃、v₁₂u₁₂的完美匹配集合记为N₁¹; 含有边u₁₅u₁₁、v₁₅v₁₁、v₁₄u₁₄、v₁₃u₁₃、v₁₂u₁₂的完美匹配集合记为N₁²; 含有边u₁₅u₁₁、v₁₅v₁₁、v₁₄u₁₄、v₁₂v₁₃的完美匹配集合记为N₁³.则N₁ⁱ∩N₁^j=Ø(1≤i < j≤3), N₁=N₁¹∪N₁²∪N₁³，故|N₁|=|N₁¹|+|N₁²|+|N₁³|.

由g(n)的定义，有|N₁¹|=|N₁²|=g(n-1);由ϕ(n)的定义，有|N₁³|=ϕ(n-1).

因此，|N₁|=2g(n-1)+ϕ(n-1).

N₂可分为5类:含有边u₁₅v₁₅、u₁₁u₁₂、v₁₁v₁₂、v₁₄v₁₃、u₁₄u₁₃的完美匹配集合记为N₂¹; 含有边u₁₅v₁₅、u₁₁u₁₂、v₁₁v₁₂、v₁₄u₁₄、v₁₃u₁₃的完美匹配集合记为N₂²; 含有边u₁₅v₁₅、u₁₁v₁₁、v₁₂u₁₂、v₁₄v₁₃、u₁₄u₁₃的完美匹配集合记为N₂³; 含有边u₁₅v₁₅、u₁₁v₁₁、v₁₂u₁₂、v₁₃u₁₃、v₁₄u₁₄的完美匹配集合记为N₂⁴; 含有边u₁₅v₁₅、u₁₁v₁₁、v₁₂v₁₃、v₁₄u₁₄的完美匹配集合记为N₂⁵.则N₂ⁱ∩N₂^j=Ø(1≤i < j≤5), N₂=$\mathop \cup \limits_{i = 1}^5$N₂ⁱ, 故|N₂|=$\sum\limits_{ - 1}^5 {\left| {N_2^i} \right|}$.

由g(n)的定义，有|N₂¹|=|N₂²|=|N₂³|=|N₂⁴|=g(n-1);由ϕ(n)的定义，有|N₂⁵|=ϕ(n-1).故|N₂|=4g(n-1)+ϕ(n-1).

N₃可分为3类:含有边u₁₅u₁₄、v₁₅v₁₄、u₁₁u₁₂、v₁₁v₁₂、v₁₃u₁₃的完美匹配集合记为N₃¹; 含有边u₁₅u₁₄、v₁₅v₁₄、u₁₁v₁₁、v₁₂u₁₂、v₁₃u₁₃的完美匹配集合记为N₃²; 含有边u₁₅u₁₄、v₁₅v₁₄、u₁₁v₁₁、v₁₂v₁₃的完美匹配集合记为N₃³.则N₃ⁱ∩N₃^j=Ø(1≤i < j≤3), N₃=N₃¹∪N₃²∪N₃³，故|N₃|=|N₃¹|+|N₃²|+|N₃³|.

由g(n)的定义，有|N₃¹|=|N₃²|=g(n-1);由ϕ(n)的定义，有|N₃³|=ϕ(n-1).因此，|N₃|=2g(n-1)+ϕ(n-1).

综上所述，有

由式(6)，得

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

由式(7)，得

式(9)减去式(10)，得

式(11)的特征方程为x²-12x+2=0, 特征根为6±$\sqrt {34}$.

故线性递推式(11)的通解为g(n)=c₁(6+$\sqrt {34}$)ⁿ+c₂(6-$\sqrt {34}$)ⁿ, 其中c₁、c₂为待定常数.

由图 6知g(1)=11.由图 7知ϕ(1)=14.由式(7)得g(2)=130.

图  6  图 2-1×Z₅的所有完美匹配

Figure  6.  All perfect matchings of 2-1×Z₅

下载: 全尺寸图片 幻灯片

图  7  W₃图

Figure  7.  Figure of W₃

下载: 全尺寸图片 幻灯片

故由g(n)=c₁(6+$\sqrt {34}$)ⁿ+c₂(6-$\sqrt {34}$)ⁿ, g(1)=11和g(2)=130，可得