§ 4 网络最大流问题 |
|
许多系统都包含了流量问题。例如公路系统中有车辆流,控制系统有信息流,供水系统有水流等等。 现在考虑这样一个问题:某物资有m个生产基地A1,A2,…,Am要通过铁路运到n个销地B1,B2,…,Bn去。把铁路网上的车站看作是顶点,两个车站间的铁路线看作是弧。可以认为在某条铁路线上可运送的物资数量是有限的,我们把某条线路上的允许最大运送量称为容量。这时要考虑如何安排运输方案,使得由产地运到销地的物资总量达到最大。这就是在这个运输网中,求最大流问题。 4.1 网络最大流概念 |
|
容量网络:在有向图D=(V,A),指定一个点为发点,记作
,指定另一个点为收点,记作
,其余点叫作中间点。对于A的每条弧(
),都对应一个权数
≥0,称为弧(
)的容量,将这样的赋权有向图叫作一个容量网络,记作D=(V,A,C)。 如果在一个网络中,有多个发点或收点,则我们可以将其变为只有一个发点和收点的网络。这只需增加一个新的总发点和一个新的总收点。从总发点到各个发点分别连接一条容量为+∞的弧,从各个收点到总收点分别连接一条容量为+∞的弧。这样就可将问题变为单发点和单收点的网络流问题。所以,以后我们只讨论一个发点和一个收点的网络流问题。 |
|
在网络中,将通过弧(
)的运量记作,并称之为弧(
)上的流量。 可行流:对于容量网络D=(V,A,C),每条弧( )都给定一个流量 ,当{}满足下列条件时,称为可行流。 1°容量限制:对每条弧( )∈A,有0≤ ≤。 2°平衡条件:对于中间点 ∈V,流入量等于流出量,即 ∑=∑。 对于发点 和收点 ,则有 发出总量等于 收到总量,即 ,称v(f)为可行流{}的流量。 |
|
如下图中,弧旁的数字分别为(
,),可以验证给出的流是可行流。 对于任何网络总是存在可行流的,比如令所有弧上的流都等于0,就可以得到一个可行流,其流量v(f) =0。 |
|
最大流:使v(f )达到最大的可行流称为最大流。 | |
4.2
计算最大流的标号法 |
|
这里介绍计算网络最大流的简便方法—标号法,此方法是Ford—Fulkerson 于1956年提出来的,它的原理是利用寻找增广链来不断改善可行流。 |
|
设μ是网络中
到 的一条链,规定
到 的方向为μ的方向。
μ上与μ的方向一致的弧称为前向弧,前向弧的集合记为μ+, μ上与μ的方向相反的弧称为后向弧,后向弧的集合记为μ-。 上图,链 |
|
若给一个可行流{},称网络中
=
的弧为饱和弧,称 <的弧为非饱和弧,称
=0的弧为零流弧,称
>0的弧为非零流弧。 |
|
增广链:设{}是可行流,
μ是
到 的一条链,若μ满足下列条件,则称μ为关于
f 的增广链。(注意: f ={}) 1°对于任何( ,)∈μ+,0≤ < (前向弧为非饱和弧) 2°对于任何( ,)∈μ-,0 <≤ (后向弧为非零流弧) 如图7-15中,μ={}就是一条增广链。 定理:可行流 f﹡是最大流,当且仅当不存在关于 f﹡的增广链。 证明:必要性:设 f﹡是最大流,若存在关于 f﹡的增广链μ,令 |
|
则θ >0,令
|
|