3类特殊图完美匹配数的计算公式
- 格式：pdf
- 大小：254.95 KB
- 文档页数：5
下载文档原格式
合集下载
二分图的最大匹配、完美匹配和匈牙利算法
二分图的最大匹配、完美匹配和匈牙利算法August 1, 2013 / 算法这篇文章讲无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于求解匹配的匈牙利算法（Hungarian Algorithm）；不讲带权二分图的最佳匹配。
二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。
准确地说：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。
如果存在这样的划分，则此图为一个二分图。
二分图的一个等价定义是：不含有「含奇数条边的环」的图。
图 1 是一个二分图。
为了清晰，我们以后都把它画成图 2 的形式。
匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。
例如，图3、图 4 中红色的边就是图 2 的匹配。
我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。
例如图 3 中 1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
图 4 是一个最大匹配，它包含 4 条匹配边。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
图 4 是一个完美匹配。
显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。
但并非每个图都存在完美匹配。
举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。
是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。
如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。
基本概念讲完了。
二分图匹配题目类型总结.
二分图匹配题目类型总结二分图最大匹配的匈牙利算法二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。
最大匹配：图中包含边数最多的匹配称为图的最大匹配。
完美匹配：如果所有点都在匹配边上（x=y=m），称这个最大匹配是完美匹配。
最小点覆盖：(二分图)最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。
可以证明：最少的点（即覆盖数）＝最大匹配数。
支配集：（二分图）最小点覆盖数+孤立点最小边覆盖：找最大匹配（注意可能是任意图最大匹配）m则有2*m 个点被m 条两两不相交的边覆盖。
对于剩下的n-2*m 个点，每个点用一条边覆盖，总边数为n-m条;最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图Ｇ的所有结点。
解决此类问题可以建立一个二分图模型。
把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m。
最大独立集问题：(二分图)n-最小点覆盖;任意图最大匹配：（没有奇环）转换为二分图：把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果原图中有边i->j，则在二分图中引入边i-> j',j->i’；设二分图最大匹配为m,则结果就是m/2。
最大完全子图：补图的最大独立集三大博弈问题威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。
我们用（ak，bk）（ak ≤bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。
前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。
2类特殊图中的完美匹配数
2类特殊图中的完美匹配数唐保祥;任韩【摘要】Perfect matching counting problems for graphs have been proven to be NP-hard, so it is very difficult to get the number of perfectly matched general graph.The counting formula of the perfect matching for graphs 4-1-nC10and 2-nT2 was made by applying partition, summation and re-recursion.The number of all perfect matchings of many graphs can be calculated by the method presented in this paper.The given method is also able to implement the possibility to obtain the number of all perfect matchings with perfect matching graphs.%图的完美对集计数问题已经被证实是NP-难的,因此要得到一般图的完美匹配数目非常困难.用划分、求和、再递推的方法给出了4-1-nC10和2-nT2图完美匹配数目的计算公式.该方法可计算许多图类的所有完美匹配的数目,使得到一般的有完美匹配图的所有完美匹配数目成为可能.【期刊名称】《浙江大学学报（理学版）》【年(卷),期】2017(044)003【总页数】4页(P266-269)【关键词】划分;递推式;完美匹配【作者】唐保祥;任韩【作者单位】天水师范学院数学与统计学院,甘肃天水 741001;华东师范大学数学系,上海 200062【正文语种】中文【中图分类】O157.5Journal of Zhejiang University(Science Edition), 2017,44(3):266-269图的完美匹配计数已经被证实是NP-难问题,因此要得到一般图的完美匹配数目是非常困难的.该问题在蛋白质结构预测、量子化学、晶体物理学和计算机科学等领域都有重要应用,对此问题的研究具有非常重要的理论价值和现实意义[1-9].本文用划分、求和、再递推的方法分别给出了4-1-nC10和2-nT2图的完美匹配数目的计算公式.该方法能够计算许多类图的所有完美匹配的数目.定义1 若G图的2个完美匹配M1和M2中有一条边不同,则称M1和M2是G 的2个不同的完美匹配.定义2 设2条长为n的路：P1=u1u2…un+1,P2=v1v2…vn+1, 分别连接路P1与P2的顶点ui与vi(i=1,2,…,n+1)得到的图,称长为n的梯子,记为Tn.n个长为10的圈记为连接圈Ci上顶点vi1与vi2,连接圈Ci与Ci+1的顶点ui2与ui+1,1,ui3与ui+1,4,wi3与wi+1,4,wi2与wi+1,1(i=1,2,…,n-1),再分别连接圈C1与Cn的顶点u14与w14,u11与w11,un3与wn3,un2与wn2,得到的图记为4-1-nC10,如图1所示.设 n个长为2的梯子,其顶点集为).连接梯子和的顶点vi1与ui+1,1、vi3与ui+1,3(i=1,2,…,n-1)，再连接梯子的顶点u11与的顶点vn1与vn3，得到的图记为2-nT2,如图2所示.定理1 f(n)表示4-1-nC10图完美匹配的数目,则.证明 4-1-nC10图是3正则3边连通图,显然存在完美匹配.欲求f(n),需定义G1,G2,G3图,并分别求出其完美匹配的数目.4-1-nC10图删除边u11w11,u14w14后得到的图记为G;将路u1u2vw的顶点u1,u2,w分别与G图的顶点u11,u14,w14连接，得到的图记为G1;将路uvw1w2的顶点u,w1,w2分别与G 图的顶点u14,w14,w11连接，得到的图记为G2;将路u1u2的顶点u1,u2分别与G图的顶点u11,u14连接,再将路w1w2的顶点w1,w2分别与G图的顶点w14,w11连接，得到的图记为G3;G1,G2,G3图分别如图3～5所示.显然G1,G2,G3图都存在完美匹配,且G1≅G2.设G1,G2,G3图的完美匹配数分别为a(n),b(n),c(n),则a(n)=b(n).G1图的完美匹配按饱和顶点u1可划分为以下6种情形:情形1 由c(n)的定义,G1图包含边u1u11,u2u14,vw,v11v12,w14w11的完美匹配数为c(n-1).情形2 由a(n)的定义,G1图包含边u1u11,u2u14,vw,v11w14,w11w12的完美匹配数为a(n-1).情形3 由a(n)的定义,G1图包含边u1u11,u2v,ww14,v11w14,w11w12的完美匹配数为a(n-1).情形4 由b(n)的定义,G1图包含边u1u11,u2u14,vw,v11w14,w11w12的完美匹配数为b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).情形5 由c(n)的定义,G1图包含边u1u2,u11u14,vw,v11v12,w14w11的完美匹配数为c(n-1).情形6 由a(n)的定义,G1图包含边u1u2,u11u13,vw,v11w14,w11w12的完美匹配数为a(n-1).综上所述,G3图的完美匹配按饱和顶点u1可分以下8种情形求得：情形1 由c(n)的定义,G3图包含边u1u11,u2u14,v11v12,w1w14,w2w11的完美匹配数为c(n-1).情形2 由a(n)的定义,G3图包含边u1u11,u2u14,w1w2,v11w14,w11w12的完美匹配数为a(n-1).情形3 由c(n)的定义,G3图包含边u1u11,u2u14,v11v12,w1w2,w14w11的完美匹配数为c(n-1).情形4 由c(n)的定义,G3图包含边u1u2,u11u14,v11v12,w1w2,w14w11的完美匹配数为c(n-1).情形5 由c(n)的定义,G3图包含边u1u2,u11u14,v11v12,w1w14,w2w11的完美匹配数为c(n-1).情形6 由a(n)的定义,G3图包含边u1u2, u11u14, v11w14, w1w2, w11w12的完美匹配数为a(n-1).情形7 由b(n)的定义,G3图包含边u1u2,u11u12,u14v11,w1w14,w2w11的完美匹配数为b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).情形8 由b(n)的定义,G3图包含边u1u2,u11u12,u14v11,w1w2,w14w11的完美匹配数为b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).综上所述,4-1-nC10图的完美匹配按饱和顶点u11可分以下5种情形求得:情形1 由c(n)的定义,4-1-nC10图包含边u11w11,u14w14,v11v12的完美匹配数为c(n-1).情形2 由a(n)的定义,4-1-nC10图包含边u11u14,v11w14,w11w12的完美匹配数为a(n-1).情形3 由c(n)的定义,4-1-nC10图包含边u11u14,w11v12,w14w11的完美匹配数为c(n-1).情形4 由b(n)的定义,4-1-nC10图包含边u11u12,u14v11,w14w11的完美匹配数为b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).情形5 4-1-nC10图的完美匹配包含边u11u12,u14w14,v11v12,w11w12,则该完美匹配一定包含边ui3ui+1,4,wi3wi+1,4,ui+1,1ui+1,2,vi+1,1vi+1,2,wi+1,1wi+1,2,i=1,2,…,n-1.所以4-1-nC10图包含边u11u12,u14w14,v11v12,w11w12的完美匹配恰有1个. 综上所述,将式(1)和(2)代入式(3),得由式(3)得式(4)-式(5)×8得f(n)=8f(n-1)-4c(n-2)-7.由式(2)和(3)得由式(6)和(7)得易知非齐次线性递推式(8)的特解为1.齐次线性递推式f(n)=8f(n-1)-8f(n-2)的通解为由图6知f(1)=7.由式(3)知，由图7知a(1)=8.由图8知c(1)=12.所以，.定理2 g(n)表示2-nT2图的完美匹配数目,则g(n)=3n+1.证明 2-nT2图是2边连通3正则图,显然存在完美匹配.为求g(n),先定义G6图.删除2-nT2图的边u11u13得到的图记为G6,如图9所示.显然，G6图存在完美匹配，其完美匹配数记为d(n).G6图的完美匹配按饱和顶点u11的情况可分以下3种情形求得:情形1 由d(n)的定义,G6图包含边u11v11,u12v12,u13v13的完美匹配数为d(n-1).情形2 由d(n)的定义,G6图包含边u11v11,u12u13,v12v13的完美匹配数为d(n-1).情形3 由d(n)的定义,G6图包含边u11u12,v11v12,u13v13的完美匹配数为d(n-1).综上所述,d(n)=3d(n-1)=3n-1·d(1)，易知2-nT2图的完美匹配按饱和顶点u11可分以下4种情形求得:情形1 2-nT2图的完美匹配包含边u11u13,则其必包含边ui2vi2(i=1,2,…,n),vi1ui+11,vi3ui+13(i=1,2,…,n-1),vn1vn3.所以2-nT2图包含边u11u13的完美匹配恰有一个.情形2 由d(n)的定义,2-nT2图包含边u11u12,v11v12,u13v13的完美匹配数为d(n-1).情形3 由d(n)的定义,2-nT2图包含边u11v11,u12v12,u13v13的完美匹配数为d(n-1).情形4 由d(n)的定义,2-nT2图包含边u11v11,u12u13,v12v13的完美匹配数为d(n-1).综上所述,由式(10)和(11), 得g(n)=3n+1.【相关文献】[1] LOVSZ L, PLUMMER M. Matching Theory [M]. New York: North-Holland Press,1986.[2] KRL D, SERENI J S, STIEBITZ M. A new lower bound on the number of perfect matchings in cubic graphs [J]. Discrete Math,2009,23:1465-1483.[3] KARDOS F, KRL D, MISKUF J, et al. Fullerene graphs have exponentially many perfect matchings[J].Journal of Mathematical Chemistry,2009,46:443-447.[4] 唐保祥,任韩.几类图完美匹配的数目[J].南京师大学报:自然科学版,2010,33(3):1-6. TANG B X, REN H. The number of perfect matching for three specific types of graphs [J].Journal ofNanjing Normal University: Natural Science Edition,2010,33(3):1-6.[5] 唐保祥,李刚,任韩.3类图完美匹配的数目[J].浙江大学学报:理学版,2011,38(4):387-390. TANGB X, LI G, REN H. The number of perfect matching for three specific types ofgraphs[J].Journal of Zhejiang University: Science Edition,2011,38(4):387-390.[6] 唐保祥,任韩.3类特殊图完美对集数的计算[J].南开大学学报:自然科学版,2014,47(5):11-16. TANG B X, REN H. The enumeration of perfect matchings in three types of special graphs[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis,2014,47(5):11-16.[7] 唐保祥,任韩.4类图完美匹配数目的递推求法[J].数学杂志,2015,353(2):626-634. TANG B X, REN H. Recursive method for finding the number of perfect matchings of the four types of graphs[J]. Journal of Mathematics,2015,353(2):626-634.[8] 唐保祥,任韩.4类图完美匹配的计数[J].武汉大学学报:理学版,2012,58(5):441-446. TANG B X, REN H. The number of perfect matchings in four types of graphs[J]. Journal of Wuhan University: Natural Science Edition,2011,58(5):441-446.[9] 唐保祥,任韩.5类图完美匹配的计数[J].中山大学学报:自然科学版,2012,51(4):31-37. TANG B X, REN H. The number of perfect matchings in five types of graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni,2012,51(4):31-37.。
基本概念匹配最大匹配完美匹配 - 组合最优化.
令
，
。我们不妨先假设
是一个顶点覆盖。那显
然与
中的每个顶点相关联。既然 是一个匹配，所以 中不存在两端点都在
中的边。因为，给定一个被匹配的顶点
，设
为匹配边，那么由
的构建可知 一定也在 。
剩下的问题就是来证明
中，从而 中每条边至少与
中的一个端点相交。综上，
是顶点覆盖。假设不是，那么必存在一条以
和
为两端点的边
□
要在一般图中找一条可增广路，我们可以修改一下二部图中的算法，使之可以发现花。发现 了，就对其进行收缩，然后在新的图上重新开始。在新图上找到的任意增广路都可以很容易 的对应到原图中的增广路，而且，由上面的引理可知，如果在新图中匹配是最大的，那么原 图中对应的匹配也是最大的。
下面是算法的正式描述。令 为图 的一个匹配， 为未被匹配顶点的一个子集（如果 每个顶点都是被匹配的，那么这个匹配就是最大匹配），我们要构造一个森林 ，使 中 的每一个顶点在一个连通分支上。像以前那样交替的增加未匹配边和匹配边来扩展 。那 么被添加到 中的 的边与 的距离为奇数。而且，与 距离为奇数的顶点度数为 2（一 条未匹配边，一条匹配边），我们把这样的顶点称为内顶点，而其余的称外顶点。 中所有 的顶点都是外顶点。
是 M 和 P 的对称差，记为
容易证 也是一个匹配，而且所含边数比 M 多一条。
这样的交错路 P 称为一条可增广路。上述分析就产生了下面的“算法”。
匹配算法：
{ 1、 从任意匹配开始。 2、 找当前匹配的一条可增广路。 3、 增广当前匹配。 4、 尽可能地重复上面两步。
} 算法终止的时候，得到一个没有可增广路的匹配 们此时 一定是最大匹配。
完美匹配。如果 A 等于 0 或 1，显然结论成立。下面分两种情况考虑：
第九章 几类特殊图
(a0a1a2a5a10a4a9a3a6a13a11a7a15a14a12a8)
(这里ai表示边i，i＝0,1,2,…,15)，对 应的16个二进制数字序列为 0000101001101111，将序列两端闭 合，便得到16个二进制数字的一个 圆形排列，可以验证正好符合我们 的要求。
哈密顿通路、哈密顿回路: 无向图或有向图G中经过 每个顶点一次且仅一次的通路，称为哈密顿通路； 经过每个顶点一次且仅一次的初级回路，称为哈密 顿回路。
推论 无向图G为欧拉图当且仅当，G是连通图且无奇 度顶点。
判断下面图是否为欧拉图。
定理9.2 有向图D有欧拉通路当且仅当，D是连通图， 并且所有顶点的入度等于出度，或者除两个顶点外， 其余顶点的入度等于出度，而这两个顶点，一个入度 比出度大1，另一个入度比出度小1。
推论 有向图D是欧拉图当且仅当，D是连通图且所有 顶点的入度等于出度。
K3,3
X
Y
x1 y1
x2 y2
x3 y3
x4
证明 必要性 设G＝〈V1, V2,E〉为二部图，证明G中 无奇数长度的回路。若G中无回路，结论当然成立。
若G中有回路，设C＝u0u1u2…ut－1u0为G中的一条回 路，其长度为t 。不妨设u0∈V1，则对于每个小于t的 正奇数i，ui∈V2，而对于每个小于t的正偶数j，uj∈ V1 。因为G中存在边(ut－1, u0)，所以ut－1∈ V2 ，因而t －1必为奇数，即t
在判别一个二部图是否存在从V1到V2的匹配时，可 以先检查“t条件”是否满足，这是比较容易进行的。 如果“t条件”不满足，可再进一步用“相异性条件” 检查。
例 求图9.14(a)的最大匹配。 解 显然满足 “t条件”（t=2），所以存在从V1到V2的 匹配，也即最大匹配。
(这里ai表示边i，i＝0,1,2,…,15)，对 应的16个二进制数字序列为 0000101001101111，将序列两端闭 合，便得到16个二进制数字的一个 圆形排列，可以验证正好符合我们 的要求。
哈密顿通路、哈密顿回路: 无向图或有向图G中经过 每个顶点一次且仅一次的通路，称为哈密顿通路； 经过每个顶点一次且仅一次的初级回路，称为哈密 顿回路。
推论 无向图G为欧拉图当且仅当，G是连通图且无奇 度顶点。
判断下面图是否为欧拉图。
定理9.2 有向图D有欧拉通路当且仅当，D是连通图， 并且所有顶点的入度等于出度，或者除两个顶点外， 其余顶点的入度等于出度，而这两个顶点，一个入度 比出度大1，另一个入度比出度小1。
推论 有向图D是欧拉图当且仅当，D是连通图且所有 顶点的入度等于出度。
K3,3
X
Y
x1 y1
x2 y2
x3 y3
x4
证明 必要性 设G＝〈V1, V2,E〉为二部图，证明G中 无奇数长度的回路。若G中无回路，结论当然成立。
若G中有回路，设C＝u0u1u2…ut－1u0为G中的一条回 路，其长度为t 。不妨设u0∈V1，则对于每个小于t的 正奇数i，ui∈V2，而对于每个小于t的正偶数j，uj∈ V1 。因为G中存在边(ut－1, u0)，所以ut－1∈ V2 ，因而t －1必为奇数，即t
在判别一个二部图是否存在从V1到V2的匹配时，可 以先检查“t条件”是否满足，这是比较容易进行的。 如果“t条件”不满足，可再进一步用“相异性条件” 检查。
例 求图9.14(a)的最大匹配。 解 显然满足 “t条件”（t=2），所以存在从V1到V2的 匹配，也即最大匹配。
29-匹配
匹配
离散数学 第29
上一讲内容的回顾
图的平面嵌入 平面图和非平面图 平面图的必要条件：欧拉公式 适用于简单图的欧拉公式推论 平面图的充分必要条件-Kuratowski定理 图着色 平面图着色与四色定理
匹配
支配集 点覆盖集与独立集 边覆盖集 匹配 最大匹配和完美匹配 二部图中的匹配 Hull定理
支配集与支配数
最小边覆盖与最大匹配的关系
证明W是最小边覆盖，M1是最大匹配．
W显然是边覆盖，所以 |W|≥α1。注意：|M|=β1, 又因为M是最大 ≥α 匹配，N中不可能有一条边的两个端点都是M-非饱和点，∴ |N|=n-2β1，∴|W|=|M|+|N|=n-β1。 β 而M1=W1-N1显然是匹配, |M1|≤β1。W1是最小边覆盖, 所以，构 ≤β 造 M1 时 ， 每 移 去 一 条 边 ， 恰 好 产 生 一 个 M1- 非 饱 和 点 。 而 |W1|=α1, M1-非饱和点数为n-2|M1|，∴|N1|=|W1|-|M1|=n-2|M1|, 即 α1= n-|M1|。 综 上 所 述 可 得 ： α 1= n-|M1|≥n-β1=|W|≥α1, 于 是 ： |W|=α1 且 ≥ β ≥α |M1|=β1，即W是G中的最小边覆盖，且M1是G中的最大匹配。
注意：极小支配集未必是最大独立集 (甚至未必是独立集)
极小支配集 不是 独立集
点覆盖与点覆盖数
点 覆盖 边
点覆盖数 α0=3
点覆盖数 α0=4
最小点覆盖 极小点覆盖
点覆盖与点独立集的关系
设G是无孤立点的简单无向图，VG的真子集V*是点 覆盖当且仅当V-V*是点独立集。 证明：令V’=V-V* ∈ ⇒ 假 设 V' 不 是 独 立 集 ， 则 存 在 u,v∈V', 满 足 uv∈EG, 注意：V‘=VG-V*, 即u,v∉V*, ∴uv边不可能被 V*所覆盖，矛盾。 ⇐ ∀e∈EG, 假设e=uv, 因为V‘是点独立集，u,v中 至 少 有 一 个 不 在 V' 中 ， 不 妨 设 u∉V', 则 u∈V*, ∴V* 是点覆盖。
离散数学 第29
上一讲内容的回顾
图的平面嵌入 平面图和非平面图 平面图的必要条件：欧拉公式 适用于简单图的欧拉公式推论 平面图的充分必要条件-Kuratowski定理 图着色 平面图着色与四色定理
匹配
支配集 点覆盖集与独立集 边覆盖集 匹配 最大匹配和完美匹配 二部图中的匹配 Hull定理
支配集与支配数
最小边覆盖与最大匹配的关系
证明W是最小边覆盖，M1是最大匹配．
W显然是边覆盖，所以 |W|≥α1。注意：|M|=β1, 又因为M是最大 ≥α 匹配，N中不可能有一条边的两个端点都是M-非饱和点，∴ |N|=n-2β1，∴|W|=|M|+|N|=n-β1。 β 而M1=W1-N1显然是匹配, |M1|≤β1。W1是最小边覆盖, 所以，构 ≤β 造 M1 时 ， 每 移 去 一 条 边 ， 恰 好 产 生 一 个 M1- 非 饱 和 点 。 而 |W1|=α1, M1-非饱和点数为n-2|M1|，∴|N1|=|W1|-|M1|=n-2|M1|, 即 α1= n-|M1|。 综 上 所 述 可 得 ： α 1= n-|M1|≥n-β1=|W|≥α1, 于 是 ： |W|=α1 且 ≥ β ≥α |M1|=β1，即W是G中的最小边覆盖，且M1是G中的最大匹配。
注意：极小支配集未必是最大独立集 (甚至未必是独立集)
极小支配集 不是 独立集
点覆盖与点覆盖数
点 覆盖 边
点覆盖数 α0=3
点覆盖数 α0=4
最小点覆盖 极小点覆盖
点覆盖与点独立集的关系
设G是无孤立点的简单无向图，VG的真子集V*是点 覆盖当且仅当V-V*是点独立集。 证明：令V’=V-V* ∈ ⇒ 假 设 V' 不 是 独 立 集 ， 则 存 在 u,v∈V', 满 足 uv∈EG, 注意：V‘=VG-V*, 即u,v∉V*, ∴uv边不可能被 V*所覆盖，矛盾。 ⇐ ∀e∈EG, 假设e=uv, 因为V‘是点独立集，u,v中 至 少 有 一 个 不 在 V' 中 ， 不 妨 设 u∉V', 则 u∈V*, ∴V* 是点覆盖。
匹配计数公式
匹配计数公式匹配计数公式是一种数学工具，用于计算给定条件下的可能情况的数量。
在概率论和组合数学等领域中经常会用到匹配计数公式。
这些公式帮助我们解决许多与排列、组合、排队和分配相关的问题。
匹配计数公式分为几种常见类型：排列、组合和二项式系数。
首先是排列。
排列是指从一组物体中选出一部分物体，按特定顺序排列的方式。
排列计数公式用于计算这种排列的数量。
在给定n个物体的情况下，可以使用以下排列计数公式来计算从中选取r个物体按顺序排列的可能情况数量：P(n, r) = n! / (n-r)!其中n!表示n的阶乘，即n! = n * (n-1) * (n-2) * ... * 1。
接下来是组合。
组合是指从一组物体中选出一部分物体，不考虑其顺序的方式。
组合计数公式用于计算这种组合的数量。
在给定n个物体的情况下，可以使用以下组合计数公式来计算从中选取r个物体的可能情况数量：C(n, r) = n! / (r! * (n-r)!)最后是二项式系数。
二项式系数是表示二项式展开中每一项的系数。
在给定非负整数n的情况下，可以使用以下二项式系数计数公式来计算二项式展开中第r项的系数：C(n, r) = n! / (r! * (n-r)!)匹配计数公式在很多实际问题中都有应用。
例如，在概率问题中，我们可以使用组合计数公式来计算从一副扑克牌中抽取r张牌的可能情况数量。
在组合数学中，匹配计数公式用于计算圆排列、循环排列和二项分布等问题。
总之，匹配计数公式是解决排列、组合和二项式系数问题的有用工具。
它们在数学和其他学科中发挥着重要作用，帮助我们计算不同情况下的可能性数量。
一类特殊立方图的完美匹配个数
一类特殊立方图的完美匹配个数摘要】一个立方图是一个所有顶点都是三度点的图，边集E（G）的子集M称为G的一个完美匹配，若其中的每个元素为边且任意两个在G中不相邻，并满足|V （M）|＝|V（G）|。
【关键词】立方图完美匹配【中图分类号】O13 【文献标识码】A 【文章编号】1006－9682（2009）03－0137－01【Abstract】A cubic graph is a graph each vertex of which has degree three. A subsetM of E（G）is called a perfect matching in G if its elements are links and no two are adjacent in G and|V（M）|＝|V（G）|.【Key words】Cubic graph Perfect matching定理1，若立方图G的每个块均为k4－e，则pm（G）＝1＋2k，其中k（k≥2）是G中k4－e的个数。
证明：若G为立方图，且G的每个块均为k4－e，而每个k4－e均有两个2度点。
故G可看作由k4－e作为点构成的一个圈。
由G的结构易知：圈上的边或者全在G的完美匹配之中，或者全部不在G的完美匹配之中。
当G的完美匹配包含圈上的边时，显然每个k4－e对完美匹配的个数贡献为1，故只有1个此类的完美匹配。
当G的完美匹配不包含圈上的边时，则此类完美匹配全部由k4－e上的边构成，此时每个k4－e对完美匹配的个数贡献为2，故有2k个此类的完美匹配。
所以pm（G）＝1＋2k。
定理2，若立方图G的每个块均为梭子，则pm（G）＝2k＋1，其中k（k≥2）是G中梭子的个数。
证明：若G为立方图，且G的每个块均为梭子，而每个梭子均有两个2度点。
故G可看作由梭子作为点构成的一个圈。
如图2所示：由G的结构易知：圈上的边或者全在G的完美匹配之中，或者全部不在G的完美匹配之中。
的完美匹配
4
Bellman-ford求解过程：第2次迭代
最短路问题
5 5 0 a 起点 b -2 c 3 3 d 终点 6
4
Bellman-ford求解过程：第3次迭代
最短路问题
5 5 0 a 起点 b -2 c 3 3 d 终点 6
4
Bellman-ford求解过程：得到最终路径
最短路问题
Floyd-Warshall算法
例：为v2寻找增广路的搜索路径
二部图匹配
[例1，POJ 1719] 射击比赛
Byteland射击比赛的 规则是这样的： 每位选手需要向一个含有r*c 个小方格(2≤r,c≤1000)矩射击。 小方格由黑白两色组成，其中 每一列由2个白格子和r-2个黑 格子。 现在我们要求选手射击c次， 使得每一列中的两个白格有且 仅有一个被射中，而每一行至 少有一个白格子被射中。问是 否存在这样的策略？
二部图匹配
KM算法描述:
如何修改A[]，B[]
当增广路查找失败时， 我们得到了一颗匈牙利树
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最小生成树
Kruskal方法：
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最短路问题
在加权图中找到两点之间的最短路径 （权值和最小）
图论
蒋威 2008-12-25
图论
基本概念 最小生成树 最短路问题 二部图匹配 *网络流
2类图完美匹配数目解析式的嵌套递推求法
对一些特殊图的完美匹配计数
的研究%#de&G
2类
特殊图完美匹配数目的计算公式G
方法，适合
>?@B 图!是一 有完美匹配的图， 图!的
和 "2 是 !的
完美匹配#
重 现的
图完美匹配数的 •
完美匹配"#和"2中有一
，
"#
定义! $# =%# %2…％2”，$2='# '2…'”-# '&是两条路，分
"1
%', %%1 的完美匹配的 E
"1 C "2,
7-;DCA7-;+,$01%@
则""","#",(1,2,且"# $"2 二"，"⑴="# %" ,!(”)=丨"⑴ I#
求I"1'因为％” &"1，所！由/(”)的定义知，I"#丨=/(”)# 求 '2 ' 因为 %%# & "2，所以 VV# ,”2”" & "2，由!( ”)的定义知,IM2 I #
匹配理论是图论研究的重要
， 在 的 年中，它是
论已经在
应用，
一， 是一 有 机 的研究 ，
具有 的应用
的组合论中 重要 的 •目前，图的完美匹配计数理
数学1、物理学1和化学1的
G 的是，16:<6>7,%#&
年证一个图！ 是图）的完美匹配计数是NP-难问题•因此，要 一般图的完美匹配数的计算
式是 的•目前，已有一
的方
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
１ 基 本 概 念
定义 １ 两条长为 ｎ的路为 Ｐ ＝ 。ｉｔ２－．． Ｐ２＝Ｖ１口２－．．Ｖ ＋１’分别 连接 路 Ｐ１与 Ｐ２的顶 点 ｕｉ与
（ｉ＝ １，２，… ，ｎ＋１）所 得 到 的 图 ，称 为 长 为 ｎ的 梯 子 ，记为 。
定 义 ２ 设 ｍ ＋ １条 长 为 ｎ 的 路 Ｐｉ＝ ｎ／￣／２ …Ｕ ＋１（ｉ＝１，２，… ，ｍ，ｍ ＋１），连接 路 Ｐ 与 Ｐ 中的顶点 与 ．ｆ （ ＝ １，２，… ，ｍ； ＝ １，２，
Ａｂｓｔｒａｃｔ： Ｐｅｒｆｅｃｔ ｍａｔｃｈｉｎｇ ｃｏｕｎｔｉｎｇ ｐｒｏｂｌｅｍｓ ｇｒａｐｈ ｈａｓ ｂｅｅｎ ｐｒｏｖｅｎ ｔｏ ｂｅ ＮＰ－ｈａｒｄ．Ｔｏ ｇｅｔ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐｅｒｆｅｃｔｌｙ ｍａｔｃｈｅｄ ｇｅｎｅｒａｌ ｇｒａｐｈ ｉｓ ｖｅｒｙ ｄｉｆｆ ｉｃｕｌｔ．Ｔｈｅ ｉｓｓｕｅ ｈａｓ ｉｍｐｏｒｔａｎｔ印 ｐｌｉｃａｔｉｏｎｓ ｉｎ ｐｒｏｔｅｉｎ ｓｔｒｕｃ－ ｔｕｒｅ ｐｒｅｄｉｃｔｉｏｎ，ｃｒ ｙｓｔａｌ ｐｈｙｓｉｃｓ，ｑｕａｎｔｕｍ ｃｈｅｍｉｓｔｒｙ ａｎｄ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ．Ｔｈｅ ｒｅｓｅａｒｃｈ ｏｎ ｔｈｉｓ ｉｓｓｕｅ ｈａｓ ｖｅｒ ｙ ｉｍｐｏｒｔａｎｔ ｔｈｅｏｒｅｔｉｃａ ｌ ａｎｄ ｐｒａｃｔｉｃａｌ ｓｉｇｎｉｆ ｉｃａｎｃｅ． Ｔ ｈ ｅ ｃｏｕｎｔｉｎｇ ｆｏｒｍｕｌａ ｏｆ ｔｈｅ ｐｅｒ ｆｅｃｔ ｍａｔｃｈｉｎｇ ｆｏｒ
第 ５６卷 第 ３期
中山大学学报 （自然科学 版）
２０１７年 ５月
ＡＣＴＡ ＳＣＩＥＮＴＩＡＲＵＭ ＮＡＴＵＲＡＬＩＵＭ ＵＮＩＶＥＲＳＩＴＡＴＩＳ ＳＵＮＹＡＴＳＥＮＩ
ＶＱ１．５６ Ｎｏ．３ Ｍａｖ ２０１７
ＤＯＩ：１０．１３４７１／ｊ．ｃｎｋｉ．ａｃｔａ．ＳｎＵＳ．２０１７．０３．００６
收 稿 日期 ：２０１６—０８—０５ 基金项 目：国家 自然科 学基金 （１１１７１１１４） 作者简 介 ：唐保 祥 （１９６１年生 ），男 ；研究方 向：图论和组合数学 ；Ｅ—ｍａｉｌ：ｔｂｘ０６１８＠ｓｉｎａ．ｔｏｍ
第 ３期
唐保祥等 ：３类特殊 图完美匹配数 的计算公式
３７
… ，／７，，／／，＋１） 所 得 的图 ，称 为 ｍ ｘ ｎ的棋 盘 。本 文 将 ／７／，Ｘ ｔ＇ ｂ的 棋 盘 记为 Ｑ 。
Ｔｈｅ ｃｏｕｎｔｉｎｇ ｆｏｒｍｕｌａ ｏｆ ｔｈｅ ｐｅｒｆｅｃｔ ｍ ａｔｃｈｉｎｇｓ ｏｆ ｔｈｒｅｅ ｔｙｐｅｓ ｏｆ ｓｐｅｃｉａｌ ｇｒａｐｈｓ
ＴＡＮ Ｇ Ｂａｏｘｉａｎｇ ，ＲＥＮ Ｈａｎ
（１．Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｓｔａｔｉｓｔｉｃｓ，Ｔｉａｎｓｈｕｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｓｈｕｉ ７４１００１，Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｅａｓｔ Ｃｈｉｎａ Ｎｏｒ ｍ ａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００６２，Ｃｈｉｎａ）
定义 ３ 若图 ｃ的两个完美匹配 和 中有一 条边不同，贝 Ｕ称 Ｍ 和 是 Ｇ的两个不同完美匹配。
ｎ 个长为 ２的梯子 的顶点集 （ ）＝ ｛ ｍ
２×２棋盘 Ｑ 的顶点集为 （Ｑ ）＝ ｛／４， ，
２ｉ，
，
，２１￣１ ，Ｕ ｉ＋Ｉ ２１—１ ，Ｕ ｉ＋１２ｉ，／．ｔｉ＋１ ２ｉ＋１，Ｕｉ＋２ ２ｉ一１ ，／／＇ｉ＋２ ２ｉ，
ｇｒａｐｈｓ ３一 ，５一凡 ａｎｄ ２—２ｎＱ２ ２ ａ ｒｅ ｏｂｔａｉｎｅｄ ｂｙ ａｐｐｌｙｉｎｇ ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ，ｓｕｍｍａｔｉｏｎ ａｎｄ ｒｅ—ｒｅｃｕｒ－
ｓｉｏｎ ．Ｔｈｉｓ ｐｒｏｖｉｄｅｓ ｔｈｅ ｔｈｅｏｒｙ ｓｕｐｐｏｒｔ ｆｏｒ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｐｅｒｆｅｃｔ ｍａｔｃｈｉｎｇ ｉｎ ｇｒａｐｈ． Ｋｅｙ ｗｏｒｄｓ：ｐｅｒｆｅｃｔ ｍａｔｃｈｉｎｇ；ｌａｄｄｅｒ；ｒｅｃｕｒｒｅｎｃｅ ｒｅｌａｔｉｏｎ；ｃｈｅｓｓｂｏａｒｄ
３类特殊 图完美匹配数 的计算公 式
唐 保 祥 ，任 韩２
（１．天水师范学院数学与统计学院，甘肃 天水 ７４１００１； ２．华东师范大学数学系，上海 ２０００６２）
摘 要 ：图的完美对集计数问题已经被证实是 ＮＰ一难问题 ，因此要得到一般图的完美对集的数 目是非常困难 的。该 问题在 蛋白质结构 预测 、晶体物理学 、计算机 科学 和量子 化学 中都有重要 的应 用 ，对此 问题的研究 具有 非 常重要的理论价值和现实意义 。用划分 ，求 和 ，再 递推 的方法 分别给 出了 图 ３一 ，５一ｎ 和 ２—２ｎＱ： ｚ的 完美 匹配数 目的计算公式 ，为图 的完美 匹配 问题 的应用 提供了理论支持 。 关键 词 ：完美匹配；梯子；递推式；棋盘 中 图分类 号 ：Ｏ１５７．５ 文 献标 志码 ：Ａ 文章编 号 ：０５２９—６５７９（２０１７）０３—００３６—０５
图 的完 美 匹配 计 数 理 论 的 研 究 成 果 已经 在 化 学 、物理学 和 计算 机科 学 中得 到应用 ，图 的完 美 匹 配 的理 论在 很 多领域 有 广泛 应用 ，例 如 ：积 和式在 计算机科学 ，特别是计算复杂性理论 中有重要的地 位 ，二分 图 的完美 匹 配 的数 目可 以方 便 地表 示为 计 算积和式的值 ；它也是组合数学的思想源泉 ，因此 受到众多学者的关注ｕ ，本 文给 出了 ３类 图完 美匹配数 目的计算公式 ，文中所给方法 ，适合相同 结构 重复 出现 的很 多类 图完 美 匹配数 的求解 。
ห้องสมุดไป่ตู้
，
，
，
，
，
ｍ ｌ２ｌ＋ｔ｝（ｉ ＝ １，２，… ，２ ），将 棋 盘 ： 的 边
Ｕ ｉ＋１ ，２ｉ＋１ ｍ
＋ｌ 与 棋 盘
Ｑ ×２的边
／ｄ＇ｉ＋１２ｉ＋１“ｍ ＋１重 合 ，