欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

网络流应用

程序员文章站 2022-11-06 08:26:48
刷了一天最大流的题,都快刷晕了,, 简单总结几个模型吧。 大部分内容来自学姐的PPT 拆点 一个非常有用的思想 限流 将对点的限制转化为对边的限制 点的合并 这个还没看到 最小割 最小割==最大流 一条增广路中,必有一条边满流,满流的流量即为这条增广路的流量,那么删除满流的这条边即可阻断一条增广路。 ......

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

简单总结几个模型吧。

大部分内容来自学姐的PPT

拆点

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

点的合并

这个还没看到

最小割

最小割==最大流

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

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

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

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

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

INF边

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

对偶图

还没看

点覆盖集

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

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

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

点独立集

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

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

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

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

路径覆盖

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

网络流应用

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

边覆盖

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

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

闭合子图

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

正点权和-最小割
网络流应用

最大密度子图

没看

01分数规划

没看