二部划分为 - 南京大学.ppt

Exercise (II) 对于每一个二部图G=(A,B,E), 判断G是否有饱和A的匹配。如果没有，请说明理由 a0 a1 a2 a3 b2 b1 b0 A B 1) a0 a1 a2 b3 b2 b1 b0 A B 2) a0 a1 a2 a3 b2 b1 b0 A B 3) a4 b3 b4 b5 a0 a1 a2 a3 b2 b1 b0 A B 4) a4 b3 b4 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）和一组偏好，使得图中不存在稳定匹配。 QA 参考文献 Reinhard Diestel. Graph Theory. Springer, Heidelberg, 2005 * * * * * * * * * * * * * * * June. 2016 * Department of Computer Science and Technology, Nanjing University Department of Computer Science and Technology, Nanjing University 二部图中的匹配 离散数学课程组 南京大学计算机科学与技术系 内容提要 引言 二部图中完备匹配（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的配对方案？ 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定理 H满足归纳假设的条件, 从而 H有V1 -{v}到V2 -{w}的完备匹配. 这个匹配加上边(v, w)构成G的