孤岛上的婚姻成就最多幸福婚姻的配对方案互不相邻的边集
成就最多幸福婚姻的配对方案 互不相邻的边集 孤岛上的婚姻
图中的匹配匹配（边独立集）：互不相邻的边的集合口M-饱和点：匹配M中各边的端点匹配数匹配数β;=3β,=4完美匹配极大匹配M-饱和点M-饱和点最大匹配
匹配（边独立集）：互不相邻的边的集合 M-饱和点：匹配M中各边的端点 匹配数 1=3 匹配数 1=4 极大匹配 最大匹配 完美匹配 M-饱和点 M-饱和点 图中的匹配
本节提要问题1：什么是二部图及其匹配?口口两个无内部边的顶点集；互不相邻的边的集合口问题2：二部图中的有哪些匹配?
问题1：什么是二部图及其匹配？ 两个无内部边的顶点集；互不相邻的边的集合 问题2：二部图中的有哪些匹配？ 本节提要
二部图中的完备匹配定义：设G是二部图，二部划分为<V,V2>，若G口中的匹配M饱和V,中所有顶点，则称M为V,到V,的完备匹配。注意：完备匹配一定是最大匹配，但仅当/V1l=/V2l才是完美匹配。无完备匹配？存在完美匹配V,到V,的完备匹配
定义：设G是二部图，二部划分为<V1 ,V2>，若G 中的匹配M饱和V1中所有顶点，则称M为V1到V2的 完备匹配。 注意：完备匹配一定是最大匹配，但仅当|V1|=|V2| 才是完美匹配。 V1到V2的完备匹配 存在完美匹配 无完备匹配？ 二部图中的完备匹配
（举例）二部图中的完备匹配口V1={1,2,3,4,5,6?，是否存在饱和V的配对方案?[A, C, F)(A, C)饱和[1,3,4,6]?[A, F){C, F)
V1={1, 2, 3, 4, 5, 6}, 是否存在饱和V1的配对方案？ A B C D E F G {A, C, F} {A, C} {A, F} {C, F} 饱和{1, 3, 4, 6}？ 二部图中的完备匹配（举例）