下载文档原格式
离散数学是数学中的一个重要分支，它研究的是离散的、离散的、不连续的数学结构与问题。
而图论是离散数学的一个重要领域，它研究的是图的性质和关系。
在离散数学中，图是一个由节点（顶点）和边组成的网络结构。
节点表示实体，边表示节点之间的关系。
图的匹配是指一种边的选择方式，使得没有两个边具有相同的起点或终点。
图的匹配问题是图论中的一个经典问题，匹配理论则是研究匹配问题的理论基础。
图的匹配在实际中有广泛的应用，比如在交通规划、人员分配等领域中都涉及到匹配问题。
在图的匹配问题中，存在两种不同的匹配，分别是最大匹配和完美匹配。
最大匹配是指在所有可能的匹配中，边数最多的匹配，而完美匹配是指图中的每个节点都被匹配。
在图的匹配问题中，一个重要的概念是增广路径。
增广路径是指一个由未匹配的顶点和匹配点依次相连所构成的路径。
通过寻找增广路径，可以使得匹配数增加，从而逐步逼近最大匹配。
图的匹配理论主要围绕匹配数的计算和匹配的寻找展开。
最简单的匹配算法是贪心算法，即每次找到一个未匹配的节点，与之相连的边进行匹配，并不断更新匹配的边。
然而，贪心算法无法保证得到最优解，因此需要其他更加高效的算法来解决匹配问题。
其中一种经典的算法是匈牙利算法，它以增广路径为基础，通过不断寻找增广路径来找到最大匹配。
匈牙利算法的核心思想是通过不断寻找增广路径来增加匹配数。
具体步骤如下：1.初始化所有节点都未匹配2.对每个未匹配的节点，进行深度优先搜索，寻找增广路径3.如果找到增广路径，则将路径上的边匹配4.重复步骤2和步骤3，直到无法找到增广路径5.返回匹配结果匈牙利算法的时间复杂度为O(V * E)，其中V为节点数，E为边数。
虽然匈牙利算法在时间复杂度上不是最优的，但它具有简单易懂、容易实现的优点。
在实际应用中，匹配问题往往需要考虑更多的因素，比如权重、容量等。
为了解决带权匹配问题，可以使用最小权重匹配算法，比如Dijkstra算法或Floyd-Warshall算法。
图论是离散数学中的一个重要分支，其中图的匹配问题被广泛研究和应用。
图的匹配是指在一个图中找到一组边，使得每个顶点都与其中的一条边相关联。
匹配问题在实际生活中有着广泛的应用，例如婚姻问题中的稳定婚姻匹配、求解工程布线问题、计算机网络中的路由问题等等。
在图的匹配问题中，一个匹配是指一个边集，其中任意两条边的两个顶点都不相同。
一个最大匹配是指具有最多边数的匹配，而完美匹配是指包含图中所有顶点的匹配。
为了求解图的最大匹配和完美匹配问题，研究者们提出了多种匹配算法。
下面介绍两种常见的匹配算法：增广路径算法和匈牙利算法。
增广路径算法是一种基于搜索的匹配算法。
该算法通过递归地搜索增广路径来不断扩展当前匹配的边集。
增广路径是指一条从未匹配的顶点开始，交替经过边集中的匹配边和未匹配边的路径。
当找到一个增广路径时，可以通过将路径上的未匹配边和已匹配边进行交换来增加匹配的边数。
该算法重复执行这一步骤，直到没有增广路径可以找到为止。
最终得到的边集就是一个最大匹配。
匈牙利算法是一种贪心算法。
该算法从一个未匹配的顶点开始，尝试将其与任意还未匹配的邻接顶点进行匹配，并递归地对邻接顶点进行匹配。
如果当前的匹配可以被改进，则进行匹配的调整。
当所有的顶点都被匹配上时，得到的边集就是一个完美匹配。
图的匹配问题具有多项式时间复杂度的解法，因此可以有效地求解大规模问题。
匹配算法在现实生活中的应用非常广泛，它们被广泛应用于计算机网络、人工智能、生物信息学等领域。
例如，在计算机网络中，匹配算法可以用于求解最优路由问题，以便在网络传输过程中选择最佳的路径。
在交通运输中，匹配算法可以用于最佳路径规划、货物调度等。
在社交媒体中，匹配算法可以用于推荐好友、推荐兴趣爱好等。
总结来说，离散数学中的图的匹配问题是一个重要而有趣的领域。
它的应用涉及广泛，算法也多样。
增广路径算法和匈牙利算法是两种常见的图匹配算法，它们在实际问题中具有重要的作用。
在未来的研究中，我们可以进一步研究图匹配问题的优化算法和高效实现方式，以满足不同实际问题的需求。
第八讲图论中的匹配与逻辑推理问题
先看一个例题.中、日、韩三个足球队进行比赛，已知A不是第一名，B不是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C各代表哪国队？各是第几名？
一般解这类题都归于逻辑推理类问题.
我们先来降低难度.先只要求你判断出中、日、韩各是第几名（不必判断A、B、C）.可以把中、日、韩各用一个点代表，列于上一行.第一、二、三名各用一个点代表，列于下一行，记为：
V1=｛中，日，韩｝，V2=｛第1名，第2名，第3名｝.
V1中的点与V2中某一个点有肯定关系的，就画一条实线，如和②.否定关系的两点之间画一条虚线，如不是②；不是①.把已知条件不加任何推理地表现于图上.虚线2条，实线1条，共3条线.
现在，有两个明显的事实；第一，V1中每点有且只有一条实线与V2中相应点配对，V2中每点有且只有一条实线与V1中相应点配对.V1内部点之间不会有线相联结，V2内部点之间也不会有线相联结.第二，从V1（或V2）中某一个点，例如说a点如发出了一条实线向着V2（或V1）中某一个点，例如说x点，那么a点与V2（或V1）中其他点之间必然只能用虚线联结.（这是逻辑推理中的排它性）
由此，我们很容易将中、日、韩的名次判出.
这样的问题，抽象起来可归属于图论中称之为“二分图的匹配”问题.
图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以前在“一笔画”等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V=V1＋V2，如V1有p个点，记为V1=｛v1，v2…，v p｝，V2有q个点，记为V2=｛v p+1，v p+2…，v p+q｝，而V1中任意一点，不会与V1中其他点联结，而只能与V2中某些点联结；V2也如此.大家看几个例.
一般的图记为G＝（V，E），V是顶点集合，E是边（也可称为线）的集合.大家在哥尼斯堡七桥问题中已领略过这种抽象.现在的二分图是一类特殊的图，只不过顶点集V划分为两部分，而这只能“跨越”于V1中某个点和V2中另一个点.二分图的匹配问题，就是找一个边的集合，这些边之间都没有公共的端点.
关于二分图的匹配，要研究的是“最大匹配”，即找一个边最多的匹配.
就本讲开始引入的问题看，我们还没有解完，因为还有A、B、C三个代号到底如何归于中、日、韩三队的问题.一种解题办法，是把已判出的国籍和名次捆绑在一个顶点内，如（中2）、（韩1）、（日3），再和A、B、C 构造一个新的二分图：
显然，推知B是（日3），因为B有2条虚线，而必然有1条实线，只能推出B与（日3）之间为实线.同理，（韩1）只能为C；剩下的唯一的情况留给了A为（中2）.全部问题解决了.
再看最初的题目，如果你选择先判断中、日、韩和A、B、C三个代号之间的匹配关系，将会怎样呢？画一个图看，利用已知条件画出实、虚线.
只能利用B不是韩国队及中国队第二，B不是第二（因此B不是中国队）这样一些条件，题目中另二句话：A不是第一名，第一名不是日本队，这种否定关系之间，没有传递性，你不能判定A是不是日本队.因此根据已知条件所画的图中只有两条虚线，之后最多只能确定日、B之间为实线.所以对这样的二分图，无法找出合理的最大匹配.这方法使问题求解走进了死胡同.
那么你选择先判A、B、C和第一、第二、第三名之间的匹配关系，又会怎样呢？画一个图看.
现在也只有二条虚线，仍然无法找出最大匹配，或说解不唯一，对求解问题无助.
现在回过头来看，先找国别与名次之间的匹配，似乎有些“碰运气”，因为完全可以把题目改动，使先找国别与名次的匹配无法解决，例如叙述
改为：
中、日、韩三足球队比赛，已知结果为：第1名不是A，第2名不是韩国队也不是B，A不是日本队，中国队为B，问A、B、C，和1、2、3名与各国队如何匹配？
细心读者发现，这只是把原题中A、B、C的地位与1、2、3名的地位互换而已.所以现在改动后的题目，再先抓“国别”和“名次”的匹配，就无法求解.
但是数学要求找出一种解一般问题的方法而不是“碰运气”，而且完全可以找一个例子，使得无论取国别与名次；或国别与代号（A，B，C）；或代号与名次这三类二分图的匹配都无法求解，而必须找更广泛意义下的匹配才能解决，为此先介绍一般的三个因素一起考虑的“匹配”方法.
先结合前例，将国别用三个不同点表示于上方，三个名次点表示于左下方，三个代号点表示于右下方.用实线的肯定关系和虚线的否定关系把已知条件“翻译”于图上.
我们现在的目的是要寻找一个捆绑三条实线边的一条广义边，使每个国别与一个名次及一个代号捆绑在一起，使问题一次性解决，遵循的原则有以下4条：
①肯定关系具有排它性（如中=第2名，则中≠第1名，中≠第3名，第2名≠日，第2名≠韩）.
②肯定关系具有传递性（如已知中=第2名，一旦推知肯定关系第2名=A，那么中=A）.
③任意两个类别的点之间要建立一种合理的完全匹配.（如国别和名次之间；名次与代号之间；国别与代号之间）.
④如果某一点与另一类点中除一点以外都是否定关系，那么与这一点只能是肯定关系.
现在把这些原则具体操作于这个图上，就能把问题求解，请读者看图，不赘述.
这类问题的思想方法上升到图论中，已经可以用一种更抽象的术语“超图”来描述，也就是顶点集合，仍用V来表示，而超图的边是一种抽象的“广义边”，把原来简单边捆绑在一起形成的一种“捆绑的边”.在这个具体例题中，就是要找出一套捆绑边，每一捆绑边，捆着一个国别，一个名次，一个代号.找出三套捆绑边，每套与别的套之间没有公共的点，也就是超图
的匹配用了这种思想方法，去解决某些逻辑推理问题，变的非常快捷而准确了.
再看例子，
有A、B、C三位大学生，一位北京人，一位上海人，一位广州人，每人的业余爱好只是足球、围棋和歌舞三种中的一种.已知：A不喜欢足球，B 不喜欢歌舞；喜欢足球的不是上海人；喜欢歌舞的是北京人；B不是广州人.请判断三市人的代号（指A、B、C）及爱好.
现在把此逻辑推理问题，转化为图论中的“捆绑边”匹配问题，大家不难把此题的图和我们最初的例比较，它们完全“同构”.
答为：B上海人，喜欢围棋；A喜欢歌舞，北京人；C喜欢足球，广州人.
关于匹配问题本身，有很多问题和方法已经充分研究和圆满解决，并找到了可以利用电脑解决的很好的算法.例如从二分图的求最大匹配算法发展出称之为“交错路”的方法，直到网络上带权的最大（或最小）匹配。
习题八
1.小明、小强、小华三人参赛迎春杯，分别来自金城、沙市、水乡，并分获一、二、三等奖.现知：
①小明不是金城选手；
②小强不是沙市选手；
③金城选手不是一等奖；
④沙市选手得二等奖；
⑤小强不是三等奖；问小华是何处选手，得几等奖？
2.下面是一个一般的图，有9个点，V=｛v1，v2，…，v9｝，有16条边，E＝｛e1，e2，…，e16｝.请找一个边数最多的匹配（即找一个最大匹配）.
3.有一个残缺棋盘（下图中的白格部分）.问是否可用1×2的骨牌将它完全覆盖？
4.一张8×8的黑白相间国际象棋盘，任意挖去一个黑格和另一处的一个白格，剩下的62格残盘，可否用31张1×2骨牌完全覆盖？。
