一.网络流:流&网络&割


1.网络流问题(NetWork Flow Problem):


给定指定的一个有向图,其中有两个特别的点S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满意条件的从S到T的最大流(MaxFlow).

The network flow problem considers a graph G with a set of sources S and sinks T and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from S to T while respecting the given edge capacities.

http://mathworld.wolfram.com/NetworkFlow.html


下面给出一个浅显点的解说

(下文根本避开形式化的证明 根本都用此类描绘叙说)

比如你家是自来水厂(有需求的同学可以把自来水厂当成银行之类 以下相似)是源,然后自来水厂和你家之间修了许多条水管子接在一同 水管子标准纷歧 有的容量大 有的容量小,然后问自来水厂开闸放水 你家收到水的最大流量是多少,假如自来水厂停水了 你家那的流量便是0 当然不是最大的流量,可是你给自来水厂交了100w美金 自来水厂拼命水管里通水 可是你家的流量也就那么多不变了 这时就到达了最大流。


2.三个根本的性质:


1假如 C代表每条边的容量 F代表每条边的流量,一个明显的实事是F小于等于C 不然水管子就爆了。这便是网络流的第一条性质 容量约束(CapacityConstraints):F<x,y> ≤ C<x,y>


2)再考虑节点恣意一个节点 流入量总是等于流出的量 不然就会蓄水(爆破风险...)或许无缘无故多出水(有地下水涌出?),这是第二条性质 流量守恒(Flow Conservation):Σ F<v,x> = Σ F<x,u>


3)当然源和汇不必满意流量守恒 咱们不必去关怀自来水厂的水是河里的 仍是江里的。最终一个不是很明显的性质 是斜对称性(Skew Symmetry): F<x,y> = - F<y,x>

这其实是完善的网络流理论不行短少的 就比如中学物理里用正负数来界说一维的位移相同,百米起点到百米结尾的位移是100m的话 那么结尾到起点的位移便是-100m,相同的 x向y流了F的流 y就向x流了-F的流。


3.容量网络&流量网络&残留网络:


网络便是有源汇的有向图 关于什么便是指边权的含义是什么。

1)容量网络便是关于容量的网络 根本是不改动(极少数问题需求变化)

2)流量网络便是关于流量的网络 在求解问题的过程中,,通常在不断的改动 可是总是满意上述三个性质,调整到最终便是最大流网络 一同也可以得到最大流值。

3)残留网络往往归纳了容量网络和流量网络 是最为常用的残留网络=容量网络-流量网络,这个等式是一直建立的 残留值当流量值为负时甚至会大于容量值,流量值为什么会为负?有正必有负,记住斜对称性!


4.割&割集:


无向图的割集(Cut Set):C[A,B]是将图G分为A和B两个点集 A和B之间的边的全集

A set of edges of a graph which, if removed (or "cut"), disconnects the graph (i.e., forms a disconnected graph).


网络的割集:C[S,T]是将网络G分为s和t两部分点集 S归于s且T归于t S到T的边的全集

带权图的(Cut)便是割会集边或许有向边的权和

Given a weighted, undirected graph G=(V,E) and a graphical partition of V into two sets A and B, the cut of G with respect to A and B is defined as cut(A,B)=sum_(i in A,j in B)W(i,j),where W(i,j) denotes the weight for the edge connecting vertices i and j. The weight of the cut is the sum of weights of edges crossing the cut.


浅显的了解一下:

割集比如是一个恐怖分子 把你家和自来水厂之间的水管网络砍断了一些

然后自来水厂不管怎样放水 水都只能从水管断口哗哗流走了 你家就停水了,割的巨细应该是恐怖分子应该关怀的事 究竟细管子好割一些,而最小割花的力气最小。


二.核算最大流的根本算法


那么怎样求出一个网络的最大流呢?

这儿介绍一个最简略的算法:Edmonds-Karp算法 即最短途径增广算法 简称EK算法。

EK算法依据一个根本的办法:Ford-Fulkerson办法 即增广路办法 简称FF办法。

增广路办法是许多网络流算法的根底 一般都在残留网络中完结,其思路是每次找出一条从源到汇的可以添加流的途径 调整流值和残留网络 不断调整直到没有增广路停止。

FF办法的根底是增广路定理(Augmenting Path Theorem):网络到达最大流当且仅当残留网络中没有增广路。

证明略 这个定理应该可以承受的吧

EK算法便是不断的找最短路 找的办法便是每次找一条边数最少的增广 也便是最短途径增广

这样就产生了三个问题:


1.最多要增广多少次?

可以证明 最多O(VE)次增广 可以到达最大流 证明略。


2.怎么找到一条增广路?

先清晰什么是增广路 增广路是这样一条从s到t的途径 途径上每条边残留容量都为正。把残留容量为正的边设为可行的边 那么咱们就可以用简略的BFS得到边数最少的增广路。


3.怎么增广?

BFS得到增广路之后 这条增广路可以增广的流值 是途径上最小残留容量边决议的,把这个最小残留容量MinCap值加到最大流值Flow上 一同途径上每条边的残留容量值减去MinCap,最终 途径上每条边的反向边残留容量值要加上MinCap 为什么? 下面会详细解说,这样每次增广的复杂度为O(E) EK算法的总复杂度便是O(VE^2),事实上 大多数网络的增广次数很少 EK算法能处理绝大多数问题,均匀含义下增广路算法都是很快的

,增广路算法比如是自来水公司不断的往水管网里一条一条的通水

上面还遗留了一个反向边的问题: 为什么增广途径上每条边的反向边残留容量值要加上MinCap?由于斜对称性! 由于残留网络=容量网络-流量网络

容量网络不改动的情况下,由于增广比如给增广路上通了一条流 途径说所有边流量加MinCap,流量网络中途径上边的流量加MinCap 反向边流量减去MinCap,相对应的残留网络就发作相反的改动,这样咱们就完结了EK算法 详细完结可以用邻接表存图 也可以用邻接矩阵存图。

接表存图 由于流量一同存在于边与反向边 为了便利求取反向边 建图把一对互为反向边的边建在一同。

代码很简略 最好自己完结一下

看一个详细的增广路算法的比如吧

.最大流最小割定理


下面介绍网络流理论中一个最为重要的定理

最大流最小割定理(Maximum Flow, Minimum Cut Theorem):网络的最大流等于最小割

The maximum flow between vertices v_i and v_j in a graph G is exactly the weight of the smallest set of edges to disconnect G with v_i and v_j in different components.


详细的证明分三部分


1.恣意一个流都小于等于恣意一个割

这个很好了解 自来水公司随意给你家通点水 构成一个流,恐怖分子随意砍几刀 砍出一个割,由于容量约束 每一根的被砍的水管子流出的水流量都小于管子的容量,每一根被砍的水管的水原本都要到你家的 现在流到外面 加起来得到的流量仍是等于本来的流,管子的容量加起来便是割 所以流小于等于割,由于上面的流和割都是恣意结构的 所以恣意一个流小于恣意一个割。


2.结构出一个流等于一个割

当到达最大流时 依据增广路定理,残留网络中s到t现已没有通路了 不然还能持续增广,咱们把s能到的的点集设为S 不能到的点集为T,结构出一个割集C[S,T] S到T的边必定满流 不然就能持续增广,这些满流边的流量和便是当时的流即最大流,把这些满流边作为割 就结构出了一个和最大流持平的割。


3.最大流等于最小割

设持平的流和割分别为Fm和Cm,则由于恣意一个流小于等于恣意一个割

恣意F≤Fm=Cm≤恣意C,定理阐明完结。


.简略的使用


Poj 1459是一个很典型的网络流使用

把电流幻想成水流。


意把多源多汇转化为单源单汇即可使用EK算法解决问题,网络流的使用还有许多 化归的思维是网络流最具魅力的当地。

代码如下:


修改|收拾 邹豪杰


推荐阅读