经典算法之二分图概要.ppt

二分图讲课：何振豪 主要内容 1.什么是二分图 2.二分图的判定 3.二分图的最大匹配 4.二分图的最小顶点覆盖 5.二分图的最小路径覆盖 6.二分图的最大独立集 7.二分图的最佳完美匹配 什么是二分图？？ 如果能将图中的所有点分为两个不相交的点集，U和V，且图中的每一条边都满足一个点在U，另外一个点在V，我们就叫这种图为“二分图（ Bipartite Graph ）” 二分图的判定 问题描述(HDU 1068)：给定n个学生，告诉你有哪m对学生是相互认识的，问你能不能把这n个学生分成两个组，使组内的学生相互不认识。（注意A认识B，B认识C，但这并不意味着A与C认识。） 二分图的判定 无向图G是二分图的充分必要条件是：G至少有两个点，且其所有回路的长度都为偶数。（摘自某度百科）换句话说就是不存在奇数环（反证法）。 常用方法：染色法 具体步骤： 先对任意一未染色的顶点染色，之后判断其相邻的顶点，若未染色则将其染上和相邻顶点不同的颜色， 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断，知道所有点被分成不一样的颜色。 以上过程用DFS和BFS都可以实现。 为什么染色法可以判定是否存在奇环呢？（简易画图即可得出答案） 二分图的最大匹配 问题描述(HDU 2063)：坐过山车，每个过山车有两个座位，并且有个硬性规定：只能男的和女的坐在一起。但是，女孩们有自己的想法，他们只会找特定的男生。现给你女生和男生的人数和k组男女的组合，问你最大的可以做过山车的组合数。 二分图的最大匹配 先来看2个概念吧！ 交替路：就是从未匹配点出发，依次走的边属于未匹配边，匹配边……未匹配边，匹配边； 增广路：就是从未匹配点出发，走交替路，最后走的是未匹配边，到达匹配点； 见图Fig.3 我们假定红色部分是已匹配的边，黑色为未匹配的边； 由以上定义，我们可以发现一条增广路：2-5-1-7-4-8 恰好是从未配点出发，走交替路，又回到未配点。 二分图的最大匹配 增广路的性质： （1）有奇数条边； （2）起点在左边，终点在右边； （3）路径上的点一定是一个在左边，一个在右边，未匹配边，匹配边，未匹配边交替出现，最后一条是为匹配边； （4）路径上的点只有终点和起点不是匹配点，其余都是匹配点； （5）第奇数个边是未匹配边，第偶数个边是匹配边； 研究增广路的意义：只要将增广路的边做一个异或操作（将未匹配边变成匹配边，将匹配边变成未匹配边），匹配边的数量就能加一，反复寻找这个增广路的话，就能将匹配数不断增加，一直到找不到这个增广路，就说明当前找到的匹配是最大匹配。 从上述的图Fig3做异或操作即可得到Fig4 二分图的最大匹配 匈牙利算法轮廓： ⑴置匹配子图M为空； ⑵找出一条增广路径P，通过异或（取反）操作获得更大的匹配子图M’代替M； ⑶重复⑵操作直到找不出增广路径为止。 以上过程用DFS和BFS实现均可。 复杂度分析： 因为每个点都要找一次增广路，这条路取最极端的长度就是边的数量，所以时间复杂度是??O(V?E)?； 代码见附件 Hopcroft Karp算法 在匈牙利算法中是通过每次找一次增广路来增加匹配的数量。如果点有上千个，又是稠密图，这个算法就跑不动了。 为了降低时间复杂度，在霍普克洛夫特－卡普算法中，我们在增加匹配集合M时，每次寻找多条增广路。 可以证明，这样只需要最多增广2 * |V|^0.5，所以时间复杂度是 O(|E||V|^0.5)。 代码见附件 实际上后面要讲的所有二分图匹配问题都是由这个匈牙利算法延伸而来的，至少主要核心内容就是寻找增广路。 二分图最小点覆盖 问题描述 ：给你一个N * M的矩阵，矩阵的格子可能有不明物体，需要用激光消灭，激光在边界均有设置，只能射出直线，问你最少用多少次激光将所有的不明物体消灭。如图： 答案显然是2 二分图最小点覆盖 最小点覆盖指的是在二分图中求最少的点，让每边都至少和其中的一个点关联。 K?nig定理：二分图中的最大匹配数等于这个图中的最小点覆盖数（具体证明可以参考Matrix67的博文：/blog/archives/116） 回到刚才那道题：为什么是最小点覆盖？？ 可以把横坐标（1……n）看做左边的集合，纵坐标（1……m）看做右边的集合，然后根据题设，射出激光就意味着取一个点，因为如果取出的点是左边的集合，那就横坐标被覆盖，取出的点是右边的点就纵坐标被覆盖，不难得出答案最大是min（n，m）； 二分图最小路径覆盖 问题描述：选择用尽量少的不相交简单路径，使其覆盖所有顶点，且任何一个顶点有且只有一条路径与之关联。换句话说，就是选尽量少的边，把这些边都从起点走到终点，恰好能够经过整个图的所有顶点。问你这些边的数量。 定理：路径覆盖与二分图匹配的关系：最小路径覆盖＝｜G｜－最大匹配数