网络流应用

2018-02-07 07:52:50来源:cnblogs.com作者:自为风月马前卒人点击

分享

刷了一天最大流的题,都快刷晕了,,

简单总结几个模型吧。

大部分内容来自学姐的PPT

拆点

一个非常有用的思想
限流 将对点的限制转化为对边的限制

点的合并

这个还没看到

最小割

最小割==最大流

一条增广路中,必有一条边满流,满流的流量即为这条增广路的流量,那么删除满流的这条边即可阻断一条增广路。删去一些边使源汇不连通即阻断所有的增广路,代价之和即为最大流。

最大流=最小割 你能想到什么?

大与小的转换
留下最多与拿走最少的转换
最大收益与最小损失的转换
选最优与不选最差的转换

什么时候转换?
凭直觉,看经验

最大流,每条增广路流量实际上是增广路上的最小流量

INF边

不会割掉不合法方案
使不合法方案经过inf边,从而保证割出的方案合法

对偶图

还没看

点覆盖集

点覆盖集是无向图 的一个点集,使得该图中所有边都至少有一个端点在该集合内。
最小点覆盖集是在无向图中,点数最少的点覆盖集。
最小点权覆盖集是在带点权无向图中,点权之和最小的点覆盖集。

最小点覆盖集=二分图最大匹配数
证明:
边分为匹配边和未匹配边
未匹配边一定至少有一个点被选中,否则会增加一个新的匹配,与最大匹配不符

最小点权覆盖=二分图最小割
证明:
把每一个匹配看做一条增广路,那么就是选一些点,使剩下的点两两之间无法连通,即割一些点使图不连通,即最小割

点独立集

点独立集是无向图 的一个点集,使得任两个在该集合中的点在原图中都不相邻。
最大点独立集是在无向图 中,点数最多的点独立集。
最大点权独立集是在带点权无向图中,点权之和最大的点独立集。

最大点独立集=V-最小点覆盖集
最大点独立集=V-二分图最大匹配数
证明:
1、当删去最小覆盖集时,剩下的点一定不会有连边,即剩下的点在原图中一定不相邻,所以最大点独立集至少包含非最小点覆盖集的所有点
2、点覆盖集已经是最小,即最小点覆盖集中如果再删去点v,v必将和独立集中的点有边相连,不符合独立集的概念,所以最大点独立集至多包含非最小点覆盖集的所有点
3、综上所述,最大点独立集=V-最小点覆盖集

最大点权独立集=总点权-最小点权覆盖集
最大点权独立集=总点权-二分图最小割

最大流——最小割
最大点独立集——最小点覆盖集

路径覆盖

路径覆盖就是在一个DAG(有向无环图)中找一些路经,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联。
最小路径覆盖就是最少的路径条数的路径覆盖。

最小路径覆盖=V-二分图最大匹配数
证明:
若匹配数为0,因为每个点都是一条路径,所以最小路径覆盖数为V;
当有一个匹配出现时,路径数就减1

边覆盖

边覆盖集是无向图的一个边集,使得该图中所有顶点都至少是集合内边的一个端点。

最小边覆盖集是在无向图中,边数最少的边覆盖集。
最小边覆盖=最大点独立集

闭合子图

有向图的闭合子图是一个点集,该点集的所有出边都还指向该点集
闭合子图中,点权和最大的点集称为最大权闭合子图

正点权和-最小割

最大密度子图

没看

01分数规划

没看

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台