最小路径覆盖，最小点覆盖，最大独立点集

青旅半醒 2022-08-02 06:06 190阅读 0赞

**node  1：最小路径覆盖**

**在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；**（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每条路径就是一个弱连通子集．  
由上面可以得出：  
１.一个单独的顶点是一条路径；  
２．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．  
最小路径覆盖就是找出最小的路径条数，使之成为Ｐ的一个路径覆盖．  
路径覆盖与二分图匹配的关系：  
最小路径覆盖＝｜Ｐ｜－最大匹配数；  
其中最大匹配数的求法是把Ｐ中的每个顶点pi分成两个顶点pi'与pi''，如果在p中存在一条pi到pj的边，那么在二分图Ｐ＇中就有一条连接pi'与pj''的无向边；这里pi' 就是p中pi的出边，pj''就是p中pj 的一条入边；

对于公式：最小路径覆盖＝｜Ｐ｜－最大匹配数；

可以这么来理解：

如果匹配数为零，那么Ｐ中不存在有向边，于是显然有：

最小路径覆盖＝｜Ｐ｜－最大匹配数＝｜Ｐ｜－０＝｜Ｐ｜；

即Ｐ的最小路径覆盖数为｜Ｐ｜；

Ｐ＇中不在于匹配边时，路径覆盖数为｜Ｐ｜；

如果在Ｐ＇中增加一条匹配边pi'－－＞pj''，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个；

如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式；但是这里只是说话了每条匹配边对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边；下面来说明一个路径覆盖中的每条连接两个顶点之间的有向边对应于一条匹配边；

与前面类似，对于路径覆盖中的每条连接两个顶点之间的每条有向边pi--->pj，我们可以在匹配图中对应做一条连接pi'与pj''的边，显然这样做出来图的是一个匹配图（这一点用反证法很容易证明，如果得到的图不是一个匹配图，那么这个图中必定存在这样两条边  pi'---pj'' 及 pi' ----pk''，（j!=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

在http://acm.hdu.edu.cn/showproblem.php?pid=1151中 It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles.**看出这一题是让你找出来最小的伞兵走完这个图里面所有的点，走出的路径不相交，所以是最小路径覆盖问题！**

**node  2：最小点覆盖**

二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最小点覆盖。  
最小点覆盖数 = 最大匹配数

证明：[http://hi.baidu.com/keeponac/blog/item/1764bec86f820f8dc91768b7.html][http_hi.baidu.com_keeponac_blog_item_1764bec86f820f8dc91768b7.html]

http://acm.hdu.edu.cn/showproblem.php?pid=1150

题目大意;有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式xi,如果它在机器B上运行，则机器A需要设置为模式yi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。

题目就成了我们选最少的点(机器模式)，可以邻接更多的线(任务),那么我们把邻接叫做覆盖，也就是说成了选最少的点，去覆盖尽可能多的边.....

**node  3：最大独立点集**

在一个二分图中,选择一些顶点,使得所选择的点集中任意两个顶点之间没有边相连

可以证明，最大独立顶点集 = 总顶点数 - 最大匹配数

摘自： [http://my.opera.com/IloveLunamaria/blog/show.dml/810972][http_my.opera.com_IloveLunamaria_blog_show.dml_810972]

http://acm.hdu.edu.cn/showproblem.php?pid=1068

**这是一题让你求最大独立集问题！独立集即一个点集，集合中任**

**两个结点不相邻，则称V为独立集。**

![Center][]

**比如上述图片！只有a1,a2,b0,b1可以放在一起组成最大独立**

**集，不能再放其他的了！**

**二分图最大独立集=点数n-二分图最大匹配。**

PS：由上面结论可得，最小覆盖点集和最大独立点集互补，即

最小点覆盖 + 最大独立点集 = 总顶点数

类似的，在带点权的二分图中，最小点权覆盖集 + 最大点权独立集 = 总权和

[http_hi.baidu.com_keeponac_blog_item_1764bec86f820f8dc91768b7.html]: http://hi.baidu.com/keeponac/blog/item/1764bec86f820f8dc91768b7.html
[http_my.opera.com_IloveLunamaria_blog_show.dml_810972]: http://my.opera.com/IloveLunamaria/blog/show.dml/810972
[Center]: /images/20220731/73c3118264a242a3b60f0287b5b2bf7e.png