图论-第5章课件

第五章匹配与因子分解.第五章匹配与因子分解.1§5.1匹配

定义设M是图G的一个不包含环的边子集，且M中任意两条边在G中

均互不相邻，则称M为

G的一个匹配（对集）。M中一条边的两个端点称为在M下是配对的。设M为

G的一个匹配，对v∈V(G)，若v是M中某边的一个端点，则称v为M饱和点，否则称为M非饱和点。若图G中的点均为M饱和点，则称M为G的完美匹配。若G中没有另外的匹配M’，使得|M|<|M’|,则称M为G的最大匹配（含边数最多的匹配）。

1、图的匹配相关概念.2§5.1匹配定义设M是图G的一个不包对M2，点v1是饱和点，点v2是非饱和点。v1v2v3v4v8v5v7v6

例1中的M1

和M2既不是最大匹配，也不是完美匹配，而M3是最大匹配，也是完美匹配。例1设图G为:G的匹配有：M1={v1v8}M2={v1v3，v8v4，v7v5}M3={v1v2，v8v3，v7v4，v6v5}等等.3对M2，点v1是饱和点，点v2是非饱和点。v1v2v3v4

关系：

(1)

完美匹配必是最大匹配，而最大匹配不一定是完美匹配。(2)

一个图的最大匹配必存在，但完美匹配不一定存在。(3)

图G存在完美匹配的一个必要条件是G的点数为偶。G的一个最大匹配G的一个完美匹配.4关系：(2)一个图的最大匹配必存在，但完美匹配不一定

设M为图G的一个匹配可看出：对Г3，若取Г3中非M的边再连同

M的不在Г3中的边组成M’，则M’的边数比

M的边数多，这表明

M不是该图的最大匹配。M交错路：G中由M中的边与非M中的边交替组成的路。M可扩路：起点与终点均为M非饱和点的M交错路。例如，取M={红边}Г1Г2Г3M交错路M可扩路.5设M为图G的一个匹配可看出：对Г3，若取Г3中非M定理1（Berge,1957）

G的匹配M是最大匹配当且仅当

G不含M可扩路.（等价于：M不是最大匹配当且仅当G含M可扩路）证明：证明其等价结论。则M′是G的匹配，且|M′|=|M|+1，因而M就不是最大匹配。

2、贝尔热定理充分性：设M是G的匹配，并假设G包含M可扩充路

v0v1…v2m+1,定义M′

E为M′=(M\{v1v2,v3v4,…,v2m-1v2m})∪{v0v1,v2v3,…,v2mv2m+1}.6定理1（Berge,1957）G的匹配M是最大匹配H的每个顶点在H中具有的度是1或2。因为它最多只能和M的一条边以及M′的一条边相关联，由（1）式，M′包含的边多于M的边，因而H中必定有的一条路P,其边始于M′且终止于M′，因此P的起点和终点在H中被M′所饱和，在图G中就是M非饱和的。于是P是G的一条M可扩路。

必要性：假设M不是最大匹配，且令M′是G的最大匹配，则

|M′|>|M|(1)置H=G[M△M′]，这里M△M′表示M和M′的对称差。因此H的每个分支或是由M和M′中的边交错组成的偶圈，或是由M和M′中的边交错组成的路。取M={红边},M′={白边}H中可能包含的子图：.7H的每个顶点在H中具有的度是1或2。因为它最多只能和M的一

贝尔热(1926---2002)法国著名数学家。他的《无限图理论及其应用》(1958)是继哥尼之后的图论历史上的第二本图论专著。他不仅在图论领域做出了许多贡献，而且四处奔波传播图论，推动了图论的普及和发展。1993年，他获得组合与图论领域颁发的欧拉奖章。贝尔热在博弈论、拓扑学领域里也有杰出贡献。在博弈领域，他引入了Nash均衡之外的另一种均衡系统。Nash的生活被改编成电影《美丽的心灵》，获02年奥斯卡金像奖。贝尔热对中国的手工艺很感兴趣。他也是一位象棋高手，还创作过小说《谁杀害了Densmore公爵》。.8贝尔热(1926---2002)法国著名数学家。他§5.2偶图的匹配与覆盖例：现有三个课外小组：物理组，化学组和生物组，有五个学生s1,s2,s3,s4,s5。已知s1,s2为物理组成员；s1,s3,s4为化学组成员；s3,s4,s5为生物组成员。问：在s1,s2,s3,s4,s5中选三位组长，不兼职，能否办到？1、问题的引出解：用c1,c2,c3分别表示物理组、化学组和生物组。令V1={c1,c2,c3}， V2={s1,s2,s3,s4,s5}以V1，V2为互补结点子集，以E={(ci,sj)|ci∈V1,sj∈V2且ci中有成员sj}为边集，构造图。c1c2c3s1s2s3s4s5V1V2.9§5.2偶图的匹配与覆盖例：现有三个课外小组：物理组取图G的一个顶点子集S，令

N(S)={v|存在u∈S，且v与u相邻}称N(S)为S的邻集。取S={v1,v2}，v1v2v3v4v8v5v7v6例如图中2、Hall定理（相异性条件）则N(S)={v8,v3,v1,v2}.10取图G的一个顶点子集S，令取S={v1,v2}，定理2（Hall，1935）设G为具有二分类（X,Y）的偶图，则G包含饱和X的每个顶点的匹配当且仅当

|N(S)|≥|S|

（2.1）对所有S

X

成立.证明

必要性：已知G包含匹配M，它饱和X的每个顶点。充分性：已知G是满足（2.1）式的偶图，假设M*是G的最大匹配，且M*不饱和X的所有顶点。设u是X的一个M*非饱和点，并设Z={v|v∈V(G)，且v通过M*交错路与u连接}设S是X的子集。由于S的顶点在M下和N(S)中的相异顶点配对，显然有|N(S)|≥|S|

。x1x2x3y1y2y3y4y5XY.11定理2（Hall，1935）设G为具有二分类（X,Y）的置S=Z∩X和

T=Z∩Y（见图）由于M*是最大匹配，从上节定理1可知：u为Z中唯一的M*非饱和点(否则将含M*可扩路)

。且任意一对配对点v和w,若v∈S,则必w∈T,反之亦然.因此SuT

|T|=|S|-1

（2.2）又因N(S)中每个顶点v均由一个M*交错路连接于u，故v∈Z,从而v∈T,这表明N(S)

T,于是有T=N(S)

(2.3)

Z={v|v∈V，且v通过M*交错路与u连接}

想推出|N(S)|<|S|

例：vv1v2…vmu,其中u为非饱和点而且

T

N(S)

。vx2v1x3考虑：

P=vv1v2…vmu，vm∈T，uvm不在M*中若v

∈S，P为M*交错路，则：

下证N(S)

Tvv1一定在M*中.12置S=Z∩X和由于M*是最大匹配，从上由（2.2）式和（2.3）式推出|N(S)|=|T|=|S|-1<|S|

这与假定（2.1）式矛盾。所以M*饱和X的所有顶点.推论

若G是k正则偶图（k>0），则G有完美匹配。证明设G是具有二分类（X,Y）的k正则偶图(k>0)。首先有|X|=|Y|(习题1的9).

任取X的一个子集S，令E1={e|e∈E,并且e与S中的顶点关联}E2={e|e∈E,并且e与N(S)中的顶点关联}.13由（2.2）式和（2.3）式推出推论若G是k正则偶图（k因与S中的顶点关联的边必与N(S)中的顶点关联，所以E1

E2再根据定理2，可知G有一个饱和X的每个顶点的匹配M.E1={e|e∈E,并且e与S中的顶点关联}E2={e|e∈E,并且e与N(S)中的顶点关联}由于|X|=|Y|，所以M是完美匹配。

.14因与S中的顶点关联的边必与N(S)中的顶点关联，所注:(1)G=(X,Y)存在饱和X每个顶点的匹配也常说成存在由X到Y的匹配。

(2)Hall定理也可表述为：设G=(X,Y)是偶图，如果存在X的一个子集S,使得|N(S)|<|S|，那么G中不存在由X到Y的匹配。Hall定理也称为“相异性条件”。

(3)Hall定理也称为“婚姻定理”，表述如下：“婚姻定理”：在一个由r个女人和s个男人构成的人群中，1≦r≦s。在熟识的男女之间可能出现r对婚姻的充分必要条件是，对每个整数k(1≦k≦r),任意k个女人共认识至少k个男人。(5)Hall定理是在偶图中求最大匹配算法的理论基础，即匈牙利算法基础。

(4)Hall定理还可以表述为：偶图G=<V1,E,V2>中存在从V1到V2的匹配的充分必要条件是V1中任意k个结点至少与V2中的k个结点相邻，k=1,2,…,|V1|。.15注:(1)G=(X,Y)存在饱和X每个顶点的匹推论：设G=<V1,E,V2>是一个偶图。如果满足条件（1）V1中每个结点至少关联t条边；（2）V2中每个结点至多关联t条边；则G中存在从V1到V2的匹配。其中t为正整数。证明：由(1)知，V1中任意k个结点至少关联tk条边(1≤k≤|V1|)，偶图匹配存在条件——t条件：由(2)知，这tk条边至少与V2中k个结点相关联，于是V1中的k个结点至少与V2中的k个结点相邻接，因而满足相异性条件，所以G中存在从V1到V2的匹配。.16推论：设G=<V1,E,V2>是一个偶图。如果满足条件证图G的一个覆盖:指V(G)的一个子集K，使得G的每条边都至少有一个端点在K中。G的最小覆盖:G中点数最少的覆盖一个覆盖一个最小覆盖例

3、点覆盖与哥尼定理v1v2v3v4v5v6V1V2v1v2v3v5v6v7v8v4v9V1V2.17图G的一个覆盖:指V(G)的一个子集K，使得G的每条边都匹配与覆盖的关系:

设K是G的覆盖，M是G的匹配,则有理由:K至少包含M中每条边的一个端点。(1)|M|≤|K|,特别地,若M*是最大匹配，且是最小覆盖,则(2)

定理4

设M是匹配，K是覆盖，若|M|＝|K|，则M是最大匹配，且K是最小覆盖。证明

设M*是最大匹配,是最小覆盖，则由（2.4）式，

|M|≤|M*|≤≤|K|由于|M|＝|K|，所以|M|=|M*|,=|K|。

|M*|≤(2.4).18匹配与覆盖的关系:设K是G的覆盖，M是G的匹配,则哥尼(KÖnig，1884----1944))——第一本图论教材《有限图与无限图理论》（1936年）的撰写者。该书对青年学者产生了很大影响，推动了图论的进一步发展。在20多年时间里，它都是世界上唯一一本图论著作。直到1958年，法国数学家贝尔热(Berge）才出版专著《无限图理论及其应用》。哥尼早期学习拓扑学，但对图论兴趣特别大。他一直工作在布达佩斯工业大学。讲课很有激情，吸引了很多优秀学生转向图论研究。特别是，他把一起获得匈牙利国家高中数学竞赛一等奖的3个学生都吸引来研究图论，这3个学生是：ErdÖs,Gallai,Turan.都是伟大的数学家。哥尼1944年为免遭纳碎迫害，选择了自杀。.19哥尼(KÖnig，1884----1944))——(3)

定理5（Kǒnig，哥尼，1931）偶图中，最大匹配的边数等于最小覆盖的顶点数。证明设G是具有二分类（X,Y）的偶图，M*是G的最大匹配，用U表示X中的M*非饱和顶点的集，用Z表示由M*

交错路连接到U中顶点的所有顶点的集。置

S=Z∩X,T=Z∩Y。类似于定理2的证明，可知T中的每个顶点都是M*饱和的，并且N(S)＝T。定义=(X\S)∪T（见图）。SUT=N(S)X\S.20(3)定理5（Kǒnig，哥尼，1931）偶图中，最则G的每条边必然至少有一个端点在

中，因为否则就存在一条边，其一个端点在S中，而另一个端点在Y\T中，这与N(S)＝T相矛盾。于是是G的覆盖。并且显然有|M*|=由定理4，是最小覆盖。例1

矩阵的一行或一列统称为一条线。证明：包含了一个（0,1）矩阵（布尔矩阵）中所有〝1〞的线的最小条数，等于具有性质〝任意两个1都不在同一条线上〞的〝1〞的最大个数。.21则G的每条边必然至少有一个端点在中，因为否则就这样,此矩阵的第i行线包含1的个数就是G中点xi关联的边数，而第j列线包含1的个数就是G中点yj关联的边数，故包含了（0,1）矩阵中所有〝1〞的线的最小条数就是偶图G中的最小覆盖的点数。证明

将（0,1）矩阵对应一个具有二分类(X,Y)的偶图G,使其行代表X中的元素,列代表Y中的元素,且满足（注:对应后,1则代表边,G含有饱和X的每个点的匹配当且仅当Q中存在|X|个不同行不同列的1).22这样,此矩阵的第i行线包含1的个数就是G中点xi而（0,1）矩阵中任意两个都不在相同线上的若干个1，就是偶图G中的一个匹配。而具有上述性质的1的最大个数，就是偶图G中最大匹配的边数，由定理5，问题得证.例如,矩阵Q及其对应的偶图如下图。其最小覆盖是{x1,y2,y4}，故包含Q中所有1的线是Q的1行，第2、4列，共3条。

x1x2x3

x4y1y2y3y4.23而（0,1）矩阵中任意两个都不在相同线上的若干个1§5.3Tutte定理与完美匹配奇(偶)分支:图的有奇(偶)数个顶点的分支,我们用o(G)表示图G的奇分支的个数。定理5（Tutte）

G有完美匹配当且仅当

o(G－S)≤|S|,对所有S

V成立（3.1）推论

每个没有割边的3正则图都有完美匹配。例

彼得森图满足推论的条件（即没有割边的3正则图），故它有完美匹配.证明冗长，从略。.24§5.3Tutte定理与完美匹配奇(偶)分支:图的有奇

证明：设S是V的任意一个非空真子集，G1,G2,…,Gk是G-S的所有奇分支。mi(1≦i≦k)表示端点分属于S和Gi的边数。SG1G2Gkm1m2mk.证明：设S是V的任意一个非空真子集，G1,G2,…25

下面分析miSG1G2Gkm1m2mk在Gi中，其总度数为2|E(Gi)|。

在Gi中，其点在G中的总度数为3|V(Gi)|。所以：所以mi必然为奇数，但G无割边，所以mi≥3.这样：

由托特定理，G有完美匹配。.26下面分析miSG1G2Gkm1m2mk在Gi中，其注:有割边的3正则图不一定有完美匹配没有完美匹配有完美匹配.27注:有割边的3正则图不一定有完美匹配没有完美匹配有完美匹配§5.4因子分解一.1－因子分解图G的因子:

G的一个至少有一条边的生成子图；G的因子分解:将G分解为一些边不相交的因子,使这些因子的并即为G；n-因子：指n度正则的因子。n-因子分解：每个因子均为n-因子的因子分解，此时称G本身是n-可因子化的。.28§5.4因子分解一.1－因子分解图G的因子:G的如果一个图G能够分解为若干n因子之并，称G是可n因子分解的。图G1在上图中，红色边在G1中的导出子图，是G的一个一因子；红色边在G2中的导出子图，是G的一个二因子。图G2研究图的因子分解主要是两个方面：一是能否进行分解(因子分解的存在性),二是如何分解(分解算法)..29如果一个图G能够分解为若干n因子之并，称G是可n因

图的一个一因子实际上就是图的一个完美匹配的导出子图。一个图能够作一因子分解，也就是它能够分解为若干边不重的完美匹配的导出子图之并。

定理6-7：

K2n,k-正则偶图(k>0),可一因子分解。

定理6的证明：把K2n的2n个顶点编号为1，2，…,2n。作如下排列：2n132::n2n-12n-2::n+1.30图的一个一因子实际上就是图的一个完美匹配的导出子图图中，每行两点邻接，显然作成K2n的一个一因子。2n132::n2n-12n-2::n+1然后按照图中箭头方向移动一个位置，又可以得到K2n的一个一因子，不断作下去，得到K2n的2n-1个边不重的一因子，其并恰好为K2n。

例1将K4作一因子分解。1234K4→41231234.31图中，每行两点邻接，显然作成K2n的一个一因子。21234423143121234例2

将K3,3作1-因子分解

1231’2’3’K3,3定理7的证明：不断减去完美匹配解将X的点用数字1，2，3标记，而Y的点用1’，2’，3’来标记，用置换G来表示K3,3中X的点与Y的点间之匹配关系，则G1G2G3.1234423143121234例2将K3,3作1-因子32定理8具有H圈的三正则图可一因子分解。证明：先从三正则图G中抽取H圈，显然剩下边构成G的一个一因子。

注：定理8的逆不一定成立。例如：

上图是三正则图，且可以一因子分解，但不存在H圈。而3正则图的H圈是偶圈，可以分解为两个一因子。所以G可以分解为3个一因子。.33定理8具有H圈的三正则图可一因子分解。证明：先从三正则图G定理9若3-正则图有割边，则不可1-因子分解。回忆：推论

每个没有割边的3正则图都有完美匹配。定理5（Tutte）

G有完美匹配当且仅当

o(G－S)≤|S|,对所有S

V成立（3.1）证明：若不然，设G的三个一因子为G1,G2,G3。不失一般性，设割边e∈G2。则G-G1中每个点的度数均为2，所以e在G的某个圈中，这与e是G的割边矛盾。注：没有割边的三正则图可能也没有一因子分解，如彼得森图,尽管它存在完美匹配。.34定理9若3-正则图有割边，则不可1-因子分解。回忆：推论二.2－因子分解

如果一个图可以分解为若干2度正则因子之并，称G可以2因子分解。注意：G的一个H圈肯定是G的一个2因子，但是G的一个2因子不一定是G的H圈。2因子可以不连通。例如，在下图中：两个红色圈的并构成图的一个2因子，但不是H圈。

一个显然结论是：G能进行2因子分解，其顶点度数必然为偶数。(注意，不一定是欧拉图).35二.2－因子分解如果一个图可以分解为若干2度正其中Pi的第j点是vk，k=i+(-1)j+1

，并且所有下标取为整数1，2，…，2n（mod2n）。生成圈Hi

是由v2n+1联接于Pi的两个端点构成。证明为了在K2n+1中构成n个边不相交的生成圈，先标定它的点v1,v2,…,v2n+1。然后，在点v1,v2,…,v2n上构成n条路Pi如下：Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n定理10图K2n+1

是n个H圈的和。.36其中Pi的第j点是vk，k=i+(-

例3对K7作2因子分解。(n=3)

解：v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1vk，k=i+(-1)j+1

，并且所有下标取为整数1，2，…，2n（mod2n）。Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n.37例3对K7作2因子分解。(n=3)解：定理11完全图K2n是一个1-因子和n-1个H圈的和。定理12每一个没有割边的3度正则图是一个1-因子和一个2-因子的和。(由定理5的推论可证)例

彼得森图是一个1-因子和一个2-因子的和

注若没有割边的3度正则图中的2-因子是一些偶圈,则该图也是1-可因子化的.定理13一个连通图是2-可因子化的当且仅当它是偶数度正则的。.38定理11完全图K2n是一个1-因子和n-1个H圈的和。定三、荫度荫度图G分解为边不相交的生成森林的最少数目,记为σ(G)。例

σ(K4)=2σ(K5)

=3

把一个图分解为若干边不重的森林因子的和，称为图的森林因子分解。.39三、荫度荫度图G分解为边不相交的生成森林的最少数目,记为σ定理14令G是一个非平凡图，又令ms是G的任何一个有s个点的子图中边的最多数目，则σ(G)≥的证明因为若G有n个点，则在任何一个生成森林中边的最多数目是n－1。从而G的边不相交的生成森林至少有m/(n-1)个.但G的荫度是一个整数，所以σ(G)≥。对于子图H，显然有σ(G)≥σ(H)，故σ(G)≥。.40定理14令G是一个非平凡图，又令ms是G的任何一个有s个

例4求σ(K5)和σ(K3,3)..41例4求σ(K5)和σ(K3,3)..41拜内克给出了完全图和完全偶图的最小森林因子分解。

对于K2n，将其分解为n条路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,脚标按模2n计算。

对于K2n+1，先作n条路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,脚标按模2n计算。在每条路外添上点v2n+1的n个森林因子；然后，v2n+1与v1,v2,…,v2n分别相连接得一星图，这是G的最后一个森林因子。推论

完全图和完全偶图的荫度为.42拜内克给出了完全图和完全偶图的最小森林因子分解。例5分K7为生成森林的最小分解如下图所示。v7v1v6v2

v5v3

v4v7v1v6v2

v5

v3

v4v7v7

P117---118习题5：1(2)，2，3,4,5，7，8，9,13.43例5分K7为生成森林的最小分解如下图所示。v7人员分派问题：n个工人x1,x2,…,xn，n件工作y1,y2,…,yn。已知xi

能胜任

ki件工作，i=1，2，…,n。问能否存在一种工作安排方案，使每个人都能分配到他所能胜任的一件工作。假定每件工作只能一人做，若能，又如何安排？

建模：以工人和工作为点，当且仅当xi

能胜任工作

yj时则连线，得偶图G.于是一种符合要求的安排对应G中一个完美匹配。所以此问题实际上是求偶图的完美匹配问题.

进一步：若不要求人数与工作数相等，则问题是求偶图的饱和X的每个点的匹配问题，其中X是工人的集合；进一步，若问：能否存在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工作被分配，则问题为求偶图的最大匹配问题。§5.5最优匹配与匈牙利算法.44人员分派问题：n个工人x1,x2,…,xn，n件工

(一)、匈牙利算法

1、偶图中寻找完美匹配

(1)、问题

设G=(X,Y),|X|=|Y|,在G中求一完美匹配M.

(2)、基本思想

从任一初始匹配M0出发，通过寻求一条M0可扩路P，令M1=M0ΔE(P)（将可扩路中M0

与非M0

的边互换）,得到比M0更大的匹配M1。(3)、M可扩扩路的寻找方法1965年，Edmonds首先提出:用扎根于M非饱和点u的M交错树的生长来求M可扩路。.45(一)、匈牙利算法1、偶图中寻找完美匹配

定义1设G=(X,Y),M是G的匹配，u是X的M非饱和点。称树H是G的扎根于点u的M交错树,如果：

1)u∈V(H)；2)对任意v∈V(H),(u,v)路是M交错路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交错树扎根于M非饱和点u的M交错树的生长讨论：

假如扎根于M非饱和点u的M交错树为H。它有两种情形：.46定义1设G=(X,Y),M是G的匹配，u是X的

情形1除点u外，H中所有点为M饱和点，且在M上配对；x4ux2y4y3y2情形1x5

情形2H包含除u外的M非饱和点。x4ux2y4y3y2情形2

对于情形1，令S=V(H)∩X,T=V(H)∩Y,显然：

1)若N(S)=T,由于S–{u}中点与T中点配对，所以有：

|T|=|S|-1,于是有：|N(S)|=|S|-1<|S|.由Hall定理，G中不存在完美匹配；.47情形1除点u外，H中所有点为M饱和点，且在M上配

2)若

令y∈N(S)–T,则在树H中存在X中的点x与y邻接。因为H的所有点，除u外，均在M下配对。所以，或者x=u，或者x与H的某一顶点配对，但无论哪种情况，都有xux2y4y3y2扎根u

的M交错树Hx5yxux2y4y3y2扎根u

的M交错树Hx5y

当然，y可能为M饱和点，也可能为M非饱和点。令S=V(H)∩X,T=V(H)∩Y.482)若令y∈N(S)–T,则在树

若y为M饱和点，可设yz∈M,则加上顶点y及z和边xy与yz来生长H，得到情形1；xux2y4y3y2扎根u

的M交错树Hx5yz

若y为M非饱和点，加上顶点y和边xy来生长H，得到情形2.xux2y4y3y2扎根u

的M交错树Hx5y令S=V(H)∩X,T=V(H)∩Y.49若y为M饱和点，可设yz∈M,则加上顶点y及z和边

后一情况下找到一条M可扩路，可以对匹配进行一次修改，过程的反复进行，最终判定G是否有完美匹配或者求出完美匹配。

根据上面讨论，可以设计求偶图的完美匹配算法。

(4)、偶图完美匹配算法——匈牙利算法。

设M是初始匹配。H是扎根于M非饱和点u的交错树。令：S=V(H)∩X,T=V(H)∩Y。

(a)、若M饱和X所有顶点，停止。否则，设u为X中M非饱和顶点，置S=｛u｝,T=Φ;

(b)、若N(S)=T,则G中不存在完美匹配。否则设y∈N(S)–T.

(c)、若y为M饱和点，且yz∈M,置S=S∪{z},T=T∪{y},转(b)。否则，设P为M可扩路，置M1=MΔE(P)，转(a)..50后一情况下找到一条M可扩路，可以对匹配进行一次修改，

例1讨论下图G=(X,Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X,Y)

解：取初始匹配M=｛x1y1,x2y3｝(a)S=｛x3｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y).51例1讨论下图G=(X,Y)是否有完美匹配。x1

(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T(c)y2为M非饱和点，加上y2和边x3y2生长树H。此时，置M=MΔE(P)=｛x1y1,x2y3,x3y2｝x1x2x3x4x5y1y2y3y4y5G=(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y).52(b)N(S)=｛y2,y3｝,N(S(a)S=｛x4｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)

(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T

(c)y2为M饱和点，y2x3∈M。此时，置S=S∪｛x3｝={x3，x4}T=T∪｛y2｝。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx4y2x3.53(a)S=｛x4｝,T=Φ;x1x2x3x4x5(c)y3为M饱和点，x2y3∈M。此时，置S=S∪{x2｝={x2,x3,x4}T=T∪｛y3｝=｛y2,y3｝

。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx1x2x3x4x5y1y2y3y4y5G=(X,Y)

(b)N(S)=｛y2,y3｝=T，所以，G无完美匹配。

(5)、匈牙利算法复杂性分析.54(c)y3为M饱和点，x2y3∈M。此时，置S=S∪{1)、最多循环|X|次可以找到完美