首页 > 代码库 > 8月24日————二分匹配
8月24日————二分匹配
参考:http://blog.csdn.net/pi9nc/article/details/11848327(别人写的真的很不错,虽然会使有那么一丢丢没看懂,但作比较水的题还是可以的,毕竟模板比较简单)
二分图:
设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。
匹配:在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。例如,图 3、图 4 中红色的边就是图 2 的匹配。
我们定义匹配点、匹配边、未匹配点、非匹配边,它们的含义非常显然。例如图 3 中 1、4、5、7 为匹配点,其他顶点为未匹配点;1-5、4-7为匹配边,其他边为非匹配边。
最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。图 4 是一个最大匹配,它包含 4 条匹配边。
完美匹配:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。图 4 是一个完美匹配。显然,完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突)。但并非每个图都存在完美匹配。
求解最大匹配问题的一个算法是匈牙利算法
该算法的基本模式:
1、 初始时最大匹配为空
2、 while (找得到增广路径)
3、 do 把增广路径加入到最大匹配中。
如果二分图的左半边一共有n个点,最多找n条增广路径,如果图中有m条边,每一条增广路径把所有边遍历一遍,所以时间复杂度为O(n*m);
几个重要概念记公式:
最小路径覆盖:在图中找尽可能少路径,是这些路径可以覆盖图中所有的点。(最小路径覆盖数=顶点个数-最大匹配数)
顶点覆盖:在顶点集合中,选取一部分顶点,这些顶点能够覆盖所有的边。(最小顶点覆盖=最大匹配数)
独立集:在所有的顶点中选取一些点,这些顶点两两之间没有连线(对大独立集=顶点个数-最大匹配数)
训练题目:http://acm.hdu.edu.cn/diy/contest_show.php?cid=24552
8月24日————二分匹配