概述
有很多问题可以抽象成顶点和有容量限制的边的网络。如何解决这类问题将是本章所要关注的。Ahuja(1993)对现有大量的网络流算法应用进行了深入的讨论。
任务分配
现在雇员们要完成一些任务,由于不同雇员在相同个任务上的花费不同,所以我们需要找到一种分配方式,使得总花费最小。
二部图匹配
有一些求职者需要面试一些工作,寻找到一个合理的分配方式,使得尽可能多的人能够找到能够胜任的工作。
运输问题
找到从工厂运输商品到零售商店性价比最高的方法。
转运问题
找到从工厂运输商品到零售商店性价比最高的方法,但是这类问题中,我们可以使用一些中转站作为临时仓库。
最大流
给定一个网络,网络中的每条边都有一个最大容量,计算出这个网络能够支持的最大流。
首先我们会阐述网络流问题之间的关系,这样能够帮助我们理解这些问题是如何解决的。图8-1描绘的是这些问题的关系。一条有向边将问题的一般化实例和问题的特例联系起来。例如运输问题就是转运问题的一个特例,因为运输图并不包含任何的中转节点。因此一个能够解决转运问题的程序肯定能够用于解决运输问题。
图 8-1 网络流问题之间的关系在本章中,我们将阐述Ford-Fulkerson算法。此算法用来解最大流问题。Ford-Fulkerson算法也可以直接用于二部图匹配问题,它们之间的关系如图8-1所示。而且,一旦理解了Ford-Fulkerson算法的基本原理,我们不难发现,Ford-Fulkerson算法的框架可以用来解决最小耗费流问题,例如转运问题、运输问题以及任务分配问题。
从理论上来说,你可以利用线性编程(LP)来解决图8-1的所有问题,但是你必须得先将这些问题转换成正确的线性表示形式,而且得到的解能够转换成原有的形式。在本章末尾,我们将会举例使用线性编程来解网络流问题。实际上,本章描述的特定算法解决图8-1的问题效率要比LP高数个数量级。
网络流
如图8-2所示,通常我们抽象出来的网络流模型是一个有向图G=(V,E),V是顶点集,E是边集。图是连通的(虽然并不是每条边都需要展示出来)。有一个源点s∈V,s生产商品,然后通过图的边运输到汇点t∈V消费(也称为终点或者目标点)。网络流假设能够生产无限多的商品,并且汇点能够消费完所有接收到的商品。
图 8-2 网络流图每条边(u,v)都有一个流f(u,v),表示从u运输到v的商品单位数目。同样每条边有一个容量c(u,v),表示从u运输到v的最大商品单位数。在图8-2中,每个顶点和每条边都做了标记,我们用数字标记顶点(源点和汇点用s和t标记),用f/c标记边,f/c表示一条边上的流容量以及最大的流容量。例如边(s,v1)标记为5/10,表示这条边上有5个单位的商品在通过这条边,这条边能够承受的最大容量为10个单位。当没有单位通过边(例如v5和v2的边),那么只会在一个灰色方格中标示容量。
在一个流通过网络时,必须满足如下的限制条件。
容量限制
通过一条边的流f(u,v)不能为负,而且不能超过边的容量c(u,v),即0≤f(u,v)≤c(u,v)。如果在网络中不存在边(u,v),那么c(u,v)=0。
流守恒
除开源点s和汇点t,每个顶点u∈V必须满足所有的入流等于所有的出流。这个性质确保了在网络中,除了源点和汇点,不会产生和消耗流。
反对称
从一致性角度来看,f(v,u)表示的是从顶点u到v的网络流。f(u,v)=-f(v,u),即使在一个有向图中存在两条边(u,v)和(v,u),这个性质也同样成立。
在接下来的算法中,我们使用一条网络路径<v1,v2,……,vn>,表示n-1条连续的边(vi,vj),这条网络路径中不存在环。在图8-2的有向图中,一条可能的网络路径是<v3,v5,v2,v4>。在一条网络路径中,我们忽略边的方向。图8-3的一条可能的网络路径是<s,v1,v4,v2,v3,t>。