网络流应用
刷了一天最大流的题,都快刷晕了,,
简单总结几个模型吧。
大部分内容来自学姐的PPT
拆点
一个非常有用的思想
限流 将对点的限制转化为对边的限制
点的合并
这个还没看到
最小割
最小割==最大流
一条增广路中,必有一条边满流,满流的流量即为这条增广路的流量,那么删除满流的这条边即可阻断一条增广路。删去一些边使源汇不连通即阻断所有的增广路,代价之和即为最大流。
最大流=最小割 你能想到什么?
大与小的转换
留下最多与拿走最少的转换
最大收益与最小损失的转换
选最优与不选最差的转换
什么时候转换?
凭直觉,看经验
最大流,每条增广路流量实际上是增广路上的最小流量
INF边
不会割掉不合法方案
使不合法方案经过inf边,从而保证割出的方案合法
对偶图
还没看
点覆盖集
点覆盖集是无向图 的一个点集,使得该图中所有边都至少有一个端点在该集合内。
最小点覆盖集是在无向图中,点数最少的点覆盖集。
最小点权覆盖集是在带点权无向图中,点权之和最小的点覆盖集。
最小点覆盖集=二分图最大匹配数
证明:
边分为匹配边和未匹配边
未匹配边一定至少有一个点被选中,否则会增加一个新的匹配,与最大匹配不符
最小点权覆盖=二分图最小割
证明:
把每一个匹配看做一条增广路,那么就是选一些点,使剩下的点两两之间无法连通,即割一些点使图不连通,即最小割
点独立集
点独立集是无向图 的一个点集,使得任两个在该集合中的点在原图中都不相邻。
最大点独立集是在无向图 中,点数最多的点独立集。
最大点权独立集是在带点权无向图中,点权之和最大的点独立集。
最大点独立集=V-最小点覆盖集
最大点独立集=V-二分图最大匹配数
证明:
1、当删去最小覆盖集时,剩下的点一定不会有连边,即剩下的点在原图中一定不相邻,所以最大点独立集至少包含非最小点覆盖集的所有点
2、点覆盖集已经是最小,即最小点覆盖集中如果再删去点v,v必将和独立集中的点有边相连,不符合独立集的概念,所以最大点独立集至多包含非最小点覆盖集的所有点
3、综上所述,最大点独立集=V-最小点覆盖集
最大点权独立集=总点权-最小点权覆盖集
最大点权独立集=总点权-二分图最小割
最大流——最小割
最大点独立集——最小点覆盖集
路径覆盖
路径覆盖就是在一个DAG(有向无环图)中找一些路经,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联。
最小路径覆盖就是最少的路径条数的路径覆盖。
最小路径覆盖=V-二分图最大匹配数
证明:
若匹配数为0,因为每个点都是一条路径,所以最小路径覆盖数为V;
当有一个匹配出现时,路径数就减1
边覆盖
边覆盖集是无向图的一个边集,使得该图中所有顶点都至少是集合内边的一个端点。
最小边覆盖集是在无向图中,边数最少的边覆盖集。
最小边覆盖=最大点独立集
闭合子图
有向图的闭合子图是一个点集,该点集的所有出边都还指向该点集
闭合子图中,点权和最大的点集称为最大权闭合子图
正点权和-最小割
最大密度子图
没看
01分数规划
没看
推荐阅读
-
2018首届青少年手机健康应用论坛 引导新时代青少年健康成长
-
python网络爬虫学习笔记(1)
-
Python网络编程使用select实现socket全双工异步通信功能示例
-
Python网络编程基于多线程实现多用户全双工聊天功能示例
-
Python网络编程之TCP套接字简单用法示例
-
闭包在python中的应用之translate和maketrans用法详解
-
.NET Core应用类型(Portable apps & Self-contained apps)
-
关于.NET动态代理的介绍和应用简介
-
asp.net网络数据库开发实例精解 源文件
-
ASP.NET Core应用中与第三方IoC/DI框架的整合