0 引言

图的完美匹配计数已经被证实是NP-难问题, 因此要得到一般图的完美匹配数目是非常困难的.该问题在蛋白质结构预测、量子化学、晶体物理学和计算机科学等领域都有重要应用, 对此问题的研究具有非常重要的理论价值和现实意义^[1-9].本文用划分、求和、再递推的方法分别给出了4-1-nC₁₀和2-nT₂图的完美匹配数目的计算公式.该方法能够计算许多类图的所有完美匹配的数目.

定义1 若G图的2个完美匹配M₁和M₂中有一条边不同, 则称M₁和M₂是G的2个不同的完美匹配.

定义2 设2条长为n的路：P₁=u₁u₂…u_n+1, P₂=v₁v₂…v_n+1, 分别连接路P₁与P₂的顶点u_i与v_i(i=1, 2, …, n+1) 得到的图, 称长为n的梯子, 记为T_n.

n个长为10的圈记为

$ {C^i} = {u_{i1}}{u_{i2}}{u_{i3}}{v_{i2}}{w_{i3}}{w_{i2}}{w_{i1}}{w_{i4}}{v_{i1}}{u_{i4}}\left( {i = 1, 2, ..., n} \right). $

连接圈Cⁱ上顶点v_i1与v_i2, 连接圈Cⁱ与Cⁱ⁺¹的顶点u_i2与u_{i+1, 1}, u_i3与u_{i+1, 4}, w_i3与w_{i+1, 4}, w_i2与w_{i+1, 1}(i=1, 2, …, n－1), 再分别连接圈C¹与Cⁿ的顶点u₁₄与w₁₄, u₁₁与w₁₁, u_n3与w_n3, u_n2与w_n2, 得到的图记为4-1-nC₁₀, 如图 1所示.

设n个长为2的梯子T₂ⁱ, 其顶点集为V(T₂ⁱ)=u_i1, u_i2, u_i3, v_i1, v_i2, v_i3(i=1, 2, …, n).连接梯子T₂ⁱ和T₂ⁱ⁺¹的顶点v_i1与u_{i+1, 1}、v_i3与u_{i+1, 3}(i=1, 2, …, n-1)，再连接梯子T₂¹的顶点u₁₁与u₁₃、T₂ⁿ的顶点v_n1与v_n3，得到的图记为2-nT₂, 如图 2所示.

1 结果及其证明

定理1 f(n)表示4-1-nC₁₀图完美匹配的数目, 则

$ f\left( n \right) = {2^{n-2}} \cdot {\left( {2 + \sqrt 2 } \right)^{n + 1}} + {2^{n-2}} \cdot {\left( {2-\sqrt 2 } \right)^{n + 1}} + 1. $

证明 4-1-nC₁₀图是3正则3边连通图, 显然存在完美匹配.欲求f(n), 需定义G₁, G₂, G₃图, 并分别求出其完美匹配的数目.4-1-nC₁₀图删除边u₁₁w₁₁, u₁₄w₁₄后得到的图记为G; 将路u₁u₂vw的顶点u₁, u₂, w分别与G图的顶点u₁₁, u₁₄, w₁₄连接，得到的图记为G₁; 将路uvw₁w₂的顶点u, w₁, w₂分别与G图的顶点u₁₄, w₁₄, w₁₁连接，得到的图记为G₂; 将路u₁u₂的顶点u₁, u₂分别与G图的顶点u₁₁, u₁₄连接, 再将路w₁w₂的顶点w₁, w₂分别与G图的顶点w₁₄, w₁₁连接，得到的图记为G₃; G₁, G₂, G₃图分别如图 3~5所示.显然G₁, G₂, G₃图都存在完美匹配, 且${G_1} \cong {G_2} $.

设G₁, G₂, G₃图的完美匹配数分别为a(n), b(n), c(n), 则a(n)=b(n).

G₁图的完美匹配按饱和顶点u₁可划分为以下6种情形:

情形1 由c(n)的定义, G₁图包含边u₁u₁₁, u₂u₁₄, vw, v₁₁v₁₂, w₁₄w₁₁的完美匹配数为c(n-1).

情形2 由a(n)的定义, G₁图包含边u₁u₁₁, u₂u₁₄, vw, v₁₁w₁₄, w₁₁w₁₂的完美匹配数为a(n-1).

情形3 由a(n)的定义, G₁图包含边u₁u₁₁, u₂v, ww₁₄, v₁₁w₁₄, w₁₁w₁₂的完美匹配数为a(n-1).

情形4 由b(n)的定义, G₁图包含边u₁u₁₁, u₂u₁₄, vw, v₁₁w₁₄, w₁₁w₁₂的完美匹配数为b(n-1), 又a(n)=b(n), 所以b(n-1)=a(n-1).

情形5 由c(n)的定义, G₁图包含边u₁u₂, u₁₁u₁₄, vw, v₁₁v₁₂, w₁₄w₁₁的完美匹配数为c(n-1).

情形6 由a(n)的定义, G₁图包含边u₁u₂, u₁₁u₁₃, vw, v₁₁w₁₄, w₁₁w₁₂的完美匹配数为a(n-1).

综上所述,

$ a\left( n \right) = 4a\left( {n-1} \right) + 2c\left( {n-1} \right). $

(1)

G₃图的完美匹配按饱和顶点u₁可分以下8种情形求得：

情形1 由c(n)的定义, G₃图包含边u₁u₁₁, u₂u₁₄, v₁₁v₁₂, w₁w₁₄, w₂w₁₁的完美匹配数为c(n-1).

情形2 由a(n)的定义, G₃图包含边u₁u₁₁, u₂u₁₄, w₁w₂, v₁₁w₁₄, w₁₁w₁₂的完美匹配数为a(n-1).

情形3 由c(n)的定义, G₃图包含边u₁u₁₁, u₂u₁₄, v₁₁v₁₂, w₁w₂, w₁₄w₁₁的完美匹配数为c(n-1).

情形4 由c(n)的定义, G₃图包含边u₁u₂, u₁₁u₁₄, v₁₁v₁₂, w₁w₂, w₁₄w₁₁的完美匹配数为c(n-1).

情形5 由c(n)的定义, G₃图包含边u₁u₂, u₁₁u₁₄, v₁₁v₁₂, w₁w₁₄, w₂w₁₁的完美匹配数为c(n-1).

情形6 由a(n)的定义, G₃图包含边u₁u₂, u₁₁u₁₄, v₁₁w₁₄, w₁w₂, w₁₁w₁₂的完美匹配数为a(n-1).

情形7 由b(n)的定义, G₃图包含边u₁u₂, u₁₁u₁₂, u₁₄v₁₁, w₁w₁₄, w₂w₁₁的完美匹配数为b(n-1), 又a(n)=b(n), 所以b(n-1)=a(n-1).

情形8 由b(n)的定义, G₃图包含边u₁u₂, u₁₁u₁₂, u₁₄v₁₁, w₁w₂, w₁₄w₁₁的完美匹配数为b(n-1), 又a(n)=b(n), 所以b(n-1)=a(n-1).

综上所述,

$ c\left( n \right) = 4a\left( {n-1} \right) + 4c\left( {n-1} \right). $

(2)

4-1-nC₁₀图的完美匹配按饱和顶点u₁₁可分以下5种情形求得:

情形1 由c(n)的定义, 4-1-nC₁₀图包含边u₁₁w₁₁, u₁₄w₁₄, v₁₁v₁₂的完美匹配数为c(n-1).

情形2 由a(n)的定义, 4-1-nC₁₀图包含边u₁₁u₁₄, v₁₁w₁₄, w₁₁w₁₂的完美匹配数为a(n-1).

情形3 由c(n)的定义, 4-1-nC₁₀图包含边u₁₁u₁₄, w₁₁v₁₂, w₁₄w₁₁的完美匹配数为c(n-1).

情形4 由b(n)的定义, 4-1-nC₁₀图包含边u₁₁u₁₂, u₁₄v₁₁, w₁₄w₁₁的完美匹配数为b(n-1), 又a(n)=b(n), 所以b(n-1)=a(n-1).

情形5 4-1-nC₁₀图的完美匹配包含边u₁₁u₁₂, u₁₄w₁₄, v₁₁v₁₂, w₁₁w₁₂, 则该完美匹配一定包含边u_i3u_{i+1, 4}, w_i3w_{i+1, 4}, u_{i+1, 1}u_{i+1, 2}, v_{i+1, 1}v_{i+1, 2}, w_{i+1, 1}w_{i+1, 2}, i=1, 2, …, n-1.所以4-1-nC₁₀图包含边u₁₁u₁₂, u₁₄w₁₄, v₁₁v₁₂, w₁₁w₁₂的完美匹配恰有1个.

综上所述,

$ f\left( n \right) = 2a\left( {n-1} \right) + 2c\left( {n-1} \right) + 1. $

(3)

将式(1) 和(2) 代入式(3), 得

$ f\left( n \right) = 16a\left( {n-2} \right) + 12c\left( {n-2} \right) + 1, $

(4)

由式(3) 得

$ f\left( {n-1} \right) = 2a\left( {n-2} \right) + 2c\left( {n-2} \right) + 1, $

(5)

式(4)-式(5)×8得

$ f\left( n \right) = 8f\left( {n-1} \right)-4c\left( {n-2} \right) - 7. $

(6)

由式(2) 和(3) 得

$ c\left( n \right) = 2f\left( n \right)-2, $

(7)

由式(6) 和(7) 得

$ f\left( n \right) = 8f\left( {n-1} \right)-8f\left( {n-2} \right) + 1. $

(8)

易知非齐次线性递推式(8) 的特解为1.

齐次线性递推式f(n)=8f(n-1)-8f(n-2) 的通解为

$ f\left( n \right) = {c_1}{\left( {4 + 2\sqrt 2 } \right)^n} + {c_2}{\left( {4-2\sqrt 2 } \right)^n}. $

(9)

由图 6知f(1)=7.由式(3) 知，

f(2)=2a(1)+2c(1)+1.

由图 7知a(1)=8.

由图 8知c(1)=12.所以，

f(2)=2×8+2×12+1=41.

因此, 线性递推式(8) 满足f(1)=7, f(2)=41的解为

$ f\left( n \right) = {2^{n-2}} \cdot {\left( {2 + \sqrt 2 } \right)^{n + 1}} + {2^{n-2}} \cdot {\left( {2-\sqrt 2 } \right)^{n + 1}} + 1. $

定理2 g(n)表示2-nT₂图的完美匹配数目, 则g(n)=3ⁿ+1.

证明 2-nT₂图是2边连通3正则图, 显然存在完美匹配.为求g(n), 先定义G₆图.删除2-nT₂图的边u₁₁u₁₃得到的图记为G₆, 如图 9所示.

显然，G₆图存在完美匹配，其完美匹配数记为d(n).G₆图的完美匹配按饱和顶点u₁₁的情况可分以下3种情形求得:

情形1 由d(n)的定义, G₆图包含边u₁₁v₁₁, u₁₂v₁₂, u₁₃v₁₃的完美匹配数为d(n-1).

情形2 由d(n)的定义, G₆图包含边u₁₁v₁₁, u₁₂u₁₃, v₁₂v₁₃的完美匹配数为d(n-1).

情形3 由d(n)的定义, G₆图包含边u₁₁u₁₂, v₁₁v₁₂, u₁₃v₁₃的完美匹配数为d(n-1).

综上所述, d(n)=3d(n-1)=3^n-1·d(1)，易知

$ d\left( 1 \right) = 3, 所以d\left( n \right) = {3^n}. $

(10)

2-nT₂图的完美匹配按饱和顶点u₁₁可分以下4种情形求得:

情形1 2-nT₂图的完美匹配包含边u₁₁u₁₃, 则其必包含边u_i2v_i2(i=1, 2, …, n), v_i1u_i+11, v_i3u_i+13(i=1, 2, …, n-1), v_n1v_n3.所以2-nT₂图包含边u₁₁u₁₃的完美匹配恰有一个.

情形2 由d(n)的定义, 2-nT₂图包含边u₁₁u₁₂, v₁₁v₁₂, u₁₃v₁₃的完美匹配数为d(n-1).

情形3 由d(n)的定义, 2-nT₂图包含边u₁₁v₁₁, u₁₂v₁₂, u₁₃v₁₃的完美匹配数为d(n-1).

情形4 由d(n)的定义, 2-nT₂图包含边u₁₁v₁₁, u₁₂u₁₃, v₁₂v₁₃的完美匹配数为d(n-1).

综上所述,

$ g\left( n \right) = 3d\left( {n-1} \right) + 1. $

(11)

由式(10) 和(11), 得g(n)=3ⁿ+1.