4类图完美匹配数目的递推求法

递推算法详解-回复什么是递推算法？递推算法，也称为迭代算法，是一种解决问题的数学或计算方法。

它通过定义初始条件和递推公式来计算求解一个问题的过程，并将问题的规模逐步缩小，直至达到基本情况可以被直接求解。

递推算法常常在计算机科学、数学、物理学等领域中被广泛应用。

递推算法的基本思想是通过已知结果计算未知结果，并逐步推导出整体的解。

它通常涉及将问题划分为一系列相互依赖的子问题，并根据子问题的解来推导出更大规模问题的解。

递推算法的核心是找到递归公式或迭代关系，通过不断迭代计算的方式逐步逼近最终解。

递推算法的特点是具有清晰的步骤和明确的终止条件。

它的执行过程可以看作是一系列有序的操作步骤，每一步都在上一步的基础上进行计算，直到达到终止条件为止。

递推算法通常使用迭代结构或递归函数实现，具有高效、可靠、易于理解的优点。

递推算法在实际问题中的应用非常广泛。

它可以用于解决数列求和、排列组合、动态规划、图算法等各种问题。

在数学中，斐波那契数列就是一个常见的递推数列，其递推公式为F(n) = F(n-1) + F(n-2)，然后给定初始条件F(0) = 0，F(1) = 1，通过递推公式可以依次求解出每一个数的值。

递推算法的步骤可以总结为以下四个：1. 找到基本情况：递推算法的终止条件是基本问题的解，请确定问题的边界。

2. 设计递归公式：根据问题的性质确定递归公式或迭代关系，以便将问题拆解为更小的子问题。

3. 确定初始条件：确定问题的初始条件或起始状态。

4. 实施递推：通过递推公式或迭代关系将问题规模不断缩小，直到达到基本情况，然后计算基本情况下的解。

对于求解递归问题，递推算法通常具有较高的时间复杂度。

这是因为在递推过程中，需要重复计算许多中间值，并且递归函数的调用过程会导致额外的函数调用开销。

为了提高执行效率，可以使用记忆化搜索等技术来优化递推算法。

总结起来，递推算法是一种通过定义初始条件和递推公式来计算求解问题的方法。

五种典型的递推关系1.Fibonacci数列在所有的递推关系中，Fibonacci数列应该是最为⼤家所熟悉的。

在最基础的程序设计语⾔Logo 语⾔中，就有很多这类的题⽬。

⽽在较为复杂的Basic、Pascal、C语⾔中，Fibonacci数列类的题⽬因为解法相对容易⼀些，逐渐退出了竞赛的舞台。

可是这不等于说Fibonacci数列没有研究价值，恰恰相反，⼀些此类的题⽬还是能给我们⼀定的启发的。

数列的代表问题是由意⼤利著名数学家Fibonacci于1202年提出的“兔⼦繁殖问题”(⼜Fibonacci数列称“Fibonacci问题”)。

问题的提出：有雌雄⼀对兔⼦，假定过两个⽉便可繁殖雌雄各⼀的⼀对⼩兔⼦。

问过n个⽉后共问题有多少对兔⼦？解：设满x个⽉共有兔⼦Fx对，其中当⽉新⽣的兔⼦数⽬为Nx对。

第x-1个⽉留下的兔⼦数 解⽬设为Fx-1对。

则：Fx=Nx+ Fx-1 Nx=Fx-2 (即第x-2个⽉的所有兔⼦到第x个⽉都有繁殖能⼒） ∴ Fx=Fx-1+Fx-2 边界条件：F0=0，F1=1由上⾯的递推关系可依次得到： F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，……。

数列常出现在⽐较简单的组合计数问题中，例如以前的竞赛中出现的“⾻牌覆盖”问Fabonacci数列题。

在优选法中，Fibonacci数列的⽤处也得到了较好的体现。

2.Hanoi塔问题问题的提出：Hanoi塔由n个⼤⼩不同的圆盘和三根⽊柱a,b,c组成。

开始时，这n个圆盘由⼤到问题⼩依次套在a柱上，如图3-11所⽰。

要求把a柱上n个圆盘按下述规则移到c柱上： (1)⼀次只能移⼀个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许⼤盘压⼩盘。

问将这n个盘⼦从a柱移动到c柱上，总计需要移动多少个盘次？解：设hn为n个盘⼦从a柱移到c柱所需移动的盘次。

显然，当n=1时，只需把a 柱上的盘⼦直接移动到c柱就可以了，故h1=1。

网格问题的基本方法--递推引言网格问题是计算机科学中一个常见且重要的问题。

这类问题通常涉及在一个网格中寻找特定目标或满足特定条件的路径、组合或排列。

递推是解决网格问题的一种基本方法，它通过将问题分解为子问题，并利用子问题的解来构建整体解决方案。

递推的基本原理递推的基本原理是将大问题拆解为一系列相对较小的子问题，然后通过求解子问题逐步构建出最终解决方案。

在网格问题中，递推可以通过以下步骤实现：1. 定义子问题：将大网格划分为小网格，通常是将一个网格划分为上、下、左、右四个相邻的子网格。

2. 定义初始条件：确定子问题的边界条件和初始状态，例如起始位置和目标位置。

3. 推导递推关系：根据子问题之间的关系，确定如何从一个子问题推导到下一个子问题。

这需要基于问题的特定要求来确定，例如可以是在相邻子网格中移动或改变状态。

4. 求解子问题：使用递归或迭代的方式求解子问题，并记录子问题的解。

5. 组合子问题的解：根据子问题的解，构建出最终的解决方案。

递推在网格问题中的应用递推在网格问题中具有广泛的应用。

以下是一些常见的网格问题及其解决方法：1. 迷宫问题：在一个迷宫中，找到从起点到终点的路径。

可以使用递推来记录每个位置是否可达，并找到从起点到终点的路径。

2. 数独问题：在一个9x9的网格中填入数字，使得每行、每列和每个3x3的子网格中的数字互不相同。

可以使用递推来逐步填充每个格子，直到整个数独被解决。

3. 动态规划问题：在一个网格中寻找最佳路径或组合。

通过定义子问题和递推关系，可以使用动态规划的方法求解。

结论递推是解决网格问题的一种基本方法，通过将问题拆解为子问题并逐步构建解决方案，可以高效地解决各种网格问题。

在实际应用中，可以根据问题的具体要求和特点，灵活运用递推方法来求解网格问题。

递推算法的一般步骤递推算法是一种常用的计算方法，通过已知条件推导出未知结果的一种数学推理过程。

它可以用于解决一些复杂的问题，特别是涉及到递归关系的情况。

递推算法的一般步骤如下：1. 首先，明确问题的递推关系。

递推算法的核心就是通过已知条件推导出未知结果，因此需要通过观察问题的特点，找到问题的递推关系。

这个递推关系可以是一个公式、一个递归函数或者一系列等差、等比数列等。

2. 然后，确定初始条件。

递推算法是从已知条件推导出未知结果的过程，因此需要确定问题的初始条件。

这个初始条件可以是问题中给出的初始值，也可以是手动给定的一些值。

3. 接下来，进行递推计算。

根据问题的递推关系和初始条件，可以开始逐步计算得到未知结果。

递推计算的过程就是反复应用递推关系，将已知的结果代入递推关系中得到新的结果，然后再将新的结果代入递推关系中得到更新的结果，依此类推，直到得到想要的未知结果。

4. 最后，进行结果验证。

得到未知结果后，需要对结果进行验证，确保结果的正确性。

这可以通过与已知条件进行对比、与问题的实际情况进行比较等方法来进行。

如果结果符合要求，即可确认递推算法的正确性。

除了以上步骤，还有一些在使用递推算法时需要注意的问题：1. 递归深度的控制。

递推算法中经常使用递归函数来表达递推关系，但要注意递归的深度，避免出现无限递归的情况。

可以通过设置递归深度的限制条件或者使用迭代方法来避免这种情况的发生。

2. 边界条件的处理。

在确定初始条件时，要考虑问题的边界条件。

边界条件是递推算法中的特殊情况，需要单独处理，以确保算法的正确性。

边界条件可以是问题中给出的某种特殊情况，或者是根据问题的特点手动给定的一些条件。

3. 问题的优化。

在实际应用中，递推算法可能会面临一些效率问题，特别是在处理大规模数据时。

因此，需要对算法进行优化，提高算法的执行效率。

可以通过改进递推关系、使用动态规划等方法来实现问题的优化。

综上所述，递推算法是一种通过已知条件推导出未知结果的计算方法。

排列组合配对问题算法排列组合配对问题，其实就是在已知有一组数据，需要对其进行组合，找到所有可能的组合情况，进而进行配对。

这个问题涉及到了算法和数学的知识，需要进行一定的计算和分析。

在这篇文章中，我将介绍几种常用的排列组合配对算法，并阐述它们的原理及其实现过程。

1. 回溯算法回溯算法是一种递归算法，用于解决包括排列、组合和背包问题等在内的一系列问题。

其核心思想是在搜索进程中遇到了问题，就返回上一级，尝试另一种可能性，直至找到问题的解法。

在排列组合配对问题中，回溯算法可以通过生成子集和排列来求解所有的组合。

生成子集的算法流程：（1）初始化一个数组 arr，表示给定的集合；（2）定义一个函数 dfs(start, subset)，其中 start 表示起始位置，subset 表示当前子集；（3）遍历数组 arr，对于每个数，都有两种可能性：将其加入子集中或不加入子集中。

如果加入，则将该数加入 subset，并递归调用 dfs(start+1, subset)，更新 start 和 subset；如果不加入，则仅递归调用 dfs(start+1, subset)。

生成排列的算法流程：（1）初始化一个数组 arr，表示给定的集合；（2）定义一个函数 dfs(pos)，其中 pos 表示已选择的数的个数；（3）遍历数组 arr，对于每个数，判断其是否已经被选择过。

如果没有，则将该数加入已选择的数中，并递归调用dfs(pos+1)，更新选择的数和 pos；如果已经被选择过，则不进行任何操作。

2. 位运算算法位运算算法与回溯算法类似，也可以用于求解排列和组合问题。

它的优势在于，通过位运算可以直接表示一个集合的子集或排列，而不需要额外的内存空间。

因此，位运算算法可以大大提高运算效率。

生成子集的算法流程：（1）初始化一个集合 set，表示给定的集合；（2）计算出集合 set 的元素个数 n，然后构建一个二进制串，表示从左到右每个元素是否在子集中，其中 0 表示不在，1 表示在。

完全多元图的最大匹配摘要在一个完全多元图的最大匹配中可以包含多少边？我们讨论了一些情况并且得到了结果，然后给出一个新的公式来解决这一类问题。

1.引言假如我们有一家含有一些部门的公司，为了某一项工程需要从不同的部门抽调雇员组合成对工作（即pair work），如果每位雇员仅在一个部门工作，而且只允许参加一次组对，那么我们可以同时拥有多少对雇员？也就是最多可以组成多少对？什么情况下所有的雇员都能被组对？我们用图论来处理此问题。

可以认为，每位雇员相当于一个顶点，已成对的雇员对应于一条边，类似的，将公司的各个部门与代表公司的一个多元图的各个顶点的分割集合相对应。

并且，因为我们允许不同部门中的雇员任意组对，所以我们考虑完全多元图。

最后，我们可以发现顶点不相交的边即对应于不相交的雇员配对。

因而我们的目标就是找到最多的顶点不相交的边集。

我们将利用图论中标准的符号与定义来解决这个问题。

实质上，在这篇论文中，我们是要知道一个完全多元图的最大匹配中含有多少边。

首先我们先看一些已经得到结果的例子。

除了结果是引用的之外，所有的定理都是原创的。

最后，在我们的结论中，提供了一个带有简单公式的定理，可以解决这一类题目。

2.基本定义首先，我们定义图为由被称作顶点的对象组成的一个确定的集合，其中由顶点的无序组合构成的集合被称作边集。

用图表示的话，边可看作是连接顶点的直线部分（见图1）。

如果一个图的顶点集合可以被分成非空的子集，（我们称每一个子集为一个元图），而且在相同的元图里任意两个顶点间无边相连，那么此图就是多元图（见图2）。

进一步，一个完全的多元图是指这样一个多元图，其中不在同一元图的任意两个顶点间均有一条边相连。

表示一个含有n个元图的完全多元图，其中，m i代表图中第我们用符号K m1,m2,m3,···,mni个元图含有的顶点总数。

为了以后的论证方便，不妨设1≤m1≤m2≤···≤m n,即可知第n K2,2,2,12,1(见图3)。

第39卷 第2期西南师范大学学报(自然科学版)2014年2月V o l .39 N o .2 J o u r n a l o f S o u t h w e s t C h i n aN o r m a lU n i v e r s i t y (N a t u r a l S c i e n c eE d i t i o n )F e b .2014文章编号:10005471(2014)2000905几类特殊图完美匹配数目的递推求法①唐保祥1, 任 韩21.天水师范学院数学与统计学院,甘肃天水741001;2.华东师范大学数学系,上海200062摘要:匹配计数理论是图论的核心内容之一,此理论有很强的物理学和化学背景.但是,一般图的完美匹配计数问题却是N P 难问题.用划分㊁求和㊁嵌套递推的方法给出了几类图完美匹配数目的显式表达式.关 键 词:完美匹配;线性递推式;特征方程中图分类号:O 157.5文献标志码:A图的完美匹配计数理论已经在多个领域得到应用,也引起了众多数学家㊁物理学家和化学家的广泛关注[1-5].但是,文献[5]在1979年就证明了:一个图的完美匹配计数问题是N P 难问题.因此,要得到一般图的完美匹配数的计算公式是困难的.目前,已有一些文献对一些特殊图的完美匹配计数作了相关的研究[6-10].本文给出了4类图完美匹配数目的计算公式,所给方法是求解一些特殊图类完美匹配数目的比较有效的方法.定义1 若图G 的两个完美匹配M 1和M 2中有一条边不同,则称M 1和M 2是G 的两个不同的完美匹配.定义2 令两条长为n 的路为P 1=u 1u 2 u n +1,P 2=v 1v 2 v n +1.分别连接路P 1与P 2的顶点u i 与v i (i =1,2, ,n +1),所得到的图称为长为n 的梯子,记为T n .分别连接梯子T n 的顶点u 1与v n +1,v 1与u n +1,所得到的图称为长为n 的莫比乌斯梯子,记为M T n .定理1 令2n 个4圈为C i 14:u i 1u i 2u i 3u i 4u i 1,C i 24:v i 1v i 2v i 3v i 4v i 1(i =1,2, ,n ).分别连接圈C i 14与C i 24的顶点u i 4与v i 4,u i 3与v i 1,u i 2与v i 2,再分别连接圈C i 14和C i +1,14的顶点u i 2与u i +1,4,C i 24和C i +1,24的顶点v i 2与v i +1,4.这样所得到的图记为2n S C 4,如图1所示.φ(n )表示图2n S C 4的完美匹配的数目.则φ(n )=10+31020㊃3+()10n +10-31020㊃3-()10n .图1 图2n S C 4证 显然,图2n S C 4有完美匹配.设图2n S C 4的完美匹配集合为M ,图2n S C 4含边u 11u 14,u 11u 12的完美匹配集合分别为M 1,M 2.则M i ⊆M ,M 1ɘM 2=Ø.故M =M 1ɣM 2,φ(n )=|M |=|M 1|+|M 2|.求|M 1|情形1 M 11⊆M 1.∀M 11ɪM 11,u 11u 14,u 12u 13,v 11v 14,v 12v 13ɪM 11,由φ(n )的定义知,|M 11|=φ(n -1).情形2 M 12⊆M 1.∀M 12ɪM 12,u 11u 14,u 12u 13,v 11v 12,v 14v 13ɪM 12,由φ(n )的定义知,|M 12|=①收稿日期:20121031基金项目:国家自然科学基金(11171114).作者简介:唐保祥(1961),男,甘肃天水人,副教授,主要从事图论和组合数学的研究.φ(n -1).情形3 M 13⊆M 1.∀M 13ɪM 13,u 11u 14,u 13v 11,u 12v 12,v 14v 13ɪM 13,由φ(n )的定义知,|M 13|=φ(n -1).情形4 M 14⊆M 1.∀M 14ɪM 14,u 11u 14,u 13v 11,v 14v 13,u 12u 24,v 12v 24,u 21u 22,u 23v 21,v 23v 22ɪM 14,由φ(n )的定义知,|M 14|=φ(n -2).因为M 1=ɣ4i =1M 1i ,M 1i ɘM 1j =Ø(1ɤi <j ɤ4),故|M 1|=3φ(n -1)+φ(n -2).求|M 2|情形1 M 21⊆M 2.∀M 21ɪM 21,u 11u 12,u 14u 13,v 14v 11,v 13v 12ɪM 21,由φ(n )的定义知,|M 21|=φ(n -1).情形2 M 22⊆M 2.∀M 22ɪM 22,u 11u 12,u 14u 13,v 11v 12,v 14v 13ɪM 22,由φ(n )的定义知,|M 22|=φ(n -1).情形3 M 23⊆M 2.∀M 23ɪM 23,u 11u 12,u 14v 14,u 13v 11,v 12v 13ɪM 23,由φ(n )的定义知,|M 23|=φ(n -1).因为M 2=M 21ɣM 22ɣM 23,M 2i ɘM 2j =Ø(1ɤi <j ɤ3),故|M 2|=3φ(n -1).综上所述,φ(n )=6φ(n -1)+φ(n -2).(1)易知φ(1)=6,φ(2)=37.线性递推式(1)式的特征方程的根为x =3ʃ10.所以(1)式的通解为φ(n )=10+31020㊃3+()10n +10-31020㊃3-()10n .定理2 长为3的莫比乌斯梯子M T i 3的顶点集为V (M T i 3)={u i 1,u i 2,u i 3,u i 4,v i 1,v i 2,v i 3,v i 4}(i =1,2, ,n ).分别连接图M T i 3与M T i +13的顶点v i 2与u i +1,2,v i 3与u i +1,3(i =1,2, ,n -1).这样得到的图记为2n MT 3,如图2所示.σ(n )表示图2n MT 3的完美匹配的数目.则σ(n )=41+44182㊃9+41æèçöø÷2n +41-44182㊃9-41æèçöø÷2n .证 欲求σ(n ),定义一个图G 1,并求其完美匹配的数目.将长为1的路u 1u 2的端点u 1和u 2分别与图2nMT 3的顶点u 12和u 13各连接一条边,得到的图记为G 1,如图3所示.显然图G 1有完美匹配.α(n )表示图G 1的完美匹配的数目.图2 图2n MT 3图3 图G 1 求α(n ).设图G 1的完美匹配的集合为M ,G 1含边u 1u 2,u 1u 12的完美匹配集合分别为M 1,M 2.则M 1ɘM 2=Ø.所以M =M 1ɣM 2,α(n )=|M |=|M 1|+|M 2|.求|M 1| ∀M 1ɪM 1,因为u 1u 2ɪM 1,所以由σ(n )的定义知,|M 1|=σ(n ).求|M 2|情形1 M 21⊆M 2.∀M 21ɪM 21,u 1u 12,u 2u 13,u 11v 11,u 14v 14ɪM 21,由α(n )的定义知,|M 21|=α(n -1).情形2 M 22⊆M 2.∀M 22ɪM 21,u 1u 12,u 2u 13,u 11v 14,u 14v 11ɪM 22,由α(n )的定义知,|M 21|=α(n -1).因为M 2=M 21ɣM 22,M 21ɘM 22=Ø,故|M 2|=2α(n -1).因此α(n )=σ(n )+2α(n -1).(2) 求σ(n ).显然图2n MT 3有完美匹配.设图G 1的完美匹配的集合为M ,2n MT 3含边u 11v 11,u 11v 14,u 11u 12的完美匹配的集合分别为M 1,M 2,M 3.则M =M 1ɣM 2ɣM 3,M i ɘM j =Ø(1ɤi <j ɤ3).所以01西南师范大学学报(自然科学版) h t t p ://x b b jb .s w u .c n 第39卷σ(n )=|M |=|M 1|+|M 2|+|M 3|.求|M 1|情形1 M 11⊆M 1.∀M 11ɪM 11,u 11v 11,u 12v 12,u 13v 13,u 14v 14ɪM 11,由σ(n )的定义知,|M 11|=σ(n -1).情形2 M 12⊆M 1.∀M 12ɪM 12,u 11v 11,u 12v 12,u 13u 14,v 13v 14ɪM 12,由σ(n )的定义知,|M 12|=σ(n -1).情形3 M 13⊆M 1.∀M 13ɪM 13,u 11v 11,u 12u 13,u 14v 14ɪM 13,由α(n )的定义知,|M 13|=α(n -1).因为M 1=M 11ɣM 12ɣM 13,M 1i ɘM 1j =Ø(1ɤi <j ɤ3),故|M 1|=2σ(n -1)+α(n -1).求|M 2|情形1 M 21⊆M 2.∀M 21ɪM 21,u 11v 14,u 12v 12,u 13v 13,u 14v 11ɪM 21,由σ(n )的定义知,|M 21|=σ(n -1).情形2 M 22⊆M 2.∀M 22ɪM 22,u 11v 14,u 13u 12,u 14v 11ɪM 22,由σ(n )的定义知,|M 22|=α(n -1).因为M 2=M 21ɣM 22,M 21ɘM 22=Ø,故|M 2|=σ(n -1)+α(n -1).求|M 3|情形1 M 31⊆M 3.∀M 31ɪM 31,u 11u 12,v 11v 12,u 13v 13,u 14v 14ɪM 31,由σ(n )的定义知,|M 31|=σ(n -1).情形2 M 32⊆M 3.∀M 32ɪM 32,u 11u 12,u 13u 14,v 11v 12,v 13v 14ɪM 32,由σ(n )的定义知,|M 31|=σ(n -1).因为M 3=M 31ɣM 32,M 31ɘM 32=Ø,故|M 3|=2σ(n -1).综上所述,σ(n )=5σ(n -1)+2α(n -1).(3) 由(2)和(3)式可得σ(n )=9σ(n -1)-10σ(n -1).(4)易知σ(1)=7,α(1)=9,由(3)式得σ(2)=53.解线性递推式(4),得σ(n )=41+44182㊃9+41æèçöø÷2n +41-44182㊃9-41æèçöø÷2n . 定理3 令2n 个3圈为C 1i 3:u i 1u i 2u i 3u i 1,C 2i 3:v i 1v i 2v i 3v i 1(i =1,2, ,n ).分别连接圈C 1i 3与C 2i3的顶点u i j 与v i j (j =1,2,3;i =1,2, ,n ),再分别连接3圈C 1i 3与C 1,i +13的顶点u i 2与u i +1,3,C 2i 3与C 2,i +13的顶点v i 3与v i +1,2(i =1,2, ,n -1).这样得到的图记为2n C 6,3,如图4所示.τ(n )表示图2n C 6,3的完美匹配的数目.则τ(n )=13+31326㊃5+13æèçöø÷2n +13-31326㊃5-13æèçöø÷2n .证 欲求τ(n ),定义图G 2,并求其完美匹配的数目.将长为3的路v 2v 1u 1u 2的端点v 2和u 2分别与图2n C6,3的顶点v 12和u 13各连接一条边,得到的图记为G 2,如图5所示.显然图G 2有完美匹配.β(n )表示图G 2的完美匹配的数目.图4 图2n C 6,3图5 图G 2求β(n ).设图G 2的完美匹配的集合为M ,G 2含边u 1u 2,u 1v 1的完美匹配集合分别为M 1,M 2.则M 1ɘM 2=Ø.所以M =M 1ɣM 2,β(n )=|M |=|M 1|+|M 2|.类似于定理2的方法,容易求得:|M 1|=τ(n ),|M 2|=β(n -1).故β(n )=τ(n )+β(n -1).(5)求τ(n ).显然图2n C 6,3有完美匹配.设图2n C 6,3的完美匹配的集合为M .图2n C 6,3含边u 11u 13,u 11v 11,u 11u 12的完美匹配集合分别为M 1,M 2,M 3.则M =M 1ɣM 2ɣM 3,M i ɘM j =Ø(1ɤi <j ɤ3).所以τ(n )=|M |=|M 1|+|M 2|+|M 3|.11第2期 唐保祥,等:几类特殊图完美匹配数目的递推求法容易求得:|M 1|=τ(n -1)+β(n -2),|M 2|=2τ(n -1),|M 3|=τ(n -1).故τ(n )=4τ(n -1)+β(n -2).(6)由(5)和(6)式易得τ(n )=5τ(n -1)-3τ(n -2).(7)易知τ(1)=4,τ(2)=17,故线性递推式(7)的通解为τ(n )=13+31326㊃5+13æèçöø÷2n +13-31326㊃5-13æèçöø÷2n . 定理4 完全4部图K i 1,1,2,2的顶点集V (K i 1,1,2,2)的4分类为{u i 1,u i 2},{v i 1,v i 2},{x i },{yi }(i =1,2, ,n ).分别连接K i 1,1,2,2与K i +11,1,2,2的顶点u i 1与v i +1,2,v i 1与u i +1,2(i =1,2, ,n -1).这样得的图记为2n K 1,1,2,2,如图6所示.g (n )表示图2n K 1,1,2,2的完美匹配的数目,则g (n )=13+31326㊃11+313æèçöø÷2n +13-31326㊃11-313æèçöø÷2n .证 欲求g (n ),定义一个图G 3,并求其完美匹配的数目.将长为1的路u v 的端点u ,v 分别与K 11,1,2,2的顶点v 12,u 12连接一条边,得到的图记为G 3,如图7所示.显然图G 3有完美匹配.γ(n )表示图G 3的完美匹配的数目.图6 图2n K 1,1,2,2图7 图G 3求γ(n ).设图G 3的完美匹配的集合为M ,G 3含边u v ,u v 12的完美匹配的集合分别为M 1,M 2.则M 1ɘM 2=Ø.所以M =M 1ɣM 2,γ(n )=|M |=|M 1|+|M 2|.类似于定理2的方法,容易得到:|M 1|=g (n ),|M 2|=2g (n -1)+γ(n -1).故γ(n )=g (n )+2g (n -1)+γ(n -1).(8) 求g (n ).显然图2n K 1,1,2,2有完美匹配.设图2n K 1,1,2,2的完美匹配的集合为M ,图2n K 1,1,2,2含边v 12u 11,v 12x 1,v 12y 1,v 12u 12的完美匹配的集合分别为M i (i =1,2,3,4).则M i ɘM j =Ø(1ɤi <j ɤ4).故g (n )=|M |=|M 1|+|M 2|+|M 3|+|M 4|.容易得到:|M 1|=3g (n -1),|M 2|=g (n -1)+γ(n -1),|M 3|=g (n -1)+γ(n -1),|M 4|=2g (n -1)+γ(n -1).故g (n )=7g (n -1)+3γ(n -1).(9) 由(8)和(9)式易得g (n )=11g (n -1)-g (n -2).(10)线性递推式(10)的特征方程的根为x =11ʃ3132.易得g (1)=10,γ(1)=13.所以由(9)式得g (2)=109.故线性递推式(10)的通解为g (n )=13+31326㊃11+313æèçöø÷2n +13-31326㊃11-313æèçöø÷2n .参考文献:[1]C Y V I NSJ ,G U TMA NI .K e k u l éS t r u c t u r e s i nB e n z e n n o i dH y d r o c a r b o n s [M ].B e r l i n :S p r i n ge rP r e s s ,1988.[2] C I U C U M.E n u m e r a t i o no fP e rf e c t M a t c h i ng s i nG r a ph swi t hR e f l e c t i v eS y mm e t r y [J ].JC o m b i nT h e o r y :S e rA ,1997,77(1):87-97.[3] J O C K U S C H W.P e r f e c tM a t h i n g s a n dP e r f e c t S q u a r e s [J ].JC o m b i nT h e o r y :S e rA ,1994,67(3):100-115.[4] L O V ÁS ZL ,P L UMM E R M.M a t c h i n g T h e o r y [M ].N e w Y o r k :N o r t h -H o l l a n dP r e s s ,1986.21西南师范大学学报(自然科学版) h t t p ://x b b jb .s w u .c n 第39卷[5] V A L I A N T L G.T h eC o m p l e x s i t y o fC o m p u t i n g t h eP e r m a n e n t [J ].T h e o r e t i c a lC o m p u t eS c i e n c e ,1979,8(2):189-201.[6] Y A N W e i -g e n ,Z HA N GF u -j i .E n u m e r a t i o n o f P e r f e c tM a t c h i n g s o f aT y p e o f C a r t e s i a nP r o d u c t s o f R a p h s [J ].D i s c r e t e A p p l i e d M a t h e m a t i c s ,2006,154:145-157.[7] 唐保祥,任 韩.2类偶图完美匹配的数目[J ].西南大学学报:自然科学版,2012,34(10):91-95.[8] 唐保祥,李 刚,任 韩.3类图完美匹配的数目[J ].浙江大学学报:理学版,2011,38(4):16-19.[9] 唐保祥,任 韩.2类图完美匹配的数目[J ].西南师范大学学报:自然科学版,2011,36(5):16-21.[10]唐保祥,任 韩.4类图完美匹配的计数[J ].武汉大学学报:理学版,2012,58(5):441-446.O nR e c u r s i v eM e t h o d f o rF i n d i n g S e v e r a l T y pe s P a r t i c u l a rG r a p h s t h eN u m b e r o fP e rf e c tM a t c h i n gs T A N GB a o -x i a n g 1, R E N H a n 21.S c h o o l o fM a t h e m a t i c sa n dS t a t i s t i c s ,T i a n s h u i N o r m a l U n i v e r s i t y ,T i a n s h u i G a n s u 741001,C h i n a ;2.D e p a r t m e n t o fM a t h e m a t i c s ,E a s t C h i n aN o r m a l U n i v e r s i t y ,S h a n gh a i 200062,C h i n a A b s t r a c t :M a t c h i n g c o u n t i n g t h e o r y i s a t t h e c o r eo f g r a p h t h e o r y ,s i n c e i t o r i g i n s f r o m b o t h p h ys i c s a n d c h e m i s t r y .H o w e v e r ,t h e p r o b l e mo f c o u n t i n g t h en u m b e r o f p e r f e c tm a t c h i n g s f o r g e n e r a l g r a p h s i sN P -h a r d .I nt h i s p a p e r ,b y a p p l y i n g d i f f e r e n t i a t i o n ,s u mm a t i o na n dr e -r e c u r s i o nc a l c u l a t i o n ,t h es e v e r a l c o u n t i n g f o r m u l a s o f t h e p e r f e c tm a t c h i n g f o r f o u r s p e c i f i c t y p e s o f g r a ph s h a v eb e e n g i v e n .K e y wo r d s :p e r f e c tm a t c h i n g ;l i n e a r r e c u r r e n c e r e l a t i o n ;c h a r a c t e r i s t i c e q u a t i o n 责任编辑 廖 坤31第2期 唐保祥,等:几类特殊图完美匹配数目的递推求法。