图的匹配与覆盖问题

计算机系统应用　ｈｔｔｐ：／／ｗｗｗ．ｃ－Ｓ－ａ．ｏｒｇ．ｃｎ　２０１２年第２１卷第３期　

一种求解二部图最大匹配问题新算法及其应用①　

唐敏　，关健　，邓国强　，王海刚２　

‘（桂林电子科技大学数学与计算科学学院，桂林５４１００４）　（桂林电子科技大学商学院，桂林５４１００４）　

摘　要：提出了解决二部图最大匹配问题的分层网络优化算法，并应用新算法对排课问题进行求解。定义了　

分层网络的概念及匹配的规则，结合广度优先搜索策略生成分层网络体系，然后按网络逆序找出最大匹配。　

实验表明，算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果，具备良好　的性能。　

关键词：分层网络；二部图；最大匹配：排课问题　

Ａ　Ｎｅｗ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｓｏｌｖｉｎｇ　Ｍａｘｉｍｕｍ　Ｍａｔｃｈｉｎｇ　Ｐｒｏｂｌｅｍ　ｏｆ　Ｂｉｐａｒｔｉｔｅ　Ｇｒａｐｈ　

ＴＡＮＧ　Ｍｉｎ　，ＧＵＡＮ　Ｊｉａｎｇ　，ＤＥＮＧ　Ｇｕｏ－Ｑｉａｎｇ　，ＷＡＮＧ　Ｈａｉ－Ｇａｎｇ‘　

（Ｓｃｈｏｏｌ　ｏｆＭａｔｈｅｍａｔｉｃｓ＆Ｃｏｍｐｕｔｉｎｇ　Ｓｃｉｅｎｃｅ。Ｇｕｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＥｌｅｃｔｒｏｎｉｃ　Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕｉｌｉｎ　５４１００４，Ｃｈｉｎａ）　（Ｓｃｈｏｏｌ　ｏｆＢｕｓｉｎｅｓｓ，Ｇｕｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＥｌｅｃｔｒｏｎｉｃ　Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕｉｌｉｎ　５４１００４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍａｘｉｍｕｍ　ｍａｔｃｈｉｎｇ　ｏｆ　Ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈ　ｂａｓｅｄ　ｏｎ　ｌａｙｅｒｅｄ　ｎｅｔｗｏｒｋ　ｍｏｄｅ１．　

Ｔｉｍｅｔａｂｌｅ　Ｐｒｏｂｌｅｍｓ　ａｒｅ　ｓｏｌｖｅｄ　ｂｙ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ．Ａ　ｍａｔｃｈｉｎｇ　ｒｕｌｅ　ｆｏｒ　ｌａｙｅｒｅｄ　ｎｅｔｗｏｒｋｓ　ｉｓ　ｄｅｆｉｎｅｄ　ａｎｄ　ｐｒｏｐｏｓｅｄ　ａ　

第九讲 二分图匹配问题

一、问题

设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。即回溯法，但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。

二 、算法分析

二分图的最大匹配有2种实现，网络流和匈牙利算法。

1.匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若边集合P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

2.由增广路径的定义可以推出下述三个结论：

（1）. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。

（2）. P经过“取反操作”（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。

（3）. M为G的最大匹配当且仅当不存在相对于M的增广路径。

3.从而可以得到求解最大匹配的匈牙利算法：

(1)置M为空；

(2)找出一条增广路径P，通过“取反操作”获得更大的匹配M’代替M；

(3)重复(2)操作直到找不出增广路径为止；

根据该算法，可以选择深搜或者广搜实现，下面给出易于实现的深度优先搜索（DFS）实现。

三、实现

1. 匈牙利算法的算法轮廓

bool 寻找从k出发的对应项出的可增广路{

while(j与k邻接){

基于二分图完美匹配算法的变换序列问题

图论模型起源于“哥尼斯堡的七桥问题”，是指对一些客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程。在建立图论模型的过程中，和几何模型、运筹学模型一样，也需要用到集合、映射、函数等基本的数学概念和工具。如何建立问题的图论模型并没有通用的准则。在复杂的实际问题中，有时我们会感到难以建立适当的模型，这些都需要我们有丰富的经验，灵活的思维以及良好的创造力。

一、变换序列问题描述

对于0，1，…，N-1的N个整数，给定一个距离序列D0，D1，…，DN-1，定义一个变换序列T0，T1，…，TN-1使得每个i，Ti的环上距离等于Di 。一个合法的变换序列应是0，1，…，N-1的一个排列，任务是要求出字典序最小的那个变换序列。

二、图论模型建立

问题抽象成图论模型：建立一个二分图，X集合每个顶点代表0，1，…，N-1的N个整数，Y集合每个顶点为对应的N个整数。X集合的第i个顶点向其环上距离为Di的Y集合中的两个顶点连一条边。

三、图的有关理论

二分图：设X，Y都是非空有限顶点集，且X∩Y = ，称G=（X，Y，E）为二分图。

正则图：定义2若二分图G=（X，Y，E）的每一个顶点的都与k条边相连，则称G为k阶正则图。

匹配：图G（V，E）中若干互不相邻的边组成的集合称为图G的一个匹配。

最大匹配：给定一个二分图G（V，E），在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

完全匹配（或称完备匹配）：如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

完美匹配：若一个匹配既是一个二分图G=（X，Y，E）中X到Y的完全匹配，又是Y到X的完全匹配，则称这个匹配是二分图G=（X，Y，E）的完美匹配。（此时|X|=|Y|）

增广路的定义（也称增广轨或交错轨）：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边（即已匹配和待匹配的边）在P上交替出现，则称P为相对于M的一条增广路径。由增广路的定义可以推出下述四个结论：第一，P的路径长度必定为奇数，第一条边和最后一条边都不属于M。第二，不断寻找增广路可以得到一个更大的匹配M’，直到找不到更多的增广路。第三，M为G的最大匹配当且仅当不存在相对于M的增广路径。第四，最大匹配数M+最大独立数N=总的结点数。

各种图论模型及其解答

摘要：

本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。

符号约定：

Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。

一、引言

图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下：

原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解

整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况：

①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图

②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图

如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。

综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。

例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友

M：点表示人，连线表示当且仅当该两个人是朋友

A：问题转化为任何一个图一定存在两个顶点的度相等

二、图论模型

接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。

2.1 偶图模型 凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。