PDF《二部图与匹配》

二部图与匹配

1 ? 引言 ? Dijkstra算法 ? 旅行商问题(TSP) 回顾 ? 二部图 ? 二部图中完备匹配(Hall定理) ? 二部图中的最大匹配 ? 二部图中的稳定匹配 提要 二部图(bipartite graph,偶图) ? 二部图:顶点集划分为2个类别(不相交),边的端点 在不同类别中.

? 完全二部图:来自不同类别的两个顶点均有边. K2,3 K3,3 G 二部图的判定 ? C6是否是二部图? ? 二种颜色对顶点着色,相邻顶点赋以不同颜色 二部图? ? 成就最多幸福婚姻的配对方案 互不相邻的边集 孤岛上的婚姻 ? 匹配(边独立集):互不相邻的边的集合 ? M-饱和点:M中各边的端点 匹配数 ?1=3 匹配数 ?1=4 极大匹配 最大匹配 完美匹配 M-饱和点 M-饱和点 图中的匹配 ? 定义:设G是二部图,二部划分为,若G 中的匹配M饱和V1中所有顶点,则称M为V1到V2的 完备匹配. 注意:完备匹配一定是最大匹配,但仅当|V1|=|V2| 才是完美匹配. 无完备匹配? V1到V2的完备匹配 存在完美匹配 二部图中的完备匹配 ? V1={1, 2, 3, 4, 5, 6}, 是否存在饱和V1的配对方案? 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}? 二部图中的完备匹配(举例) Hall定理

10 ? Hall定理(1935, Marriage Theorem) 设二部图G=, 则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' | Hall定理

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

12 (2)存在 V1的一个真子集A', |N(A')| =|A' |. 记B'= N(A'). 据归纳假设,存在A'到B' 的完备匹配. 二部图H=G-A'-B' 满足归纳假设条件. A' B' 否则, 存在C ?V1-A'. |NH(C)|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 结束之时 A中未配对的顶点均没有可被接受的对象 A中的所有顶点对M满意 ? 结束之时,M是稳定的 对任意一个e?E\M,存在 f?M满足 : (i) e 和f 有公共端点;

(ii) e ?vf. e g f 稳定匹配 ? 算法正确性分析*

24 ? 算法是否会结束? ? M越来越好,至于不能更好. ? M 比M'更好: 使得B中顶点更快乐, 也就是说,对于B中 任一顶点b,若b是某个边f'∈M'的端点,则b必是某个 边f∈M的端点,且f' ≤b f. ? 问题:n个毕业生有可供选择的m个岗位,每个毕业 生给出若干个志愿,是否存在每个人都满意的分配 方案. ? 数学模型:建立二部图,V1中每个点对应一个毕业 生, V2中每个点对应一个可选的岗位,uv?E当且 仅当u对应的毕业生愿意选择v对应的岗位. ? 问题的解:问题有解当且仅当G有饱和V1中所有顶 点的完备匹配. 工作分配问题 ? 工作分配问题 ? 某机构提供n个空缺职位, 有m个申请者.每个申请者满足 某些职位的要求. ? 是否可能使每个申请者得到一个他/她适合的职位? ? 若不能,最多多少申请者能够被分配到合适的职位? ? 如何实现一个最佳分配方案? 工作分配问题的一般形式 A ai B bj ...... 申请者集合 职位的集合 aibj?EG iff. ai 适合于 bj 在此模型中如何 解释问题的解? 工作分配问题的求解模型 要在左图所示的棋盘上放 置4个士兵,任何一行或者 一列恰好放一个,但不能 放在有标记的格子中. 构造一个二步图,ai表示行,bi 表示列.aibj ?E 当且仅当第i行第j列的方格没有标记. ? ? ? ? ? o o o o 棋盘上的士兵 ? 见课程网站 作业