二分图匹配匹配.ppt

《二分图匹配匹配.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论2江川二分图一个图的点集可以划分为两个不相交的子集，每一个子集中的点和该子集中的其他点没有边相连二分图一个图是二分图的充要条件是这个图里没有奇环二分图匹配匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。最大匹配：所有匹配中边数最多的。完备匹配：如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完备匹配。二分图匹配Hall定理一个二分图有完备匹配的充要条件是：任意k个点相邻的点的集合中不少于k个点匈牙利算法M-交错路：p是G的一条通路，如果p中的边为

2、属于M中的边与不属于M的边交替出现，则称p是一条M-交错路。M-饱和点：对于v∈V(G），如果v与M中的某条边关联，则称v是M-饱和点，否则称v是非M-饱和点。M-可增广路：p是一条M-交错路，如果p的起点和终点都是非M-饱和点，则称p为M-可增广路。匈牙利算法匈牙利算法ForalliinX:1、从i出发寻找可增广路2、沿增广路更新（删除原属于M的边，增加不属于M的边）O(nm)匈牙利算法匈牙利算法匈牙利算法应用1点覆盖集：图的顶点集的子集，覆盖图中所有的边最小点覆盖：无向图中，求最少需要多少个点可以覆盖所有的边。NP应用1二分

3、图的最小点覆盖应用1König定理：二分图的最小点覆盖=最大匹配应用1假设最小点覆盖=N，最大匹配=M考虑最大匹配中的边两两不相交，所以至少需要M条边覆盖。得N>=M应用2独立集:图的顶点集的子集，其中任意两点不相邻。最大点独立集:无向图中，求一个最大的顶点集，其中任意两点不相邻。NP应用2覆盖集的补集一定是独立集证明：假设某一覆盖集的补集不是独立集。说明有一条边连接了覆盖集的补集的两个点。那么这条边没有被覆盖集所覆盖，产生矛盾。应用2独立集的补集一定是覆盖集证明：假设某一独立集的补集不是覆盖集。说明有一条边不被独立集的补集覆盖

4、，那么这条边连接了独立集的两个端点，产生矛盾。应用2覆盖集与独立集互为补集二分图中可求出最大匹配M最小覆盖集=M，最大独立集=n-M应用3一共N个男孩和女孩参加聚会，某些男孩和女孩之间会产生恋爱关系。现在希望找到最多的孩子，他们之间不会产生恋爱关系。应用3男孩在一边，女孩在一边会产生恋爱关系的连边找最大独立集应用4一共N个人参加聚会，某些人之间会产生恋爱关系（一定是异性之间）。现在希望找到最多的人，他们之间不会产生恋爱关系。应用4所有的人复制成两份放在两边会产生恋爱关系的连边最大独立集=N–最大匹配/2应用5给你一个N*N的格子

5、，每个格子里要么有一个陨石，要么为空。每一次你可以清除一行或者一列里的所有陨石，求最少要多少次才能把所有的陨石清除干净。XXXX应用5把N*N的格子看成是一个二分图，每一行是一个集合的点，每一列是另一个集合的点，那么某个格子（x,y）中有陨石就相当于顶点x到顶点y有一条边，那么要求使陨石全部被清理掉的最少的次数，就是要使该二分图中的所有边都被覆盖的最少顶点数。XXXX应用6动物园有N只猫，M只狗，P个小孩。每个小孩都有自己喜欢的和讨厌的动物。如果他喜欢狗，那么就讨厌猫；如果他讨厌猫，那么他就喜欢狗。每个小孩会说，我喜欢__号猫，

6、讨厌__号狗；或者说，我喜欢__号狗，讨厌__号猫。如果他喜欢的那只动物被留下，而且讨厌的那只动物被带走，他就会开心。请问最多有多少小孩能开心。应用6现在要求最多的小孩，两两之间不矛盾从矛盾关系入手猫和猫之间，狗和狗之间一定不存在矛盾关系如果A小孩喜欢的动物与B小孩讨厌的动物一样，或者A小孩讨厌的动物与B小孩喜欢的动物一样，那AB之间就存在着排斥关系，则他们之间连接一条边（他们不可能同时开心）求最大的点集，两两之间没有边最大点独立集应用7路径覆盖：路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一

7、条路径与之关联。注意一个单独的点也是一条路径。现要求有向无环图的最小路径覆盖，即在一张有向无环图中，找路径数最少的路径覆盖。应用7把每个顶点拆成两份，然后按原图连边。应用7最小路径覆盖=n–最大匹配每一个匹配相当于原图中的某两个路径合并应用8在一个有向无环图上，至少放多少个机器人可以遍历整个图？注意点是可以重复经过的。应用8允许重复经过点的最小路径覆盖如果经过一个重复的点我们可以假装跳过了它进入下一个点Floyed求出传递闭包再做最小路径覆盖应用9在一个N*M的矩形里，有一些格子被毁坏。现在要求用1*2的木板去覆盖没有被毁坏的

8、格子，木板不可覆盖彼此，问是否能把每个格子都盖住。应用9所有没有被毁坏的格子都看成图中的点按格子的“奇偶性”分成两类如果两个格子相邻，则在这两个点上连边若存在完备匹配则所有的格子可以被覆盖应用10A机器有n个模式，B机器有m个模式。现有k个任务需要做，可以用A