1、信息学竞赛 算法分析与设计1本节课程内容二分图、匹配二分图、匹配(bipartite graph、 matching)l 匈 牙 利 算 法 l Kuhn-Munkras算法2二分图的概念l 二分图又称作二部图，是图论中的一种特殊模型。l 设 G=(V,R)是一个无向图。如顶点集 V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图 G为二分图。1122334453最大匹配l 给定一个二分图 G，在 G的一个子图 M中，M的边集 E中的任意两条边都不依附于同一个顶点，则称 M是一个匹配。l 选择这样的边数最大的子集称为图的最大匹配问题 (maximal mat
2、ching problem)l 如果一个匹配子图中，图中的每个顶点都和匹配子图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。4匈牙利算法l 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。l 增广路的定义 (也称增广轨或交错轨 )：若 P是图 G中一条连通两个未匹配顶点的路径，并且属 M的边和不属 M的边 (即已匹配和待匹配的边 )在 P上交替出现，则称 P为相对于 M的一条增广路径。5匈牙利算法l 由增广路的定义可以推出下述三个结论： 1. P的路径长度必定为奇数，第一条边和最后一条边都
3、不属于 M。 2. P经过取反操作可以得到一个更大的匹配 M。 3. M为 G的最大匹配当且仅当不存在相对于 M的增广路径。6匈牙利算法l 用增广路求最大匹配 (称作匈牙利算法，匈牙利数学家 Edmonds于 1965年提出 )l 算法轮廓：l (1)置 M为空l (2)找出一条增广路径 P，通过取反操作获得更大的匹配 M代替 Ml (3)重复 (2)操作直到找不出增广路径为止7任给初始匹配找 xV1为非饱和点S=x,T=取 yN(s)-T存在一条从 x到 y的 M可增广路 P， M： =MP无法继续匹配，停止存在边 y,u MS： =SuT： =T yM饱和 V1N(s)=T?YNYNY已经
4、饱和 YN停止， M为最大匹配8设 G是具有二部划分 (V1,V2)的二分图 .(1)任给初始匹配 M;(2)若 M饱和 V1则结束 .否则转 (3);(3)在 V1中找一非 M饱和点 x,置 S=x,T=;(4)若 N(S)=T,则停止 ,否则任选一点 yN(S)-T;(5)若 y为 M饱和点转 (6),否则作求一条从 x到 y的 M可增广路 P,置 M=MP,转 (2)(6)由于 y是 M饱和点 ,故 M中有一边 y,u,置S=Su,T=Ty,转 (4).匈牙利算法步骤9匈牙利算法程序清单：#include#includebool g201201;int n,m,ans;bool b201;int link201;10
