离散数学课程组 南京大学计算机科学与技术系 二部图中的匹配 离散数学课程组 南京大学计算机科学与技术系

内容提要 引言 二部图中完备匹配（Hall定理） 二部图中的最大匹配 二部图中的稳定匹配

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

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

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

二部图中的完备匹配（举例） 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}？

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’ |

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

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的完备匹配. 得证

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|，该匹配是完美匹配。

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

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

最大匹配 Berge’s Lemma (1957). M是最大匹配 相对于M没有增广路径 证明. 容易证明必要性，下证充分性. 假设有一个更大的匹配M′. 令G′ = (V, M⊕M′). G′中各顶点的度最多为2. 因此, G′的各连通分支要么是路径(孤立点也看作路径), 要么是回路.无论是路径还是回路，来自M 的边与来自M′的边一定是交错的.

最大匹配 若是回路, 来自M 的边数等于来自M′的边数. 因为|M′| |M|, 故必有一条路径包含M′的边多于M的边, 从而是相对于M的增广路径. 得证

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

稳定匹配（稳定的婚姻） 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. e g f a b G的一个偏好集 一族线性序 (v)vV， 其中，v是E(v)上的线性序。

稳定匹配（稳定的婚姻） G中一个匹配M 是稳定的 对任意一个eE\M，存在 fM满足： (i) e 和f 有公共端点v，(ii) e v f. e f e v f e f e v f 定理 1.4. (Gale & Shapley 1962) 任意给定一个偏好集，二步图G有一个稳定的匹配。

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

稳定匹配（稳定的婚姻） Example. 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

稳定匹配（稳定的婚姻） 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 Y b Z c W d

稳定匹配（稳定的婚姻） 术语 给定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’)

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

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

稳定匹配（稳定的婚姻） 算法正确性分析 算法是否会结束？ 何为“好”: M 比M’好 M越来越好，至于不能更好。 稳定匹配（稳定的婚姻） 算法正确性分析 算法是否会结束？ M越来越好，至于不能更好。 何为“好”: M 比M’好 对于B中任一顶点b，若b是某个边f ’∈M’的端点，则b必是某个边f∈M的端点，且f ’ ≤b f. （B中顶点有更好的配对）

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

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

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

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

作业 教材[9.2] p. 468： 27, 28

Exercise (II) 从下图G=(A,B,E)中, 找出相对于匹配M(粗边的集合)的任意三条交错路径(alternating path)和两条增广路径(augmenting path)。然后利用找出的增广路径扩大M. a0 a1 a2 a3 a4 a5 b0 b1 b2 b3 b4 b5

Exercise (II) 对于每一个二部图G=(A,B,E), 判断G是否有饱和A的匹配。如果没有，请说明理由 A B 4) A B 1) 2) a0 a1 a2 a3 b2 b1 b0 A B 3) a4 b3 b4 b5

Exercise (II) 3. 令k为一整数。对于任意有限集合，证明对它的任意 两个ｋ划分 都存在一个相同的代表集。 　 说明：１）ｋ划分指划分为大小相同的互不想交的ｋ个子集，为简便起见，设集合的大小为ｋ的整数倍从而每个子集均有相同个元素。 　　　　　２）一个划分的代表集指从每个子集中取出一个元素而构成的集合。 　　 举例：集合 {1,2,3,4}的一个２划分为 A:{1,2} {3,4} . 此划分的代表集有 {1,3} ， {2,3} ，{1,4} ， {2,4}, 但 {1,2}不是其代表集. 集合的另外一个划分为 B:{2,3} {1,4}.易见，Ａ与Ｂ存在相同的代表集 {1,3}。可以试验，任意两个２划分均存在相同的代表集。

拓展题 4. 找出一个二部图和一组偏好(preference),使得在此图中所有最大匹配均不是稳定匹配而所有稳定匹配均不是最大匹配（Find a bipartite graph and a set of preferences such that no matching of maximal size is stable and no stable matching has maximal size.） 5. 找出一个非二部图（non-bipartite graph）和一组偏好，使得图中不存在稳定匹配。

Reinhard Diestel. Graph Theory. Springer, Heidelberg, 2005 Q&A 参考文献 Reinhard Diestel. Graph Theory. Springer, Heidelberg, 2005