二部图与匹配.

Presentation on theme: "二部图与匹配."— Presentation transcript:

1 二部图与匹配

2 回顾 引言 Dijkstra算法 旅行商问题（TSP）

3 提要 二部图 二部图中完备匹配（Hall定理） 二部图中的最大匹配 二部图中的稳定匹配

4 二部图(bipartite graph，偶图)
二部图：顶点集划分为2个类别(不相交)，边的端点 在不同类别中。 完全二部图：来自不同类别的两个顶点均有边。 K2,3 K3,3 G

5 二部图的判定 C6是否是二部图？ 二种颜色对顶点着色，相邻顶点赋以不同颜色 二部图？

6 孤岛上的婚姻 成就最多幸福婚姻的配对方案 互不相邻的边集

7 图中的匹配 匹配（边独立集）：互不相邻的边的集合 M-饱和点：M中各边的端点 匹配数 1=3 匹配数 1=4 完美匹配 极大匹配
不一定要二部图 完美匹配 极大匹配 最大匹配 M-饱和点 M-饱和点

8 二部图中的完备匹配 定义：设G是二部图，二部划分为<V1,V2>，若G 中的匹配M饱和V1中所有顶点，则称M为V1到V2 的完备匹配。 注意：完备匹配一定是最大匹配，但仅当|V1|=|V2|才 是完美匹配。 存在完美匹配 无完备匹配？ V1到V2的完备匹配

9 二部图中的完备匹配（举例） V1={1, 2, 3, 4, 5, 6}, 是否存在饱和V1的配对方案？ 饱和{1, 3, 4, 6}？
A 1 B 2 C 3 D 4 E 5 F 6 G {A, C, F} {A, C} {A, F} {C, F} 饱和{1, 3, 4, 6}？

10 Hall定理 Hall定理(1935, Marriage Theorem)
设二部图G=<V1, V2, E>, 则G有V1到V2的完备匹配  对于任意的 A V1 ，有 |N(A)|  |A | 证明. 必要性易证，下证充分性（使用强归纳法）。 如果 |V1 |=1, 充分性命题显然成立。 假设当|V1 |k (k 1) 时充分性命题均成立, 要证:当|V1|=k+1时 充分性命题也成立。分二种情形来证明。 (1)对V1的任意真子集A ， |N(A)|  | A | (2)存在 V1的一个真子集A'， |N(A')| = | A' |

11 Hall定理 归纳证明. (1)对V1的任意真子集A , |N(A)|  | A |
任取一个顶点v V1, 任取wN({v}) （一定存在）. H=G-{v, w}是一个二部图（非空）. v w H满足归纳假设的条件, 从而 H有V1 -{v}到V2 -{w}的完备匹配. 这个匹配加上边(v, w)构成G的从V1 到V2的完备匹配.

12 Hall定理 (2)存在 V1的一个真子集A', |N(A')| =|A' |. 记 B'= N(A').
二部图H=G-A'-B' 满足归纳假设条件. A' B' 否则, 存在C V1-A'. |NH(C)|<|C|. |NG(CA')| |NH(C)|+|B'|<|C|+|B'|=|C|+|A'|= |CA'|. 矛盾. 据归纳假设,存在V1-A'到V2-B'的完备匹配. 合并上述两个匹配得到一个V1到V2的完备匹配. 得证

13 Hall定理的推论 设二部图G是一个k-正则的(k  1), 则G有完美匹配.
证明. 不妨设G= < A, B, E>, k |A| = k |B|, 所以|A| =|B|. 下证G有A到B的完备匹配. 对任一S A，S与N(S)之间总共有k|S| 条边，而与N(S)相关的 边总共有k|N(S)| 条边。 ∴ k|S|  k|N(S)| ∴ |N(S)|  |S| 根据Hall定理，G有A到B的完备匹配，因 |A| = |B|，该匹配是 完美匹配。

14 完备匹配的一个充分条件 二部图G=(V1,V2, E), 若V1中每个顶点至少关联t条边，而若V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配。 证明 类似于上述推论， t|S|  …  t |N(S)| 。

15 交错路径与可增广交错路径 定义：设M是G中一个匹配。若G中路径P中M与 EG-M中的边交替出现，则称P为M-交错路径(也可 以是回路)；若P的起点与终点都是M-非饱和点 （没有被匹配的顶点），则称P是可增广交错路径 （增广路径）。 可增广交错路

16 最大匹配与增广路径 Berge定理. M是最大匹配 相对于M没有增广路径 证明. 容易证明必要性，下证充分性.
假设有一个更大的匹配M′. 令G′ = (V, M⊕M′). G′中 各顶点的度最多为2. 因此, G′的各连通分支要么是 路径(孤立点也看作路径), 要么是回路（偶长度）. 无论是路径还是回路，来自M 的边与来自M′的边一 定是交错的. 由|M′| |M|, 故必有一条路径包含M′的 边多于M的边, 易见此路径是相对于M的增广路径. M⊕M′为对称差，并减去交

17 增广路径的算法思想 在二部图中直接使用增广路径的匹配算法 找增广路径, 对M进行增广 , 一直至没有增广路径.
复杂度 O(|V||E|)，最大匹配的元素个数|V|/2

18 稳定匹配 Unstable: If M is a matching and e=(a, b) is an edge not in M such that both a and b prefer e to their current matching edge. G的一个偏好集 一族线性序 (v)vV， 其中，v是E(v)上的线性序。 G中一个匹配M 是稳定的 对任意一个eE\M，存在 fM满足 ： (i) e 和f 有公共端点，(ii) e vf.

19 稳定匹配（稳定的婚姻） 稳定匹配获取思路 定理 1.4. (Gale & Shapley 1962)
男子向尚未拒绝他的最喜爱的女子求婚. 女子接受目前为止最如意的求婚提议，但是，倘若有 更如意的求婚者，会改变主意。

20 例 Given men x, y, z, w, women a, b, c, d, and preferences listed below, the matching {xa, yb, zd, wc} is a stable matching. Men{x, y, z, w} Women {a, b, c, d} x: a > b> c > d a: z > x > y> w y: a> c > b > d b: y >w > x> z z: c> d > a > b c: w > x > y > z w:c > b > a >d d: x > y > z > w X a Y b Z c W d

21 稳定匹配  术语 给定M，a∈A可被b∈B接受 a∈A对M满意 (a, b)∈E\M，并且
若存在(a', b)∈M, 则 (a', b) b (a, b). a∈A对M满意 a是一个尚未配对的顶点，或 者 存在(a, b)∈M, 若a可被b'接 受，则 (a, b) >a (a, b') a可被b接受：b的视角里a更好，如果a的视角里也是b更好，这就是一个不稳定的匹配

22 稳定匹配  算法 从一个空的边集开始，构造（更新）匹配M，保持 “A中的所有顶点对M满意”这一特性。 给定这样的一个M,
对于A中尚未配对的某顶点a，若{ (a, b) | a可被b接受}非 空. 按照线性序≤a找出最大元，记为(a, bj)，将这条边添加 到M中，删除M中以bj为端点的边（假如有的话）。 对于A中尚未配对的所有顶点a，{ (a, b) | a可被b接受}均 为空. （结束）

23 稳定匹配  算法正确性分析* 结束之时 结束之时，M是稳定的 对任意一个eE\M，存在 fM满足 ：
A中未配对的顶点均没有可被接受的对象 A中的所有顶点对M满意 结束之时，M是稳定的 对任意一个eE\M，存在 fM满足 ： (i) e 和f 有公共端点; (ii) e vf. f e g

24 稳定匹配  算法正确性分析* 算法是否会结束？
M越来越好，至于不能更好。 M 比M'更好: 使得B中顶点更快乐, 也就是说，对于B 中任一顶点b，若b是某个边f'∈M'的端点，则b必是某 个边f∈M的端点，且f' ≤b f.

25 工作分配问题 问题：n个毕业生有可供选择的m个岗位，每个毕 业生给出若干个志愿，是否存在每个人都满意的分 配方案。
数学模型：建立二部图，V1中每个点对应一个毕业 生， V2中每个点对应一个可选的岗位，uvE当且 仅当u对应的毕业生愿意选择v对应的岗位。 问题的解：问题有解当且仅当G有饱和V1中所有顶 点的完备匹配。

26 工作分配问题的一般形式 工作分配问题 是否可能使每个申请者得到一个他/她适合的职位？ 若不能，最多多少申请者能够被分配到合适的职位？
某机构提供n个空缺职位, 有m个申请者。每个申请者满 足某些职位的要求。 是否可能使每个申请者得到一个他/她适合的职位？ 若不能，最多多少申请者能够被分配到合适的职位？ 如何实现一个最佳分配方案？

27 工作分配问题的求解模型 申请者集合 职位的集合 bj ai ...... 在此模型中如何解释问题的解？ A B
aibjEG iff. ai 适合于 bj

28 棋盘上的士兵  o o    o o  要在左图所示的棋盘上放置4个士兵，任何一行或者一列恰好放一个，但不能放在有标记的格子中。
构造一个二步图，ai表示行，bi表示列。aibj E 当且仅当第i行第j列的方格没有标记。 o 

29 作业 见课程网站