网络流(一)基础知识篇

摘要:
那么P被称为关于可行流f的增广路径,简称为增广路径。相关定理剩余网络和原始网络之间的关系设f为容量网络G(V,E)的可行流,f’为剩余网络G’的可行流。则f+f’仍然是容量网络G的可行流,如果任何流量为f,任何切割为(S,T),则必须存在,即网络流量小于或等于任何切割的容量。
传送门:网络流(一)基础知识篇网络流(二)最大流的增广路算法网络流(三)最大流最小割定理网络流(四)dinic算法网络流(五)有上下限的最大流网络流(六)最小费用最大流问题  转载自:https://blog.csdn.net/txl199106/article/details/64441994 网络流入门

基本概念(从书上摘抄,可以直接跳过不看)

容量网络和网络最大流

容量网络: 设 G(V, E)是一个有向网络, 在 V 中指定了一个顶点, 称为源点(记为 Vs ), 以及另一个顶点, 称为汇点(记为 Vt); 对于每一条弧 <u, v>∈E, 对应有一个权值 c(u, v)>0, 称为弧的容量, 通常把这样的有向网络 G 称为容量网络。

也就是指: 一个拥有源点、汇点并且可以容纳流量的图.

弧的流量: 通过容量网络 G 中每条弧 <u, v> 上的实际流量(简称流量), 记为 f(u, v)
网络流: 所有弧上流量的集合 f = { f(u, v) },称为该容量网络 G 的一个网络流。
可行流: 在容量网络 G(V, E) 中, 满足以下条件的网络流 f, 称为可行流:

  • 弧流量限制条件: 
  • 平衡条件: 除了 Vs, Vt 外, 其余的点流入的流量总和等于流出的流量总和, 其中 Vs 流出的流量总和 - 流出的流量总和 = fVt 流入的流量总和 - 流出的流量总和 = f, 并且称 f 为可性流的流量.

也就是指: 在图中有一条从 Vs 到 Vt 的路径, 这条路径上起点 , 终点 , 其他的点 , 并且所有的边的当前流量小于等于最大流量.(其中  代表流入流量,  代表流出流量)

伪流: 如果一个网络流只满足弧流量限制条件, 不满足平衡条件, 则这种网络流称为伪流, 或称为容量可行流。
最大流: 在容量网络 G(V, E) 中, 满足弧流量限制条件和平衡条件、且具有最大流量的可行流, 称为网络最大流, 简称最大流。

链与增广路

在容量网络 G(V, E) 中, 设有一可行流 f = { f(u, v) }, 根据每条弧上流量的多少、以及流量和容量的关系,可将弧分四种类型:

  • 饱和弧, 即 ;
  • 非饱和弧,即 ;
  • 零流弧, 即 ;
  • 非零流弧, 即 。

链: 在容量网络中,称顶点序列为一条链,要求相邻两个顶点之间有一条弧, 如 <u, u1> 或 <u1, u> 为容量网络中一条弧。沿着 Vs 到 Vt 的一条链, 各弧可分为两类:

  • 前向弧: 方向与链的正方向一致的弧, 其集合记为 P+;
  • 后向弧: 方向与链的正方向相反的弧, 其集合记为 P-;

增广路: 设 f 是一个容量网络 G 中的一个可行流, P 是从 Vs 到 Vt 的一条链, 若 P 满足下列条件:

  • 在 P 的所有前向弧 <u, v> 上, , 即 P+ 中每一条弧都是非饱和弧;
  • 在 P 的所有后向弧 <u, v> 上, , 即 P– 中每一条弧是非零流弧。

则称 P 为关于可行流 f 的一条增广路, 简称为 增广路(或称为增广链、可改进路)。沿着增广路改进可行流的操作称为增广

残留容量与残留网络

残留容量: 给定容量网络 G(V, E) 及可行流 f, 弧 <u, v> 上的残留容量记为 。每条弧的残留容量表示该弧上可以增加的流量。因为从顶点 u 到顶点 v 流量的减少, 等效于顶点 v 到顶点 u 流量增加, 所以每条弧 <u, v> 上还有一个反方向的残留容量 。

一个容量网络中还可以压入的流量称为残留容量

残留网络: 设有容量网络 G(V, E) 及其上的网络流 f,G 关于 f 的残留网络(简称残留网络)记为 G'(V', E'), 其中 G’的顶点集 V’和 G 的顶点集 V 相同,即 V’=V, 对于 G 中的任何一条弧 <u, v>, 如果 , 那么在 G’中有一条弧 <u, v>∈E', 其容量为 , 如果 ,则在 G’中有一条弧 <v, u>∈E', 其容量为 , 残留网络也称为剩余网络.

由残留的容量以及源点汇点构成的网络。

割与最小割

割: 在容量网络 G(V, E) 中, 设 E'⊆E, 如果在 G 的基图中删去 E’ 后不再连通, 则称 E’ 是 G 的割。割将 G 的顶点集 V 划分成两个子集 S 和 T = V - S。将割记为(S, T)。
s-t 割: 更进一步, 如果割所划分的两个顶点子集满足源点 Vs ∈ S,汇点 Vt ∈ T, 则称该割为 s-t 割。 s-t 割(S, T)中的弧 <u, v>(u∈S, v∈T) 称为割的前向弧, 弧 <u, v>( u∈T, v∈S) 称为割的反向弧。
割的容量: 设 (S, T) 为容量网络 G(V, E) 的一个割, 其容量定义为所有前向弧的容量总和, 用 c(S, T) 表示。
最小割: 容量网络 G(V, E) 的最小割是指容量最小的割。

相关定理

残留网络与原网络的关系

设 f 是容量网络 G(V, E) 的可行流, f’ 是残留网络 G’ 的可行流, 则 f + f’ 仍是容量网络 G 的一个可行流。(f + f’ 表示对应弧上的流量相加)

网络流流量与割的净流量之间的关系

在一个容量网络 G(V, E) 中, 设其任意一个流为 f, 关于 f 的任意一个割为(S, T), 则有 ,即网络流的流量等于任何割的净流量。

网络流流量与割的容量之间的关系

在一个容量网络 G(V, E) 中, 设其任意一个流为 f, 任意一个割为(S, T), 则必有 ,即网络流的流量小于或等于任何割的容量。

最大流最小割定理

对容量网络 G(V, E), 其最大流的流量等于最小割的容量。

增广路定理

设容量网络 G(V, E) 的一个可行流为 f, f 为最大流的充要条件是在容量网络中不存在增广路。

几个等价命题

设容量网络 G(V, E)的一个可行流为 f 则:

  • 1) f 是容量网络 G 的最大流;
  • 2) | f |等于容量网络最小割的容量;
  • 3) 容量网络中不存在增广路;
  • 4) 残留网络 G’中不存在从源点到汇点的路径。

免责声明:文章转载自《网络流(一)基础知识篇》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇前端-Vue基础1Android系统架构(图解)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

(四)AppScan用外部设备(ios,安卓)录制app脚本进行安全测试

一、打开AppScan,选择外部设备/客户机,点击下 二、记录代理设置,可以手动输入需要的端口号,也可以自动选择。 手机配置代理: 1.连接wifi 2.找到该wifi--高级设置--配置代理: 三、SSL证书,点击下一步 四、安装好证书以后,点击登陆管理 在手机上打开app,打开登录界面后,点击记录按钮 可以看到设备已连接,执行完登录按钮后,...

深入剖析全链路灰度技术内幕

作者:扬少 当服务有新版本要发布上线时,通过引流一小部分流量到新版本,可以及时发现程序问题,有效阻止大面积故障的发生。业界上已经有比较成熟的服务发布策略,比如蓝绿发布、A/B 测试以及金丝雀发布,这些发布策略主要专注于如何对单个服务进行发布。在微服务体系架构中,服务之间的依赖关系错综复杂,有时某个功能发版依赖多个服务同时升级上线。我们希望可以对这些服务的新...

思考:如何保证服务稳定性?

思考:如何保证服务稳定性? 最近一直在忙618大促的全链路压测&稳定性保障相关工作,结果618还未开始,生产环境就出了几次生产故障,且大多都是和系统稳定性、性能相关的bad case。 生产全链路压测终于告一段落,抽出时间将个人收集的稳定性相关资料整理review了一遍,顺带从不同的维度,谈谈稳定性相关的“务虚”认知和思考。。。 一、SLA! 在开...

Android流量统计

项目中需要对Android设备进行流量统计来进行资费结算,所以对Android设备流量统计进行了一些调研。发现流量统计主流上有两种方式 使用系统统计类TrafficStats获取 通过系统文件解析读取 TrafficStats static long getMobileRxBytes() //获取通过Mobile连接收到的字节总数,不包含WiFi s...

限流的几种方式

先来描述一下什么是限流   限流可以认为服务降级的一种,限流就是限制系统的输入和输出流量已达到保护系统的目的。一般来说系统的吞吐量是可以被测算的,为了保证系统的稳定运行,一旦达到的需要限制的阈值,就需要限制流量并采取一些措施以完成限制流量的目的。比如:延迟处理,拒绝处理,或者部分拒绝处理等等。 一般做接口限流主要是为了应对突发流量,避免突发流量拖垮服务。如...

PHP解决网站大流量与高并发

1:硬件方面   普通的一个p4的服务器每天最多能支持大约10万左右的IP,如果访问量超过10W那么需要专用的服务器才能解决,如果硬件不给力 软件怎么优化都是于事无补的。主要影响服务器的速度 有:网络-硬盘读写速度-内存大小-cpu处理速度。 2:软件方面     第一个要说的就是数据库   首先要有一个很好的架构,查询尽量不用* 避免相关子查询 给经常查...