图论课件第五章 匹配与因子分解

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

图论及其应用

应用数学学院

1

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

第五章 匹配与因子分解

主要内容 一、偶图的匹配问题 二、图的因子分解 三、匈牙利算法与最优匹配算法 教学时数

安排6学时讲授本章内容

2

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

本次课主要内容

偶图的匹配问题

(一)、图的匹配与贝尔热定理 (二)、偶图的匹配与覆盖 (三)、托特定理

3

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

(一)、图的匹配与贝尔热定理

1、图的匹配相关概念 (1)、匹配 M--- 如果M是图G的边子集(不含环），且 M中的任意两条边没有共同顶点，则称M是G的一个匹 配或对集或边独立集。

如果G中顶点v是G的匹配 M中某条边的端点，称它 为M饱和点，否则为M非饱和点。

M1=｛v6v7｝

v7

M2=｛v6v7, v1v8｝

M3=｛v6v7, v1v8, v3v4｝ M1,M2,M3等都是G的匹配。

v6

v5 v8

v1

v2

v4 G

v3

4

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

(2)、最大匹配 M--- 如果M是图G的包含边数最多的 匹配，称M是G的一个最大匹配。特别是，若最大匹配 饱和了G的所有顶点，称它为G的一个完美匹配。

G的一个完美匹配 G的一个 最大匹配

注：一个图G不一定存在完美匹配。

5

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

(3)、M交错路--- 如果M是图G的匹配，G中一条由M 中的边和非M中的边交错形成的路，称为G中的一条M 交错路。特别地，若M交错路的起点与终点是M非饱和 点，称这种M交错路为M可扩路。 在下图中：

v6 v5 v8 v7 v1 v2

v4 G

v3

设M=｛v7v8 , v3v4｝，则： 路v6v7v8v3v4与v1v7v8v2都是M交错路。其中后者是M 可扩路。

6

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

2、贝尔热定理 定理1 (贝尔热，1957) G的匹配M是最大匹配，当且 仅当G不包含M可扩路。 证明：“必要性” 若G包含一条M可扩路P,则可令该可扩路为：

P v1 v v 2 v 2 3

k 2

v 1k

显然，P中M中的边比非M中的边少一条。于是作新 的匹配M1,它当中的边由P中非M中边组成。M1中边比 M中多一条，这与M是G的最大匹配矛盾。 “充分性” 若不然，设M1是G的一个最大匹配，则|M1|>|M|。

7

图论课件

1

0 .5 n 0

0 .5

1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6 1

令H = M1ΔM。 容易知道：G[H]的每个分支或者是由M1与M中边交 替组成的偶圈，或者是由M1与M中边交替组成的路。 在每个偶圈中，M1与M中边数相等；但因|M1|>|M|， 所以，至少有一条路P，其起点和终点都是M非饱和点， 于是，它是G的一条M可扩路。这与条件矛盾。 注：贝尔热定理给我们提供了扩充G的

图论课件

图论课件

图论课件

图论课件

图论课件

图论课件

图论课件

图论课件