图论课件匈牙利算法与最优匹配算法

格式：ppt
大小：838.50 KB
文档页数：31

下载文档原格式

/ 31

匈牙利算法解决二分图最大匹配

匈⽛利算法解决⼆分图最⼤匹配预备知识匈⽛利算法是由匈⽛利数学家Edmonds于1965年提出，因⽽得名。

匈⽛利算法是基于Hall定理中充分性证明的思想，它是⼆分图匹配最常见的算法，该算法的核⼼就是寻找增⼴路径，它是⼀种⽤增⼴路径求⼆分图最⼤匹配的算法。

⼆分图⼆分图⼜称作⼆部图，是图论中的⼀种特殊模型。

设G=(V,E)是⼀个⽆向图，如果顶点V可分割为两个互不相交的⼦集(A，B)，并且图中的每条边（i，j）所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i in A，j in B)，则称图G为⼀个⼆分图。

匹配在图论中，⼀个图是⼀个匹配（或称独⽴边集）是指这个图之中，任意两条边都没有公共的顶点。

这时每个顶点都⾄多连出⼀条边，⽽每⼀条边都将⼀对顶点相匹配。

例如，图3、图4中红⾊的边就是图2的匹配。

图3中1、4、5、7为匹配点，其他顶点为⾮匹配点，1-5、4-7为匹配边，其他边为⾮匹配边。

最⼤匹配⼀个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最⼤匹配。

图 4 是⼀个最⼤匹配，它包含 4 条匹配边。

任意图中，极⼤匹配的边数不少于最⼤匹配的边数的⼀半。

完美匹配如果⼀个图的某个匹配中，所有的顶点都是匹配点，那么它就是⼀个完美匹配。

显然，完美匹配⼀定是最⼤匹配，但并⾮每个图都存在完美匹配。

最⼤匹配数：最⼤匹配的匹配边的数⽬。

最⼩点覆盖数：选取最少的点，使任意⼀条边⾄少有⼀个端点被选择。

最⼤独⽴数：选取最多的点，使任意所选两点均不相连。

最⼩路径覆盖数：对于⼀个DAG（有向⽆环图），选取最少条路径，使得每个顶点属于且仅属于⼀条路径，路径长可以为0（即单个点）定理1：Konig定理——最⼤匹配数 = 最⼩点覆盖数定理2：最⼤匹配数 = 最⼤独⽴数定理3：最⼩路径覆盖数 = 顶点数 - 最⼤匹配数匈⽛利算法例⼦为了便于理解，选取了dalao博客⾥找妹⼦的例⼦：通过数代⼈的努⼒，你终于赶上了剩男剩⼥的⼤潮，假设你是⼀位光荣的新世纪媒⼈，在你的⼿上有N个剩男，M个剩⼥，每个⼈都可能对多名异性有好感（惊讶，-_-||暂时不考虑特殊的性取向）如果⼀对男⼥互有好感，那么你就可以把这⼀对撮合在⼀起，现在让我们⽆视掉所有的单相思（好忧伤的感觉，快哭了），你拥有的⼤概就是下⾯这样⼀张关系图，每⼀条连线都表⽰互有好感。

二分图的最大匹配、完美匹配和匈牙利算法

二分图的最大匹配、完美匹配和匈牙利算法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 是一个完美匹配。

显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。

但并非每个图都存在完美匹配。

举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。

是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。

如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。

基本概念讲完了。

图论的配对问题课件

x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
M={(x1,y1 ),(x3,y5),(x5,y3)}
V1={x2,x5,x3}；V2 ={y3,y5}；
M=ME(P)={(x1,y1 ),(x2,y图3论),(的x配3对,y问2题),( x5,y5)}
（2）若X已经饱和，结束；否则转（3）；解（（y34∈））N在若(VXN1中()V-V找1)2=一V2个则非停饱止和，点否x则0，任V选1=一{x点0}，V2={}
图论的配对问题
匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题” 中有重要作用。假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生配对？
类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？
V1={x2},V2=空集
N(V1)={y2, y3}
图论的配对问题
解（∪条（5）从{2）z若}x0】y，到已yV饱的2和=可V，增2∪M广{中道y}必路；有P转，(y（,对z)4之；）进作】行【，增否V广1则=；V【1转求一
x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
M={(x1,y1 ),(x3,y5),(x5,y3)} V1={x2},V2=空集 V1=V1∪{x5}={x2,x5}； V2=V2∪ {y3} ={y3}
x1
x2
x3
x4
x5
y1
y2
y3
y4

匈牙利算法示例ppt

(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ． (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。
•
非标准型的指派问题：
匈牙利法的条件是：模型求最小值、效率cij≥0。当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式， 1、人数和事数不相等的指派问题：人少事情多，虚拟 “人”，做各事的费用系数为0；人多事情少，虚拟 “事”，各人做的费用系数为0。 2、对于求极大化的问题，只要系数矩阵变换为B＝（mcij）nn，仍可利用匈牙利算法进行求解。 3、一个人可以做几件事情的指派问题：可以将该人化作相同的几个“人”来接受指派，费用一样。 4、某事一定不能由某人做的指派问题，费用系数为“ M” 然后用匈牙利法来求解。
2 0 2 4 5
-0 -0 -0 -0 -0
第二步：进行试指派，以寻求最优解。在 (bij) 中找尽可能多的独立 0 元素，若能找出 n 个独立 0元素，就以这 n个独立 0元素对应解矩阵 (xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：
0 0 1 0 0
或
0 0 0 0 1
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0
解矩阵得到2个最优指派方案；（1）甲-B，乙-C，丙--E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C，戊-A。所需时间为minz=7+6+9+6+4=32

二分图的最大匹配—匈牙利算法

⼆分图的最⼤匹配—匈⽛利算法【基本概念】：⼆分图：⼆分图⼆分图⼜称作⼆部图，是图论中的⼀种特殊模型。

设G=(V,E)是⼀个⽆向图，如果顶点V可分割为两个互不相交的⼦集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为⼀个⼆分图。

⽆向图G为⼆分图的充分必要条件是，G⾄少有两个顶点，且其所有回路的长度均为偶数。

最⼤匹配最⼤匹配：给定⼀个⼆分图G，在G的⼀个⼦图M中，M的边集中的任意两条边都不依附于同⼀个顶点，则称M是⼀个匹配. 选择这样的边数最⼤的⼦集称为图的最⼤匹配问题，如果⼀个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配.最⼩覆盖：最⼩覆盖要求⽤最少的点（Ｘ集合或Ｙ集合的都⾏）让每条边都⾄少和其中⼀个点关联。

可以证明：最少的点（即覆盖数）＝最⼤匹配数最⼩路径覆盖：⽤尽量少的不相交简单路径覆盖有向⽆环图Ｇ的所有结点。

解决此类问题可以建⽴⼀个⼆分图模型。

把所有顶点i拆成两个：Ｘ结点集中的i 和Y结点集中的i',如果有边i->j，则在⼆分图中引⼊边i->j'，设⼆分图最⼤匹配为m,则结果就是n-m。

增⼴路（增⼴轨）：（增⼴轨）：增⼴路若P是图G中⼀条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的⼀条增⼴路径（举例来说，有A、B集合，增⼴路由A中⼀个点通向B中⼀个点，再由B中这个点通向A中⼀个点……交替进⾏）。

增⼴路径的性质：1 有奇数条边。

2 起点在⼆分图的左半边，终点在右半边。

3 路径上的点⼀定是⼀个在左半边，⼀个在右半边，交替出现。

（其实⼆分图的性质就决定了这⼀点，因为⼆分图同⼀边的点之间没有边相连，不要忘记哦。

）4 整条路径上没有重复的点。

5 起点和终点都是⽬前还没有配对的点，⽽其它所有点都是已经配好对的。

算法学习：图论之二分图的最优匹配(KM算法)

二分图的最优匹配（KM算法）KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。

基本原理该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。

设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。

在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。

KM算法的正确性基于以下定理：若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。

首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。

这个定理是显然的。

因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。

所以相等子图的完备匹配一定是二分图的最大权匹配。

初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。

如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。

我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。

这时我们获得了一棵交错树，它的叶子结点全部是X顶点。

现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。

也就是说，它原来属于相等子图，现在仍属于相等子图。

2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。

指派问题的匈牙利法ppt

判断就是否为最优解:圈起得零得个数就是否等于n。
确定调整行与列
在没有圈起得零所在行上打“√”; 在打“√”行中所有零所在得列打“√”; 在打“√”列中含有圈起零得行上打“√”, 反复执行2)与3)两步,直到不能打“√”为止; 用直线划去打“√”得列与不打“√”得行,没有
划去得行构成调整得行,划去得列构成调整列。
调整可行解得方法
在调整行中寻找最小得元素,将它作为调整量;
将调整行各元素减去调整量,对调整列中各元素加上调整量。
再次执行“圈零”与“划零”得操作,并循环以上得步骤,直到圈起得零数等于n为止。
匈牙利法解例3、3
时间矩阵
2 10 3 7
15
4
14
8
13 14 16 11
4
7
13
任务
人员
A
B
C
D
甲
6
7
11
2
乙
4
5
9
8
丙
3
1
10
4
丁
5
9
8
2
求解过程如下:
第一步,变换系数矩阵:
6 7 11 2 2
(cij
)
4 3
5 1
9 10
8 4 4 1
5 9 8 2 2
4 5 9 0 0 1 5 4 2 0 9 3 3 7 6 0
4 5 4 0 0 1 0 4 2 0 4 3 3 7 1 0
0元素,就以这n个独立0元素对应解矩阵(xij)中得元素为1, 其余为0,这就得到最优解。找独立0元素,常用得步骤为:
(1)从只有一个0元素得行(列)开始,给这个0元素加圈, 记作◎ 。然后划去◎ 所在列(行)得其它0元素,记作Ø ; 这表示这列所代表得任务已指派完,不必再考虑别人了。

ppt19 匈牙利算法与最优匹配算法

y4
y5
(c) y2为M非饱和点，加上y2和边x3y2生长树H。此时，置M=MΔE(P)=｛x1y1, x2y3, x3y2｝
x1 y2 x2 x3 x4 x5
x3
y1
y2
y3 G=(X, Y)
y4
y5 10
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
15
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
定义2 设G=(X, Y), 若对任意的x ∈X, y ∈Y,有：
l ( x ) l ( y ) w ( xy )
称 l 是赋权完全偶图G的可行顶点标号。对于任意的赋权完全偶图G，均存在G的可行顶点标号。事实上，设：
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
2) 若 T N (S ) 令y ∈N(S) – T, 则在树H中存在点x与y邻接。因为H的所有点，除u外，均在M下配对。所以，或者x = u，或者x与H的某 xy M 一顶点配对，但无论哪种情况，都有
w ( M *)
eM *

w(e)
vV ( G )

l (v )
又设M是G的任一完美匹配，则：
w( M )
eM
w(e)
l (v )
vV ( G )
所以，w (M*)≥w (M)。即M*是G的最优匹配。
18
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
w ( xy ), 若 x X , l ( x ) max yY l ( y ) 0, 若 y Y .

算法学习：图论之用匈牙利算法求二分图的最大匹配

用匈牙利算法求二分图的最大匹配什么是二分图，什么是二分图的最大匹配，这些定义我就不讲了，网上随便都找得到。

二分图的最大匹配有两种求法，第一种是最大流（我在此假设读者已有网络流的知识）；第二种就是我现在要讲的匈牙利算法。

这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。

匈牙利算法其实很简单，但是网上搜不到什么说得清楚的文章。

所以我决定要写一下。

最大流算法的核心问题就是找增广路径（augment path）。

匈牙利算法也不例外，它的基本模式就是：可见和最大流算法是一样的。

但是这里的增广路径就有它一定的特殊性，下面我来分析一下。

（注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。

每条边也不需要有方向。

）图1 图2图1是我给出的二分图中的一个匹配：［1，5］和［2，6］。

图2就是在这个匹配的基础上找到的一条增广路径：3->6->2->5->1->4。

我们借由它来描述一下二分图中的增广路径的性质：(1)有奇数条边。

(2)起点在二分图的左半边，终点在右半边。

(3)路径上的点一定是一个在左半边，一个在右半边，交替出现。

（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。

）(4)整条路径上没有重复的点。

(5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。

（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。

）(6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。

（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。

而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。

）(7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。

二分图匹配――匈牙利算法和KM算法简介.

KM算法
对于任意的G和M，可行顶标都是存在的： l(x) = maxw(x,y) l(y) = 0 欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹配时怎么办？1957年（居然比匈牙利算法早？？？），Kuhn和Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。
二分图匹配
匈牙利算法和KM算法简介
二分图的概念
二分图又称作二部图，是图论中的一种特殊
模型。设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则 1 2 3 4 5 称图G为二分图。
1
2
3
4
最大匹配
给定一个二分图G，在G的一个子图M中，M
的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
匈牙利算法
求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P 上交替出现，则称P为相对于M的一条增广路径。
KM算法
穷举的效率－n！，我们需要更加优秀的算法。定理：设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i] 表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j] 成立，则M是图G的一个最佳匹配。证明很容易。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
本次课主要内容
匈牙利算法与最优匹配算法 (一)、匈牙利算法 (二)、最优匹配算法
1
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
(一)、匈牙利算法
1、偶图中寻找完美匹配
(4) 若y是M饱和的，设yz ∈ M,置S=S∪｛z｝, T=T∪ ｛y｝,转(3);否则，存在(u, y)交错路是M可扩路P,置 M=MΔE(P),转(1).
(5) 若X-S=Φ,停止；否则转(2).
12
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
(二)、最优匹配算法
11
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
偶图中寻找最大匹配算法：
设M是G=(X, Y)的初始匹配。
(1) 置S=Φ, T=Φ;
(2) 若X-S已经M饱和，停止；否则，设u是X-S中的一非饱和顶点，置S=S∪｛u｝。
(3) 若N(S)=T,转(5)；否则，设y ∈N(S)-T。
称Gl = G [El]为G的对应于l 的相等子图。
例如，设如下矩阵是赋权完全偶图G的权值矩阵并注明了一种可行顶点标号l
3 5 5 4 1 5
2
2
0
2
2
2
W 2 4 4 1 0 4
0
1
1
0
0
1
1 2 1 3 3 3
0 0 0 00
x1 x2 x3
x4
x5
y1 y2 y3
y4
y5
G l=(X, Y)
2 、可行顶点标号与相等子图
13
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
定义2 设G=(X, Y), 若对任意的x ∈X, y ∈Y,有：
l(x) l( y) w(xy)
称 l 是赋权完全偶图G的可行顶点标号。对于任意的赋权完全偶图G，均存在G的可行顶点标号。事实上，设：
l ( x)
max yY
w( xy),
若x
X
,
l( y) 0,若y Y.
则 l 是G的一个可行顶点标号。
14
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
定义3 设 l 是赋权完全偶图G=(X, Y的可行顶点标号，令：
El xy E(G) l(x) l( y) w(xy)
2
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
定义1 设G=(X, Y), M是G的匹配，u是M非饱和点。称树H是G的扎根于点u的M交错树,如果：
1) u ∈V(T)； 2) 对任意v ∈V(T), (u, v)路是M交错路。
x1
x2 x3
x4
y2
x4
0.5
00
1 0.8
0.6 0.4 x 0.2
若y为M非饱和的，加上顶点y和边xy生长H，得到情形2. 找到一条M可扩路，可以对匹配进行一次修改，过程的反复进行，最终判定G是否有完美匹配或者求出完美匹配。根据上面讨论，可以设计求偶图的完美匹配算法。 (4) 、偶图完美匹配算法——匈牙利算法。设M是初始匹配。 (a) 、若M饱和X所有顶点，停止。否则，设u为X中M 非饱和顶点，置S=｛u｝,T=Φ; (b) 、若N(S)=T, 则G中不存在完美匹配。否则设 y ∈N(S) – T.
y2
x5
x4
x2
y4
y3
u
扎根 u 的M交错树H
情形2 H包含除u外的M非饱和点。
y2
x4
x2
y4
y3
u
扎根 u 的M交错树H
4
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
对于情形1，令S=V(H)∩X, T=V(H)∩Y,显然： T N(S)
1) 若N(S)=T, 由于S - ｛u｝中点与T中点配对，所以有： |T|=|S|-1, 于是有： |N(S)| = |S|-1< |S|.由Hall定理，G中不存在完美匹配；
x3
y2
x4
(b ) N(S)= ｛y2, y3｝ ≠T，取y3 ∈N(S)-T
9
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
(b ) N(S)= ｛y2, y3｝ ≠T，取y3 ∈N(S)-T
x1 x2 x3
x4
x5
y1 y2 y3
y4
y5
G=(X, Y)
解：给出初始可行顶点标号 l 为：
3 5 5 4 1 5
2
2
0
2
2
2
W 2 4 4 1 0 4
0 1 1 0 0 1
1 2 1 3 3 3
0 0 0 00 19
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
对应的相等子图Gl为：
x1 x2 x3
x4
2) 若 T N(S)
令y ∈N(S) – T, 且x与y邻接。因为H的所有点，除u外，均在M下配对。所以，或者x=u，或者x与H的某一顶点配对，这样，有 xy M
若y为M饱和的，设yz ∈M,则加上顶点y及z和边xy与yz生长H，得到情形1；
5
1
0.5 n 0
0.5
1 2 1.5 t1
yT
17
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
l(v) l , v S lˆ l(v) l , v T
l(v), 其它
给出新的可行顶点标号。
(3) 在NGl (S)-T中选择点y。若y是M饱和的，yz ∈M,
则置S=S∪｛z｝,T=T∪｛y｝转(2)。否则，设P是Gl中M 可扩路，置M=MΔE(P),转(1).
由 lˆ l(v) l , v T 得新标号为：
l(v), 其它
3 5 5 4 1 4
2
2
0
2
2
2
W 2 4 4 1 0 3
0
1
1
0
0
0
1 2 1 3 3 3
0 1 1 00
x1 x2 x3
x4
x5
y1 y2 y3
y4
y5
G l=(X, Y)
22
1
0.5 n 0
(1) 、问题设G=(X, Y), |X|=|Y|, 在G中求一完美匹配M.
(2) 、基本思想从任一初始匹配M0出发，通过寻求一条M0可扩路P，令 M1=M0ΔE(P), 得比M0更大的匹配M1(近似于迭代思想)。 (3) 、M可扩扩路的寻找方法
1965年，Edmonds首先提出: 用扎根于M非饱和点u的M 交错树的生长来求M可扩路。
பைடு நூலகம்x4
x5
(2) NGl (S) y2, y3 T
y1 y2 y3
y4
y5
(3) 取：y2 NGl (S ) T
G l=(X, Y)
y2为饱和顶点，y2x1 ∈M,于是： S x1, x4,T y2
(2) NGl (S) y2, y3 T
(3) 取：y3 NGl (S ) T
y3为饱和顶点，y3x3 ∈M,于是：S x1, x3, x4,T y2, y3
6
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
(c ) 若y为M饱和点，且yz ∈M, 置S=S∪｛z｝, T=T∪｛y｝, 转(b)。否则，设P为M可扩路，置M1=MΔE(P)，转(a).
例1 讨论下图G=(X, Y)是否有完美匹配。
x1 x2 x3
x4
21
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
(2) NGl (S) y2, y3 T
于是修改标号：
x1 x2 x3
x4
x5
l
minl(x) l( y) w(xy) 1 xS
yT
y1 y2 y3
y4
y5
G l=(X, Y)
l(v) l , v S
x1 x2 x3
x4
x5
y1 y2 y3
y4
y5
G=(X, Y)
(c) y2为M非饱和点，加上y2和边x3y2生长树H。此时，置M=MΔE(P)=｛x1y1, x2y3, x3y2｝
x1 x2 x3
x4
x5
y2
x3
y1 y2 y3
y4
y5
G=(X, Y)
8
1