百度商桥可以在两个网站放,营销技巧在线观看,seo分析seo诊断,广州网站设计服务商来自#xff1a;http://blog.csdn.net/l04205613/article/details/6278394 node 1#xff1a;最小路径覆盖 在一个#xff30;#xff38;#xff30;的有向图中#xff0c;路径覆盖就是在图中找一些路经#xff0c;使之覆盖了图中的 所有顶点#xff0c;且任何一个顶…来自http://blog.csdn.net/l04205613/article/details/6278394 node 1最小路径覆盖 在一个的有向图中路径覆盖就是在图中找一些路经使之覆盖了图中的 所有顶点且任何一个顶点有且只有一条路径与之关联如果把这些路径中的每条路径从它的起始点走到它的终点那么恰好可以经过图中的每个顶点一次且仅一 次如果不考虑图中存在回路那么每条路径就是一个弱连通子集 由上面可以得出 .一个单独的顶点是一条路径 如果存在一路径p1,p2,......pk其中p1 为起点pk为终点那么在覆盖图中顶点p1,p2,......pk不再与其它的顶点之间存在有向边 最小路径覆盖就是找出最小的路径条数使之成为的一个路径覆盖 路径覆盖与二分图匹配的关系 最小路径覆盖最大匹配数 其中最大匹配数的求法是把中的每个顶点pi分成两个顶点pi与pi如果在p中存在一条pi到pj的边那么在二分图中就有一条连接pi与pj的无向边这里pi 就是p中pi的出边pj就是p中pj 的一条入边 对于公式最小路径覆盖最大匹配数 可以这么来理解 如果匹配数为零那么中不存在有向边于是显然有 最小路径覆盖最大匹配数 即的最小路径覆盖数为 中不在于匹配边时路径覆盖数为 如果在中增加一条匹配边pipj那么在图P的路径覆盖中就存在一条由pi连接pj的边也就是说pi与pj 在一条路径上于是路径覆盖数就可以减少一个 如此继续增加匹配边每增加一条路径覆盖数就减少一条直到匹配边不能继续增加时路 径覆盖数也不能再减少了此时就有了前面的公式但是这里只是说话了每条匹配边对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边下面来说明一 个路径覆盖中的每条连接两个顶点之间的有向边对应于一条匹配边 与前面类似对于路径覆盖中的每条连接两个顶点之间的每条有向边 pi---pj我们可以在匹配图中对应做一条连接pi与pj的边显然这样做出来图的是一个匹配图这一点用反证法很容易证明如果得到 的图不是一个匹配图那么这个图中必定存在这样两条边 pi---pj 及 pi ----pkj!k那么在路径覆盖图中就存在了两条边pi--pj, pi---pk 那边从pi出发的路径就不止一条了这与路径覆盖图是矛盾的还有另外一种情况就是存在pi---pj,pk---pj这种情况也类似可证 至此就说明了匹配边与路径覆盖图中连接两顶点之间边的一一对应关系那么也就说明了前面的公式成立 摘自http://www.cppblog.com/SHFACM/archive/2009/02/05/73050.html 下面的几道题都是这类题目可以练练手 zoj 1364 || poj 1325 zoj 1525 || poj 1422 node 2最小点覆盖 二分图中选取最少的点数使这些点和所有的边都有关联把所有的边的覆盖叫做最小点覆盖。 最小点覆盖数 最大匹配数 证明http://hi.baidu.com/keeponac/blog/item/1764bec86f820f8dc91768b7.html node 3最大独立点集 在一个二分图中,选择一些顶点,使得所选择的点集中任意两个顶点之间没有边相连 可以证明最大独立顶点集 总顶点数 - 最大匹配数 摘自http://my.opera.com/IloveLunamaria/blog/show.dml/810972 PS由上面结论可得最小覆盖点集和最大独立点集互补即 最小点覆盖 最大独立点集 总顶点数 类似的在带点权的二分图中最小点权覆盖集 最大点权独立集 总权和转载于:https://www.cnblogs.com/gongxijun/p/3928021.html
