流网络和可行流

流网络

有向图中有两个特殊的点是 源点 和 汇点,
流网络中的每条边都有一个属性,就是流网络的容量。


流网络对比到城市的自来水管道,每个点都是管道的交汇点,每条边都是一条水管。


边的容量就是水管每秒流过的水量。

  • 源点就是大的水库 ☞ 源源不断有无穷多的流量可以流出去。
  • 汇点可以是大海 ☞ 可以容纳无穷多的容量。


整体来看,就是从源点源源不断的把水通过每条管道,不断流向汇点的过程,这个图就被称为流网络。


image.png


流网络  G = ( V, E )

在流网络中是不考虑反向边的。


对于有反向边的图,需要等价的变成没有反向边的图


image.png  image.png

如果一条边不存在,则定义这条边的容量是0。

可行流

指定每条边的容量(即指定每条水管每秒流过的速率),只要满足两个条件,它就是一个可行的流。

  1. 满足容量限制   从 u 到 v 的流量
  2. 流量守恒 ☞ 整个网络里除了源点和汇点之外,其余所有点是不存储容量的。


对于任意的点x属于点集V(不包括源点和汇点),都有流入的流量等于流出的流量。


 表示一个方案,即每条边的取值。

对于某个可行流来说,那么每秒从源点流到汇点的流量具体是多少呢?这个定义为可行流的流量值用  表示。

  每秒从源点流出的所有流量 减去 流入源点的流量。一般没有后面的流入源点的流量。


对于一个流网络来说有很多可行流。最大流是最大可行流

最大流指的是:流网络的所有可行流中流量值最大的可行流。

原文地址:https://www.cnblogs.com/custer/p/13404191.html