《《二分图相关问题》ppt课件》由会员分享，可在线阅读，更多相关《《二分图相关问题》ppt课件（61页珍藏版）》请在金锄头文库上搜索。
1、二分图相关问题|二分图相关问题。二分图最大匹配。二分图最小覆盖。二分图最大独立集。二分图最小路径覆盖。二分图最优匹配“稳定婚姻问题|二分图定义及判定定义:二分图中,顶点可以分为两个集合X和耳，每一条边的两个顶点都分别位于X和Y集合。判定:利用BFS或者DFS进行黑白染色,共享一边的两点异色,检查是杏存在矛盾。图G为二分图的充要条件是图中不含奇环|二分图最大匹配。定义:匹配是二分图中边的集合,世集合中的任意两条边没有公共点,包含边数最多的匹配就是最大匹配熹个口|匀牙利算法。概念:交错路5对于一个匹配M,如果能找到一条奇数长度的路,使得路的第一、,三、五.边不属于M,而第二、四、六.边属于M,那么
2、这条路叫健交错路。5交错路可以“增广“,即通过适当修改得到更大的匹配。|匀牙利算法。交错路增广示例(1-2-3-4-5-6-7-8)|匀牙利算法。定理:一个匹配为最大匹配当且仅当匹配中不存在交错路证明相当繁琐,具体参见组合数学。可以利用BFS或者DFS实现寻找交错路|匀牙利算法。伟牙利算法的实现还依赖于一个很重要的定理:如果从一个点出发,没有找到增广路径,那么无论再从别的点出发找到多少增广路径来改变露萼的匹配，从这个点出发都永远找不到增广佣。Why?。AVOV1V2V32.1.B如果是V0或V2或.的匹配的改变导致找到交错路,那么改变的这点也存在于交错路中,那么在改变之前就应该找到交错路|匀牙利算法。匈牙利算法只需要以每个节点为起点找一次增广路即可求得最大匹配,寻找增广路的复杂度为O(E,总的复杂度为O(CVE)DFS实现intfindtintgfor(每个与k相邻的点)if(coverf=FALSE)q=inkilinkJ=kcoverf=TRUE;ifq=-1川findtqj=1)return1;link=q;returnD;work0link数组初始化为-1for(i=0iism;cover数组初始化为FALSE;findf;
