图与网络分析Graph and Network Analysis

Ludong University

第六章 图与网络分析图与子图 图的连通性 树与支撑树 最小树问题 最大流问题 最小费用流问题

匹配问题 (Matching Problem)Ludong University 2

2012-10-25

基本概念匹配：图G中一组边的集合M,当图中的每个节点最多只与 M中的一条边关联，则称M为图G匹配。同M中的边关联的点 称为M-饱和点，否则称为M-非饱和点。

图6.5.1最大基数匹配

图6.5.2完美匹配

完美匹配：G的每一个点都是M-饱和点。 最大基数匹配：不存在另外一个对集M’,使得|M’|>|M|,其中 |M|表示的基数。2012-10-25 Ludong University 3

基本概念M-交错路：边在对集M和E\M中交错出现的路，如图6.5.3 中路v2v3v4v5v6 。 M-增广路：起点和终点都是M-非饱和的一条M-交错路， 如图6.5.3中路v1v2v3v4v5v6 。 v1 v5

v2

v4

v3图6.5.3

v6

2012-10-25

Ludong University

匹配问题 (Matching Problem)1、两部图的匹配问题 a) 运输问题实际上是两部图的最小费用最大流问题 b) 任务分配问题实际上是两部图的最小完美匹配问 题 2、非两部图的匹配问题 a) 最大基数匹配(maximum cardinality matching) b) 最大权匹配(maximum weight matching) c) 最小完美匹配(minimum weight perfect matching) d) 最优分数匹配(optimal fractional matching)2012-10-25 Ludong University 5

覆盖覆盖：图G中一组点的集合K,使得图中的每条边至少有一 个端点在K中，则称K为图G覆盖。

图6.5.4一个覆盖

图6.5.5一个最小覆盖

定理6.8.1 设M是一个对集，K是一个覆盖，它们满足|M|=|K|, 则M必定是最大基数对集。而K是最小覆盖。2012-10-25 Ludong University 6

两部图的最大基数匹配 匈亚利算法

任务分配问题的抽象就是两部图的最小完全匹配问题 匈亚利算法(Hungarian method)由Kuhn教授提出，它实际 上是主对偶算法的先驱 匈亚利算法借助于效率矩阵和两部图来完成运算 任务分配问题的效率矩阵对应两部图的边权{cij},对偶问 题的解对应的是每条边的两个端点{ai, bj};对偶约束为 ai+bj cij 匈亚利算法的实质是通过构造对偶问题的可行解，得到一 个等值边子图，即所有ai+bj=cij的边构成的图；然后在等 值边子图上求最大基数匹配；当得到原问题的完全匹配， 则算法结束 对偶问题的可行解 等值边子图 满足互补松弛定理求原 问题的解(部分可行解) 检验 扩充等值边子图Ludong University 7

2012-10-25

最大基数匹配

最大基数匹配是基于交错树的算法 非饱和点、根、交错路、外点、内点、增广路 尚未匹配的节点称为非饱和点 以非饱和点为根，交错路的根为外点，其后内点与外点交替；外 点是交错链的生长点 以内点结

束的交错链称为增广路，因为反转该链上各边的匹配状 态可使匹配的边数增加一条

根

内点

外点

奇数圈

交错树示例2012-10-25 Ludong University

增广链8

算例求下图a所示的二分图G的最大基数对集，若初始解如下图b 所示。

1

6

1

6

2

7

2

7

3

8 9

3

8 9

4 5

4 5

A

A

a2012-10-25 Ludong University

b9

迭代过程(1)

1

6

3 1

1

6

2

7

2

7

3

8 9

33 3

3

8 9

4

4 5

5

A

A

标号

增广路6

1

3 1 5 3

1

6

7 8 10

2

7

2

7

3

8 9

3

8 9

4 5

4 5

A

3Ludong University

A

标号2012-10-25

增广路10

迭代过程(2)

1

6

1

6

7

2

7

1 2

2

7

3

8 9

3

8 9

10 8

4 5

4

A

5

5

A

标号

增广路

2012-10-25

Ludong University

两部图的最小权匹配-匈亚利算法1 2

3 4

5

7

令所有 ai=0 在效率矩阵中找每列最小值 qj,令bj=qj ,故 i,j,满足 ai+bj cij 在满足ai+bj=cij 的边构成的等值子图中求最大基数匹配；若达到完 全匹配则结束，否则到下一步 对敞露点求每列的最小松弛量 sj=min i* {ci*j-ai*-bj } 求最大增广量 S=0.5 min j {sj} 增广等值子图， j, bj = bj +S i*(敞露点), ai*=ai*+S ; i (非敞露点), ai= ai -S 返回到第3步Ludong University 12

2012-10-25

例 * 0 0 0 * 0 slack nbour 1 3 3 (1) 4 2 1 2 3 (2) 5 6 1 1 S*=0.5 1 5 5 1 4 3 4 2 3 2 6 10 1 1

*

*

2012-10-25

Ludong University

例 0.5 -0.5 -0.5 * 0.5 slack nbour 1.5 3 3 (1) 4 2 4 2.5 (3) 2 5 6 3 4 S*=1 1.5 5 5 1 4 2 4 2.5 3 (2) 6 10 7 4

*

2012-10-25

Ludong University

例 -0.5 -1.5 -1.5 1.5 slack nbour 2.5 3 3 1 (4) 3.5 (3) 2 5 6 2.5 5 5 (1) 4 3.5 3 (2) 6 10

2012-10-25

Ludong University

任务分配问题、匹配问题和TSP的关系三个问题都有一个 n n 正权值的边权矩阵 三个问题的解都可以用代数置换(permutation)表示 1 i 1 2 i2 3 i3 4 i4 5 i5 1 3 2 2 3 4 4 5 5 1

是1, 2, 3, 4, 5的任一排列 轮换，全轮换，对换 TSP的解必须是一个全轮换 任务分配问题的解可以是任一个置换 匹配的解必须是 n/2 个对换 任务分配问题是匹配问题的松弛问题 i1, i2, i3, i4, i52012-10-25 Ludong University 16