[工学]图论 的配对问题

《[工学]图论 的配对问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章匹配§1最大匹配－1具体问题描述：有n个女士和n个男士参加舞会，每位女士与其中若干位男士相识，每位男士与其中若干位女士相识，问如何安排，使得尽量多配对的男女舞伴相识。f1f2m1f3f4f5m2m3m4m5§1匹配§1最大匹配－1下图就是一种分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生配对？类似的工作分配问

2、题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？§1最大匹配－定义定义：若图G=(V,E)的顶点可以分成X，Y两个子集，每个子集里的顶点互不相邻，这样的图称为二分图。f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义1定义：若M是图G=(V,E)的边子集，且M中的任意两条边在G中不相邻，则称M为G中的一个匹配，M中的每条边的两个端点称为是M-饱和的的。f1f2m1f3f4f5m2m3m4m5M={(f1,m2),(f2,m1),(f3,m4),(f4,m5)}§1最大匹配－定义2定义：若图G中每个顶点均被M许配时，称M为G中的

3、一个完美匹配。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－定义3定义：图G中边数最多的匹配M，称为G中的一个最大匹配。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义4定义：若匹配M的某边和顶点v关联，称v是M-饱和的，否则就是M-不饱和的。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5饱和的不饱和的§1最大匹配－定义5定义：若M是图G的一个匹配，若从G

4、中一个顶点到另一个顶点存在一条道路，此路径由属于M和不属于M的边交替出现组成的，则称此路径为M-交错路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}P=f1m3f4m5f2m1f5m4§1最大匹配－定义6定义：若交错路的两个端点为关于M的不饱和顶点时，称此交互道为可增广道路。M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一条可增广道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义8f1f2m1f3f4f

5、5m2m3m4m5M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一条可增广道路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－Berge定理定理7.1(Berge1957)：M为最大匹配的充要条件是：图G中不存在可增广道路。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5[引理]设P是匹配Ｍ-可增广道路，则PM是一个比M更大的匹配，且

6、PM｜＝

7、M

8、+1.[定理1](Berge)

9、设G=(V,E)，M为G中匹配，则M为G的最大匹配当且仅当G中不存在M可增广道。[证明]必要性：如有M-可增广道路，则有更大匹配。矛盾！充分性：如果有最大匹配M’,

10、M’

11、>

12、M

13、.考虑MM’，在可增广路中，第一条边与最后一条边都不是中的边，因而可增广路中属于的边数比不在中边数少一条。M实线边，M’虚线边MM’其中每个结点的最多与Ｍ边和一个M’边关联，每条道路是M边和M’边交互道路。其中回路包含相同数目的M边和M’边。由

14、M’

15、>

16、M

17、,必存在M’边开始，M‘边终止的M交互道路，即M-可增广道路，矛盾！§2Hall定理设有m个人，n项工作，每个人会做其中的若干项工作，能不能适当安排，

18、使得每个人都有工作做？w1w2m1w3w4w5m2m3m4§2Hall定理当m>n时，肯定是不可能的，即使是m≤n也不一定。但如果每个人能做的工作越多，越容易实现。w1w2m1w3w4w5m2m3m4§2Hall定理－1Hall定理(1935)：二分图G存在一匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X任一子集A，及与A邻接的点集为N(A)，恒有：

19、N(A)

20、≥

21、A

22、。w1w2m1w3w4w5m2m3m4YX§