§ 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,令