最大流问题图和收发点

一个图是由点集V={v_i}和V中元素的无序对的一个集合E={e_k}所构成的二元组，记为G=(V,E)，V中的元素v_i叫做顶点，E中的元素e_k，叫做边。

仅有一个入次为0的点v_s称为发点(源)，一个出次为0的点v_t称为收点(汇)，其余点为中间点，这样的网络G称为容量网络，常记做G=(V,E,C)。

最大流问题容量和流量

设有向连通图G=(V,E)，G的每条边(v_i,v_j)上的非负数c_ij称为边的容量。对任一G中的边(v_i,v_j)有流量f_ij，称集合f={f_ij}为网络G上的一个流。图1即为一个有向连通图，括号中第一个数字代表容量，第二个数字代表流量。

最大流问题可行流

称满足下列两个条件的流为可行流：

1.容量限制条件：对G中的每条边(v_i,v_j)，有0≤f_ij≤c_ij；即每条边上的流量非负而且最大也只能达到容量的限制。

2.平衡条件：对中间点v_i，有

对发、收点v_s,v_t,，有

一个流f={f_ij}，当f_ij=c_ij，则称流f对边(vi,vj)是饱和的，否则称f对(v_i,v_j)不饱和。

最大流问题割（截）集

容量网路G=(V,E,C),v_s,v_t为发、收点，若有边集E‘为E的子集，将G为两个子图G₁,G₂，即点集V被剖分其为两个顶点集合分别记

1.若把整个截集的弧从网络G=(V,E,C)中丢去，则不存在从v_s和vt的有向路，即图(V,E-E')不连通。

2.只要没把整个截集删去，就存在从v_s和vt的有向路，即当E’‘为E的真子集，图G(V,E-E'')仍连通。

由此可知，截集是从起点v_s到终点v_t的必经之路。

割集

由割集的定义不难看出，无论拿掉那个割集，发点v_s到收点v_t便不再相通，所以任何一个可行流都会经过割集，且不会超过任一割集的容量。最小割如同瓶颈一般，即使是最大流也无法超过最小割，网络的最大流与最小割容量满足下面的定理（证明略）。

最大流问题定理一

设f为网络G=(V,E,C)的任一可行流，流量为v(f)，

最大流问题定理二

由定理一可知，最大流的流量v(f)和某一割集K的容量相等，而且最大流的流量本身也不带任一割集的容量，因此割集一定是最小的割集。

任一网络G中，从v_s到v_t的最大流的流量等于分离v_s、v_t的最小割的容量（最小的割集的容量）。

最大流问题前后向弧

一条从起点v_s到终点vt的链μ，规定从v_s到v_t的方向为链μ的方向，链上与μ方向一致的边叫前向弧（边），记作μ^-；与μ方向相反的边称为后向弧（边），记作μ 。

最大流问题可增广链

f是一个可行流，f_ij表示由i点指向j点的流量，如果满足前向弧的流量非负且小于容量，或后向弧的流量大于0且不超过容量：

则称μ为从v_s到v_t的关于f的可增广链。

可增广链的实际意义是：沿着这条从v_s到v_t输送的流，仍有潜力可挖，只要前向弧的流量增加或后向弧的流量减少，就可以将截集的流量提高。调整后的流，在各点仍满足平衡条件及容量限制条件，仍为可行流。

从另一个角度来说，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要条件是不存在从v_s到v_t的可增广链。

最大流问题是一类应用极为广泛的问题，例如在交通网络中有人流、车流、货物流，供水网络中有水流，金融系统中现金流，等等。求最大流的标号算法最早由福特和福克逊于1956年提出，20世纪50年代福特(Ford)、福克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。

最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流f*，使其流量v(f)达到最大， 这种流f称为最大流，这个问题称为(网络)最大流问题。最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。

最大流问题可以建立如下形式的线性规划数学模型：

式中v(f)称为这个可行流的流量、发点的净输出量或收点的净输出量。∞一般用标号法寻求有向最大流比用求线性规划问题的一般方法要方便得多。

最大的标号算法还用于解决多发点多收点网络的最大问题，设容量网络G有若干个发点x₁,x₂,...,x_m；若干收点y₁,y₂,...,y_n，可以添加两个新点vs,vt，用容量为∞的有向边分别连接两个新点v_s与点x₁,x₂,...,x_m，点y₁,y₂,...,y_n与v_t，得到新的网路G‘。G’是一个只有一个收点和发点的网络，求解最大流问题即可都得到G的解。

最大流问题算法思路

从可行流和可增广链关系来看，就可以知道一种寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。 v这种算法由Ford 和 Fulkerson于1956年提出，故又称 　Ford-Fulkerson标号法。

最大流问题算法步骤

标号的方法可分为两步：第一步是标号过程，通过标号来寻找可增广链；第二步是调整过程，沿可增广链调整f以增加流量。

1.标号过程

（1）给发点（始点）以标号(△, ∞)或(0, ∞)。

（2）选择一个已标号的顶点v_i，对于v_i的所有未给标号的邻接点v_j按下列规则处理：

(a)若后向边(v_j,v_i)∈E，且f_ji>0时，则令δ_j=min(f_ji,δ_i)，并给v_j以标号(-v_i,δ_j)，这表明v_j点的v_i点的边最多可以减少δ_j的流量以提高整个网络的流量。

(b)若前向边(v_i,v_j)∈E，且f_ij

括弧内的第一个数字表示这个节点得到的得到标号前的第一个结点的代号，第二个数字表示从上个标号节点到这个标号节点允许的最大调整量δ，假定发点的调整量不限，所以标记为 ∞。

（3）重复（2）直到收点v_t被标号或不再有顶点可被标号为止。

若v_t没有得到标号，说明标号过程已无法进行，可行流f已是最大流。若v_t得到标号，说明存在一条可增广链，转入调整过程。标号若有多条增广链时，不用刻意考虑哪种调整更适合，只需一条一条地转入调整过程，不用全盘考虑。

2.调整过程

（1）令这条被找到的增广链中所有的前向弧全部加上δ_j的流量，所有的后向弧全部减去δ_j的流量，至于不在增广链之中的边的流量则不需要调整。

（2）去掉所有标号，回到第1步，对可行流f’重新标号。

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。

在实际中：n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。

解决最小费用最大流问题，一般有两条途径。一条途径是先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。

然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进。另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解靠近（直至最大流时才是一个可行解）。

由于第二种算法和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。

在这一算法中，为了寻求最小费用的增流链，对每一当前流，需建立伴随这一网络流的增流网络。例如图 1 网络G 是具有最小 费用的流，边旁参数为c(e),f(e),w(e），而图 2 即为该网络流 的增流网络G′。增流网络的顶点和原网络相同。按以下原则建 立增流网络的边：若G中边（u，v）流量未饱，即f(u,v) < e(u,v），则G ' 中建边（u,v），赋权w ' (u,v)=w(u,v）；若G中边（u,v）已有流量，即f(u,v）〉0，则G′中建边（v,u），赋权w′（v,u) =-w(u,v）。建立增流网络后，即可在此网络上求源点至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流。

计算中有一个问题需要解决。这就是增流网络G ′中有负权边，因而不能直接应用标号法来寻找x至y的最短路径，采用其它计算有负权边的网络最短路径的方法来寻找x至y的最短路径，将 大大降低计算效率。为了仍然采用标号法计算最短路径，在每次建立增流网络求得最短路径后，可将网络G的权w(e）做一次修正，使再建的增流网络不会出现负权边，并保证最短路径不至于因此而改变。下面介绍这种修改方法。当流值为零，第一次建增流网络求最短路径时，因无负权边，当然可以采用标号法进行计算。为了使以后建立增流网络时不出现负权边，采取的办法是将 G中有流边（f(e)>0）的权w(e）修正为0。为此， 每次在增流网络上求得最短路径后，以下式计算G中新的边权w " (u,v）：

w " (u,v)=L(u)-L(v) w(u,v) (*)

式中 L(u),L(v) -- 计算G′的x至y最短路径时u和v的标号值。第一次求最短径时如果（u,v）是增流路径上的边， 则据最短 路径算法一定有 L(v)=L(u) w ' (u,v)=L(u) w(u,v）， 代入（*）式必有

w″（u,v)=0。

如果（u,v）不是增流路径上的边，则一定有：

L(v）≤L(u) w(u,v）， 代入（*）式则有 w(u,v）≥0。

可见第一次修正w(e）后，对任一边，皆有w(e）≥0， 且有流 的边（增流链上的边），一定有w(e)=0。以后每次迭代计算，若 f(u,v)>0，增流网络需建立（v,u）边，边权数w ' (v,u)=-w(u,v) =0，即不会再出现负权边。 此外，每次迭代计算用（*）式修正一切w(e）， 不难证明对每一条x至y的路径而言，其路径长度都同样增加L(x)-L(y）。因此，x至y的最短路径不会因对w(e）的修正而发生变化。

【计算步骤】

⒈ 对网络G=[V,E,C,W]，给出流值为零的初始流。

⒉ 作伴随这个流的增流网络G′=[V′，E′，W′]。G′的顶点同G：V′=V。若G中f(u,v)0，则G′中建边（v,u），w′（v,u)=-w(u,v）。

⒊ 若G′不存在x至y的路径，则G的流即为最小费用最大流， 停止计算；否则用标号法找出x至y的最短路径P。

⒋ 根据P，在G上增流：对P的每条边（u,v），若G存在（u,v），则（u,v）增流；若G存在（v,u），则（v,u）减流。增（减）流后，应保证对任一边有c(e）≥ f(e）≥0。

⒌ 根据计算最短路径时的各顶点的标号值L(v），按下式修 改G一切边的权数w(e):

L(u)-L(v) w(e）→w(e）。

⒍ 将新流视为初始流，转2。

在图论中，网络流（英语：Network flow）是指在一个每条边都有容量（capacity）的有向图分配流，使一条边的流量不会超过它的容量。通常在运筹学中，有向图称为网络。顶点称为节点（node）而边称为弧（arc）。一道流必须匹配一个结点的进出的流量相同的限制，除非这是一个源点（source）──有较多向外的流，或是一个汇点（sink）──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。