江苏龙网

  1. 首页 > 生活 > >

图论：最大匹配的充要条件和交错路径的概念问题

交错路径的理解并没有错，如上所说，交错路径长度可以为1。设想一下，你在算最大匹配的时候，初始的匹配就是一个空集，你是怎样往这个匹配里面加边的。另外，你没有提到那本课本里面，可增广的交错路径，给出了定义吗？交错路径：假设M是图G的一个匹配，那么M的交错路径指的是匹配边和非匹配边交替构成的路径。增广路径：假设M是图G的一个匹配，那么M的增广路径指的是 起点和终点都是M的非匹配边顶点 的M的交错路径。当然，前提你必须有图、匹配、路径这些概念。比如如果你觉得在图三中{e2,e1,e3}是一条增广路径那就是没有理解路径的概念了。
■网友
二分图是两两唯一匹配这个能理解吧，就像是一对狗男女牵手了一样，每个男的都要找到对应喜欢或喜欢自己的女的，也就是图中的点两两对应，最大匹配也就是能牵手的最大数量，越多越好，直到没有单身狗为止，而所谓的单身狗也就是所对应的非饱和点，尽可能去实现顶点的两两对应最大化，而本题中最大匹配就是M={e1,e4,e7}，同时M={e1,e4,e7}也是图中的最小边覆盖，这3条边对应的6个点，3对狗男女可以完美牵手，且没有落单狗存在，所以本题是找不到增广路径的，因为已经是最优解了，假设我们一开始设定M={e3,e5}这个匹配，那左上角的那个点和右下角e7的那个点都是非饱和点了，那我们也可以发现，{e1,e3,e4,e5,e7}就是一条增广路经，同时也证实了增广路径的路径个数必定为奇数，第一条边和最后一条边都不属于M集合，增广路经存在，说明必然有更大匹配，这个可以去看下匈牙利算法，一看便知道

■网友
【图论：最大匹配的充要条件和交错路径的概念问题】 我们书上写的是“二部图的匹配是最大匹配当且仅当不存在关于它的增广交错路径”，我想或许是需要“二部图”的条件才能成立？


    推荐阅读


    上一篇：一个外贸电商项目组发展初期的领导人应该具有哪些能力

    下一篇：淘宝推喵街对万达电商推飞凡有啥冲击