几类特殊图的完美匹配的计数

doi:10.12677/PM.2022.121004

期刊菜单

几类特殊图的完美匹配的计数
The Counting of Perfect Matchings on Some Special Graphs

DOI: 10.12677/PM.2022.121004, PDF, HTML, XML, 下载: 305 浏览: 510 国家自然科学基金支持
作者: 杨思齐^*, 边红^#, 魏丽娜：新疆师范大学，数学科学学院，新疆乌鲁木齐；于海征：新疆大学，数学与系统科学学院，新疆乌鲁木齐
关键词: 完美匹配；分类；递推关系式；通解；Perfect Matching； Classification； Recursive Relation； General Solution

摘要: 图的完美匹配的计数问题已经被证实是NP-困难问题，因此想要得到一般图的完美匹配数是非常困难的。根据图中饱和某个顶点的完美匹配进行分类讨论，得到图的相应完美匹配数的递推关系式，通过求出递推关系式的通解，从而求出图的完美匹配数，是一种有效计算图的完美匹配数的方法。而对于一些直接利用饱和某个顶点进行分类讨论求解不出来的图类，则可以通过对图进行合适的变换得到相应的变换图，再利用饱和某个顶点，对两个图的完美匹配进行分类讨论，从而得到两组有关联的完美匹配数的递推关系式，间接求出图的完美匹配数。本文利用上述方法给出了几类特殊图中完美匹配数的递推公式。

Abstract: The counting problem of perfect matchings of graphs has been confirmed to be NP-hard and therefore obtaining the number of perfect matchings of general graph is very difficult. According to the perfect matching that saturates a certain vertex in graph, we can give the classification of perfect matchings of graphs, and obtain the recursive relation for the corresponding number of perfect matchings of the graph. It is an effectively method to calculate the number of perfect matchings of graph by presenting the general solution of the recursive relation. And for some graphs that cannot be solved by using above method, by constructing transformation graph, we can give the recursive relations of the number of perfect matchings of original graph and corresponding transformation graph. In this paper, we give the recursive formulae for the number of perfect matchings in some special classes of graphs, and present the exact number of perfect matchings of these special graphs.

文章引用：杨思齐, 边红, 于海征, 魏丽娜. 几类特殊图的完美匹配的计数[J]. 理论数学, 2022, 12(1): 27-35. https://doi.org/10.12677/PM.2022.121004

1. 引言

图的完美匹配计数理论具有较强的物理、化学背景，其研究结果在多个领域都有广泛应用 [1] [2] [3] [4]。Valiant在1979年证明了图的完美匹配的计数问题是NP-困难问题，因此想要得到一般图的完美匹配的计数公式是非常困难的 [5]。目前，已有一些文献对特殊图类的完美匹配数作了相关的研究 [6] - [11]。本文利用分类、递推、消元的方法给出了四类特殊图的完美匹配的计数公式。

定义1 [1] 若图G有一个1-正则生成子图，则称该生成子图称为图G的完美匹配。

定义2 [1] 设图G是一个有完美匹配的图，若图G的两个完美匹配 $M_{1}$ 和 $M_{2}$ 中有一条边不同，则称 $M_{1}$ 和 $M_{2}$ 是G两个不同的完美匹配。

定义3 设四个点的三角格子图 $T_{r}^{i}$ 的顶点集合为 $V (T_{r}^{i}) = {u_{i 1}, u_{i 2}, u_{i 3}, u_{i 4}} (i = 1, 2, 3, \dots, n)$ ，分别连接 $T_{r}^{i}$ 和 $T_{r}^{i + 1}$ 的顶点 $u_{i 2}$ 和 $u_{i + 1,1}$ 及 $u_{i 3}$ 和 $u_{i + 1, 4} (i = 1, 2, 3, \dots, n - 1)$ 所得的图记为 $2 - n T_{r}$ ，如图1所示。

定义4 图G中的每一条边用 $P_{3}$ 替换得到的变换图称为图G的剖分图，记为 $S (G)$ 。 $K_{3}$ 为三个点的完全图。设 $K_{3}$ 剖分图的顶点集合为 $V (S {(K_{3})}^{i}) = {u_{i 1}, u_{i 2}, u_{i 3}, u_{i 4}, u_{i 5}, u_{i 6}} (i = 1, 2, 3, \dots, n)$ ，分别连接 $S {(K_{3})}^{i}$ 和 $S {(K_{3})}^{i + 1}$ 的顶点 $u_{i 1}$ 和 $u_{i + 1,1}$ 及 $u_{i 3}$ 和 $u_{i + 1, 5} (i = 1, 2, 3, \dots, n - 1)$ 所得的图记为 $2 - n S (K_{3})$ ，如图2所示。

定义5 设 $F_{6}$ 为在六个点 ${u_{i 1}, u_{i 2}, u_{i 3}, u_{i 4}, u_{i 5}, u_{i 6}} (i = 1, 2, 3, \dots, n)$ 的圈中，连接 $u_{i 1}$ 和 $u_{i 4}$ ， $u_{i 2}$ 和 $u_{i 5}$ ， $u_{i 3}$ 和 $u_{i 6}$ 得到的图。将 $F_{6}^{i}$ 中的两个顶点 $u_{i 2}$ 和 $u_{i 3}$ 分别连接 $F_{6}^{i + 1}$ 中 $u_{i + 1,6}$ 和 $u_{i + 1, 5} (i = 1, 2, 3, \dots, n - 1)$ ，得到的分图记为 $4 - n F_{6}$ ，如图3所示。

Figure 1. $2 - n T_{r}$

图1. $2 - n T_{r}$

Figure 2. $2 - n S ( K 3 )$

图2. $2 - n S ( K 3 )$

定义6 $K_{4}$ 为四个点的完全图。设 $K_{4}$ 的顶点集合为 $V {(K_{4})}^{i} = {u_{i 1}, u_{i 2}, u_{i 3}, u_{i 4}} (i = 1, 2, 3, \dots, n)$ ，分别连接 $K_{4}^{i}$ 和 $K_{4}^{i + 1}$ 的顶点 $u_{i 1}$ 和 $u_{i + 1,1}$ ， $u_{i 4}$ 和 $u_{i + 1,2}$ 及 $u_{i 3}$ 和 $u_{i + 1,3}$ $(i = 1, 2, 3, \dots, n - 1)$ 所得的图记为 $3 - n K_{4}$ ，如图4所示。

Figure 3. $4 - n F_{6}$

图3. $4 - n F_{6}$

Figure 4. $3 - n K_{4}$

图4. $3 - n K_{4}$

2. 引理及主要结论

定理1 设图 $2 - n T_{r}$ 的完美匹配数为 $α (n)$ ，则 $α (n) = 2^{n}$ 。

证明图 $2 - n T_{r}$ 显然存在完美匹配。设图 $2 - n T_{r}$ 完美匹配的集合为P，图 $2 - n T_{r}$ 含 $u_{11} u_{12}$ 、 $u_{11} u_{13}$ 、 $u_{11} u_{14}$ 的完美匹配集合分别为 $P_{1}$ 、 $P_{2}$ 、 $P_{3}$ ，则 $P_{1} \cap P_{2} \cap P_{3} = \emptyset$ ， $P = P_{1} \cup P_{2} \cup P_{3}$ ，故 $α (n) = | P | = | P_{1} | + | P_{2} | + | P_{3} |$ 。

$P_{1}$ 中含边 $u_{11} u_{12}$ 和 $u_{13} u_{14}$ 。观察图 $2 - n T_{r}$ 可知没有包含边 $u_{11} u_{13}$ 的完美匹配。 $P_{3}$ 中含边 $u_{11} u_{14}$ 和 $u_{12} u_{13}$ 。由 $α (n)$ 的定义， $| P_{1} | = | P_{3} | = α (n - 1)$ ， $| P_{2} | = 0$ 。

所以 $α (n) = 2 α (n - 1) = 2^{n - 1} α (1) .$

Figure 5. Two perfect matchings of $α (1)$ (bold edges represent the matching edges)

图5. $α (1)$ 中的两个完美匹配(粗边代表匹配边)

由图5知， $α (1) = 2$ ，故 $α (n) = 2^{n}$ 。

定理证毕。

定理2 设图 $2 - n S (K_{3})$ 的完美匹配数为 $η (n)$ ，则

$η (n) = \frac{5 + \sqrt{5}}{10} \cdot {(1 + \sqrt{5})}^{n} + \frac{5 - \sqrt{5}}{10} \cdot {(1 - \sqrt{5})}^{n} .$

证明图 $2 - n S (K_{3})$ 显然存在完美匹配。设图 $2 - n S (K_{3})$ 完美匹配的集合为P，图 $2 - n S (K_{3})$ 含 $u_{15} u_{14}$ 、 $u_{15} u_{16}$ 的完美匹配集合分别为 $P_{1}$ 、 $P_{2}$ ，则 $P_{1} \cap P_{2} = \emptyset$ ， $P = P_{1} \cup P_{2}$ ，故 $η (n) = | P | = | P_{1} | + | P_{2} |$ 。

$P_{1}$ 划分为三类。 $P_{1}$ 中含 $u_{15} u_{14}$ 、 $u_{12} u_{13}$ 、 $u_{11} u_{16}$ 的完美匹配的集合记为 $P_{1}^{1}$ ； $P_{1}$ 中含 $u_{15} u_{14}$ 、 $u_{16} u_{12}$ 、 $u_{13} u_{25}$ 、 $u_{11} u_{21}$ 、 $u_{22} u_{26}$ 、 $u_{23} u_{24}$ 的完美匹配的集合记为 $P_{1}^{2}$ ； $P_{1}$ 中含 $u_{15} u_{14}$ 、 $u_{16} u_{12}$ 、 $u_{13} u_{25}$ 、 $u_{11} u_{21}$ 、 $u_{22} u_{23}$ 、 $u_{24} u_{26}$ 的完美匹配的集合记为 $P_{1}^{3}$ 。则 $P_{1}^{1} \cap P_{1}^{2} \cap P_{1}^{3} = \emptyset$ ， $P_{1} = P_{1}^{1} \cup P_{1}^{2} \cup P_{1}^{3}$ ，由 $η (n)$ 的定义知， $| P_{1}^{1} | = η (n - 1)$ ， $| P_{1}^{2} | = | P_{1}^{3} | = η (n - 2)$ 。 $| P_{1} | = η (n - 1) + 2 η (n - 2)$ 。

$P_{2}$ 划分为三类。 $P_{2}$ 中含 $u_{15} u_{16}$ 、 $u_{13} u_{14}$ 、 $u_{11} u_{12}$ 的完美匹配的集合记为 $P_{2}^{1}$ ； $P_{2}$ 中含 $u_{15} u_{16}$ 、 $u_{12} u_{14}$ 、 $u_{13} u_{25}$ 、 $u_{11} u_{21}$ 、 $u_{22} u_{26}$ 、 $u_{23} u_{24}$ 的完美匹配的集合记为 $P_{2}^{2}$ ； $P_{2}$ 中含 $u_{15} u_{16}$ 、 $u_{12} u_{14}$ 、 $u_{13} u_{25}$ 、 $u_{11} u_{21}$ 、 $u_{22} u_{23}$ 、 $u_{24} u_{26}$ 的完美匹配的集合记为 $P_{2}^{3}$ 。则 $P_{1}^{1} \cap P_{1}^{2} \cap P_{1}^{3} = \emptyset$ ， $P_{2} = P_{1}^{1} \cup P_{1}^{2} \cup P_{1}^{3}$ ，由 $η (n)$ 的定义知， $| P_{2}^{1} | = η (n - 1)$ ， $| P_{2}^{2} | = | P_{2}^{3} | = η (n - 2)$ 。 $| P_{2} | = η (n - 1) + 2 η (n - 2)$ 。

Figure 6. (a) Two perfect matchings of $η (1)$ (bold edges represent the matching edges); (b) Eight perfect matchings of $η (2)$ (bold edges represent the matching edges)

图6. (a) $η (1)$ 中的两个完美匹配(粗边代表匹配边)；(b) $η (2)$ 中的八个完美匹配(粗边代表匹配边)

综上所述

$η (n) = 2 η (n - 1) + 4 η (n - 2) .$ (1)

递推式(1)的递推方程为 $x^{2} - 2 x - 4 = 0$ ，特征根为 $1 \pm \sqrt{5}$ 。

递推式(1)的通解为 $η (n) = c_{1} {(1 + \sqrt{5})}^{n} + c_{2} {(1 - \sqrt{5})}^{n}$ ， $c_{1}$ 、 $c_{2}$ 为待定常数。

由图6知， $η (1) = 2$ ， $η (2) = 8$ 。

故

$η (n) = \frac{5 + \sqrt{5}}{10} \cdot {(1 + \sqrt{5})}^{n} + \frac{5 - \sqrt{5}}{10} \cdot {(1 - \sqrt{5})}^{n} .$

定理证毕。

定理3 设图 $4 - n F_{6}$ 的完美匹配数为 $β (n)$ ，则

$β (n) = \frac{3 + \sqrt{3}}{6} \cdot {(4 + 2 \sqrt{3})}^{n} + \frac{3 - \sqrt{3}}{6} \cdot {(4 - 2 \sqrt{3})}^{n} .$

证明图 $4 - n F_{6}$ 显然存在完美匹配。欲求 $β (n)$ 的解析式，先定义图 $G_{1}$ ，并求出它的完美匹配数的递推式。把路 $a b$ 的端点a、b分别与图 $4 - n F_{6}$ 的顶点 $u_{15}$ 、 $u_{16}$ 连两条边，得到的图记为 $G_{1}$ ，如图7所示。

Figure 7. $G_{1}$

图7. $G_{1}$

图 $G_{1}$ 显然存在完美匹配。 $γ (n)$ 表示图 $G_{1}$ 的完美匹配数，设图 $G_{1}$ 完美匹配的集合为P，图 $G_{1}$ 含 $a b$ 、 $a u_{16}$ 、 $a u_{15}$ 的完美匹配集合分别为 $P_{1}$ 、 $P_{2}$ 、 $P_{3}$ ，则 $P_{1} \cap P_{2} \cap P_{3} = \emptyset$ ， $P = P_{1} \cup P_{2} \cup P_{3}$ ，故 $η (n) = | P | = | P_{1} | + | P_{2} | + | P_{3} |$ 。

$P_{1}$ 中含 $a b$ ，由 $β (n)$ 的定义知， $| P_{1} | = β (n)$ 。

$P_{2}$ 划分为两类。 $P_{2}$ 中含 $a u_{16}$ 、 $b u_{15}$ 、 $u_{11} u_{14}$ 的完美匹配的集合记为 $P_{2}^{1}$ ； $P_{2}$ 中含 $a u_{16}$ 、 $b u_{15}$ 、 $u_{11} u_{12}$ 、 $u_{13} u_{14}$ 的完美匹配的集合记为 $P_{2}^{2}$ 。则 $P_{2}^{1} \cap P_{2}^{2} = \emptyset$ ， $P_{2} = P_{2}^{1} \cup P_{2}^{2}$ ，由 $γ (n)$ 和 $β (n)$ 的定义知， $| P_{2}^{1} | = γ (n - 1)$ ， $| P_{2}^{2} | = β (n - 1)$ 。 $| P_{2} | = γ (n - 1) + β (n - 1)$ 。

$P_{3}$ 划分为两类。 $P_{3}$ 中含 $a u_{15}$ 、 $b u_{16}$ 、 $u_{11} u_{14}$ 的完美匹配的集合记为 $P_{3}^{1}$ ； $P_{3}$ 中含 $a u_{15}$ 、 $b u_{16}$ 、 $u_{11} u_{12}$ 、 $u_{13} u_{14}$ 的完美匹配的集合记为 $P_{3}^{2}$ 。则 $P_{3}^{1} \cap P_{3}^{2} = \emptyset$ ， $P_{3} = P_{3}^{1} \cup P_{3}^{2}$ ，由 $γ (n)$ 和 $β (n)$ 的定义知， $| P_{3}^{1} | = γ (n - 1)$ ， $| P_{3}^{2} | = β (n - 1)$ 。 $| P_{3} | = γ (n - 1) + β (n - 1)$ 。

故

$γ (n) = β (n) + 2 γ (n - 1) + 2 β (n - 1) .$ (2)

再求 $β (n)$ 的递推式。设图 $4 - n F_{6}$ 完美匹配的集合为W，图 $4 - n F_{6}$ 含 $u_{16} u_{11}$ 、 $u_{16} u_{13}$ 、 $u_{16} u_{15}$ 的完美匹配集合分别为 $W_{1}$ 、 $W_{2}$ 、 $W_{3}$ ，则 $W_{1} \cap W_{2} \cap W_{3} = \emptyset$ ， $W = W_{1} \cup W_{2} \cup W_{3}$ ，故 $β (n) = | W | = | W_{1} | + | W_{2} | + | W_{3} |$ 。

$W_{1}$ 划分为两类。 $W_{1}$ 中含 $u_{16} u_{11}$ 、 $u_{14} u_{15}$ 的完美匹配的集合记为 $W_{1}^{1}$ ； $W_{1}$ 中含 $u_{16} u_{11}$ 、 $u_{12} u_{15}$ 、 $u_{13} u_{14}$ 的完美匹配的集合记为 $W_{1}^{2}$ 。则 $W_{1}^{1} \cap W_{1}^{2} = \emptyset$ ， $W_{1} = W_{1}^{1} \cup W_{1}^{2}$ ，由 $γ (n)$ 和 $β (n)$ 的定义知， $| W_{1}^{1} | = γ (n - 1)$ ， $| W_{1}^{2} | = β (n - 1)$ 。 $| W_{1} | = γ (n - 1) + β (n - 1)$ 。

$W_{2}$ 划分为两类。 $W_{2}$ 中含 $u_{16} u_{13}$ 、 $u_{11} u_{12}$ 、 $u_{14} u_{15}$ 的完美匹配的集合记为 $W_{2}^{1}$ ； $W_{2}$ 中含 $u_{16} u_{13}$ 、 $u_{11} u_{14}$ 、 $u_{12} u_{15}$ 的完美匹配的集合记为 $W_{2}^{2}$ 。则 $W_{2}^{1} \cap W_{2}^{2} = \emptyset$ ， $W_{2} = W_{2}^{1} \cup W_{2}^{2}$ ，由 $β (n)$ 的定义知， $| W_{2}^{1} | = | W_{2}^{2} | = β (n - 1)$ ， $| W_{2} | = 2 β (n - 1)$ 。

$W_{3}$ 划分为两类。 $W_{3}$ 中含 $u_{16} u_{15}$ 、 $u_{11} u_{14}$ 的完美匹配的集合记为 $W_{3}^{1}$ ； $W_{1}$ 中含 $u_{16} u_{15}$ 、 $u_{11} u_{12}$ 、 $u_{13} u_{14}$ 的完美匹配的集合记为 $W_{3}^{2}$ 。则 $W_{3}^{1} \cap W_{3}^{2} = \emptyset$ ， $W_{3} = W_{3}^{1} \cup W_{3}^{2}$ ，由 $γ (n)$ 和 $β (n)$ 的定义知， $| W_{3}^{1} | = γ (n - 1)$ ， $| W_{3}^{2} | = β (n - 1)$ ， $| W_{3} | = γ (n - 1) + β (n - 1)$ 。

Figure 8. (a) Six perfect matchings of $β (1)$ (bold edges represent the matching edges); (b) Ten perfect matchings of $γ (1)$ (bold edges represent the matching edges)

图8. (a) $β (1)$ 中的六个完美匹配(粗边代表匹配边)；(b) $γ (1)$ 中的十个完美匹配(粗边代表匹配边)

综上所述

$β (n) = 4 β (n - 1) + 2 γ (n - 1) .$ (3)

由(2)得

$γ (n - 1) = β (n - 1) + 2 γ (n - 2) + 2 β (n - 2) .$ (4)

将(4)代入(3)得

$β (n) = 6 β (n - 1) + 4 β (n - 2) + 4 γ (n - 2) .$ (5)

由(3)得

$β (n - 1) = 4 β (n - 2) + 2 γ (n - 2) .$ (6)

将(6)代入(5)得

$β (n) = 8 β (n - 1) - 4 β (n - 2) .$ (7)

递推式(7)的递推方程为 $x^{2} - 8 x + 4 = 0$ ，特征根为 $4 \pm 2 \sqrt{5}$ 。

递推式(7)的通解为 $β (n) = c_{1} {(4 + 2 \sqrt{5})}^{n} + c_{2} {(4 - 2 \sqrt{5})}^{n}$ ， $c_{1}$ 、 $c_{2}$ 为待定常数。

由图8知， $β (1) = 6, γ (1) = 10$ 。

所以由(3)得， $β (2) = 44$ 。

故

$β (n) = \frac{3 + \sqrt{3}}{6} \cdot {(4 + 2 \sqrt{3})}^{n} + \frac{3 - \sqrt{3}}{6} \cdot {(4 - 2 \sqrt{3})}^{n} .$

定理证毕。

定理4 设图 $3 - n K_{4}$ 的完美匹配数为 $ω (n)$ ，则

$ω (n) = 4 ω (n - 1) - ω (n - 3) .$

其中： $ω (1) = 3$ ， $ω (2) = 12$ ， $ω (3) = 47$ 。

证明图 $3 - n K_{4}$ 显然存在完美匹配。欲求 $ω (n)$ 的解析式，先定义图 $G_{2}$ ，并求出它的完美匹配数的递推式。把路 $a b$ 的端点a、b分别与图 $3 - n K_{4}$ 的顶点 $u_{11}$ 、 $u_{12}$ 连一条边，得到的图记为 $G_{2}$ ，如图9所示。再定义图 $G_{3}$ 。把路 $a b$ 的端点a、b分别与图 $3 - n K_{4}$ 的顶点 $u_{13}$ 、 $u_{12}$ 连一条边，得到的图记为 $G_{3}$ ，如图10所示。

Figure 9. $G_{2}$

图9. $G_{2}$

图 $G_{2}$ 存在完美匹配， $ψ (n)$ 表示图 $G_{2}$ 的完美匹配数。图 $G_{3}$ 也存在完美匹配， $π (n)$ 表示图 $G_{3}$ 的完美匹配数。显然， $ψ (n) = π (n)$ 。设图 $G_{2}$ 完美匹配的集合为P，图 $G_{2}$ 含 $a b$ 、 $a u_{11}$ 的完美匹配集合分别为 $P_{1}$ 、 $P_{2}$ ，则 $P_{1} \cap P_{2} = \emptyset$ ， $P = P_{1} \cup P_{2}$ ，故 $ψ (n) = | P | = | P_{1} | + | P_{2} |$ 。

$P_{1}$ 中含 $a b$ ，由 $ω (n)$ 的定义知， $| P_{1} | = ω (n)$ 。

$P_{2}$ 中含 $a u_{11}$ 、 $b u_{12}$ ，由 $π (n)$ 和 $ψ (n)$ 的定义知， $| P_{2} | = π (n - 1) = ψ (n - 1)$ 。

故

$ψ (n) = ω (n) + ψ (n - 1) .$ (8)

再求 $ω (n)$ 的递推式。设图 $3 - n K_{4}$ 完美匹配的集合为W，图 $3 - n K_{4}$ 含 $u_{12} u_{11}$ 、 $u_{12} u_{13}$ 、 $u_{12} u_{14}$ 的完美匹配集合分别为 $W_{1}$ 、 $W_{2}$ 、 $W_{3}$ ，则 $W_{1} \cap W_{2} \cap W_{3} = \emptyset$ ， $W = W_{1} \cup W_{2} \cup W_{3}$ ，故 $ω (n) = | W | = | W_{1} | + | W_{2} | + | W_{3} |$ 。

$W_{1}$ 中含 $u_{12} u_{11}$ 的完美匹配的集合记为 $W_{1}$ 。 $| W_{1} | = π (n - 1) = ψ (n - 1)$ 。

$W_{2}$ 中含 $u_{12} u_{13}$ 的完美匹配的集合记为 $W_{2}$ 。 $| W_{2} | = ψ (n - 1)$ 。

Figure 10. $G_{3}$

图10. $G_{3}$

$W_{3}$ 划分为两类。 $W_{3}$ 中含 $u_{12} u_{14}$ 、 $u_{11} u_{13}$ 的完美匹配的集合记为 $W_{3}^{1}$ ； $W_{1}$ 中含 $u_{12} u_{14}$ 、 $u_{11} u_{21}$ 、 $u_{13} u_{23}$ 、 $u_{22} u_{24}$ 的完美匹配的集合记为 $W_{3}^{2}$ 。则 $W_{3}^{1} \cap W_{3}^{2} = \emptyset$ ， $W_{3} = W_{3}^{1} \cup W_{3}^{2}$ ，由 $ω (n)$ 的定义知， $| W_{3}^{1} | = ω (n - 1)$ ， $| W_{3}^{2} | = ω (n - 2)$ 。 $| W_{3} | = ω (n - 1) + ω (n - 2)$ 。

Figure 11. (a)Three perfect matchings of $ω (1)$ (bold edges represent the matching edges); (b) Twelve perfect matchings of $ω (2)$ (bold edges represent the matching edges); (c) Four perfect matchings of $ψ (1)$ (bold edges represent the matching edges)

图11. (a) $ω (1)$ 的三个完美匹配(粗边代表匹配边)；(b) $ω (2)$ 的十二个完美匹配(粗边代表匹配边)；(c) $ψ (1)$ 的四个完美匹配(粗边代表匹配边)

综上所述

$ω (n) = 2 ψ (n - 1) + ω (n - 1) + ω (n - 2) .$ (9)

由(8)得

$ψ (n - 1) = ω (n - 1) + ψ (n - 2) .$ (10)

将(10)代入(9)得

$ω (n) = 3 ω (n - 1) + 2 ψ (n - 2) + ω (n - 2) .$ (11)

由(9)得

$ω (n - 1) = 2 ψ (n - 2) + ω (n - 2) + ω (n - 3) .$ (12)

将(12)代入(11)得

$ω (n) = 4 ω (n - 1) - ω (n - 3) .$ (13)

由图11知， $ω (1) = 3$ ， $ω (2) = 12$ ， $ψ (1) = 4$ 。

所以由(11)得， $ω (3) = 47$ 。

故

$ω (n) = 4 ω (n - 1) - ω (n - 3) .$

其中： $ω (1) = 3$ ， $ω (2) = 12$ ， $ω (3) = 47$ 。

定理证毕。

基金项目

国家自然科学基金项目(11761070, 61662079)；2021年新疆维吾尔自治区自然基金联合项目(2021D01C078)；2020年新疆师范大学一流专业、一流课程项目资助。

NOTES

^*第一作者。

^#通讯作者。

参考文献

[1]	Cyvin, S.J. and Gutman, I. (1988) Kekulé Structures in Benzennoid Hydrocarbons. Springer Pres, Berlin. https://doi.org/10.1007/978-3-662-00892-8
[2]	Ciucu, M. (1997) Enumeration of Perfect Matchings in Graphs with Reflective Symmetry. Journal of Combinatorial Theory, Series A, 77, 87-97. https://doi.org/10.1006/jcta.1996.2725
[3]	Jockusch, W. (1994) Perfect Mathings and Perfect Squares. Journal of Combinatorial Theory, Series A, 67, 100-115. https://doi.org/10.1016/0097-3165(94)90006-X
[4]	Lovbsz, L. and Plummer, M. (1986) Matching Theory. North-Holand Press, New York.
[5]	Valiant, L.G. (1979) The Complexsity of Computing the Permanent. Theoretical Compute Science, 8, 189-201. https://doi.org/10.1016/0304-3975(79)90044-6
[6]	唐保祥, 任韩. 2类图完美匹配数按匹配顶点分类的递推求法[J]. 吉林大学学报(理学版), 2020, 58(2): 309-313.
[7]	唐保祥, 任韩. 图和完美匹配的计数[J]. 吉林大学学报(理学版), 2020, 58(4): 859-863.
[8]	唐保祥, 任韩. 2类图完美对集数的计算公式[J]. 西南师范大学学报(自然科学版), 2020, 45(10): 13-15.
[9]	唐保祥, 任韩. 2类特殊图的完美对集数的分类递推求法[J]. 南京师大学报(自然科学版), 2021, 44(1): 1-5.
[10]	唐保祥, 任韩. 两类图完美对集数的分类递推计算[J]. 昆明理工大学学报(自然科学版), 2021, 46(2): 135-139.
[11]	Wei, S.L., Chen, N.D., Ke, X.L., Hao, G.L., Huang, J.W., Tang, N.S. (2021) Perfect Matchings in Random Octagonal Chain Graphs. Journal of Mathematics, 2021, Article ID 2324632. https://doi.org/10.1155/2021/2324632

为你推荐

友情链接