1、网络最大流问题v1v2v4v3v5vtvsff624374317988 下图看做输油管道网，vs为起点，vt为终点，v1,v2,v3,v4,v5为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大？网络最大流问题 管道网络中每一弧的最大通过能力即容量是有限的，实际流量也并一定等于容量，此类问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为网络最大流问题。例 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量c
2、ij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6网络最大流问题基本概念：网络 定义：对有向图D=（V，A）:vs-始点 vt-终点 其余-中间点 c(vi，vj)-弧(vi，vj)的容量(capacity)，简写为cijD=(V，A，C)网络 网络流：定义在弧集合上的函数 f=f(vi，vj)，称为网络上的流(flow)，简称网络流。f(vi，vj)为弧（vi，vj）上的流量，简记为fij。可行流可行流满足:1.容量限制条件：ijijcf02.平衡条件：a.
3、中间点：b.发点净流出量收点净流入量v(f).v(f)称为可行流的流量jjiiijffv1v2v4v3v5vtvsff(6,3)(2,1)(4,1)(3,2)(7,3)(4,4)(3,2)(1,1)(7,1)(9,5)(8,2)(8,4)注:(容量，流量)使流量v(f)达到最大的可行流 fij 最大流最大流问题：tifvfftsiffsifvffAvvcftsfvMaxAvvjtAvvtjAvvjiAvvijAvvjsAvvsjjiijijtjjtijjisjjs )(,0 )(),(0.)(),(),(),(),(),(),(增广链（可增值链）v2v1(5，5)v2v1(5，3)v2v1(5
4、，0)v2v1(5，3)几个概念：未饱和弧饱和弧ijijijijcfcf1非零流弧零流弧 00ijijff2ttsvvvvs ),.,(定义链的方向网络中的一条链，3其全体记为的方向相反后向弧，弧的方向与链其全体记为的方向一致前向弧，弧的方向与链链-增广链：设 f 是一可行流，时从始点到终点的一条链，若满足下列条件，称其为一条增广链非零流弧对后向弧：未饱和弧对前向弧：ijijijijcfcf00v1v2v4v3v5vtvsff(6,3)(2,1)(4,1)(3,2)(7,3)(4,4)(3,2)(1,1)(7,1)(9,5)(8,2)(8,4)v1v2v4v3v5vtvsff(6,3)(2,0
5、)(4,2)(3,2)(7,3)(4,4)(3,2)(1,1)(7,1)(9,6)(8,2)(8,5)截割集与割集容量（截量）定义：的）截割集与（分离称为，则把弧集，且和被分为两个非空集合，若对网络tstsvvVVVvVvVVVCAVD),(),(_11_11_11),(),(_11_11_11_11),(),(),(VVvvijjicVVcVVcVV即：，量，记为为截集的容量，简称截中所有弧的容量之和称把截集定义：v1v2v4v3v5vtvsff(6,3)(2,0)(4,2)(3,2)(7,3)(4,4)(3,2)(1,1)(7,1)(9,6)(8,2)(8,5)v1v2v4v3v5vtvs
6、ff(6,3)(2,0)(4,2)(3,2)(4,4)(3,2)(1,1)(7,1)(9,6)(8,2)v1v2v4v3v5vtvsff(6,3)(2,0)(4,2)(3,2)(7,3)(4,4)(3,2)(1,1)(7,1)(9,6)(8,2)(8,5)v1v2v4v3v5vtvsff(2,0)(4,2)(3,2)(7,3)(3,2)(7,1)(9,6)(8,2)(8,5)v1v2v4v3v5vtvsff(6,3)(2,0)(4,2)(3,2)(7,3)(4,4)(3,2)(1,1)(7,1)(9,6)(8,2)(8,5)v1v2v4v3v5vtvsff(6,3)(2,0)(4,2)(3,2
7、)(7,3)(4,4)(7,1)(8,2)(8,5)vs其它各点(vs,v1)(vs,v2)15vs,v1,v2v3,v4 v5,vt(v1,v4)(v2,v3)(v2,v5)11vs,v1,v2v3,v4v5,vt(v3,v5)(v2,v5)(v4,vt)131V1V),(11VV),(11VVC基本定理：定理 1：（最大流最小割定理）最大流量最小截集容量),(11VVcMinfMaxij定理 2：增值链网络中不存在的是最大流可行流*ij*ijff 寻求网络最大流的方法：可行流 f有无关于可行流 的增广链？调整可行流无有最大流 寻求最大流的方法FordFord标号法Ford Ford 标号法
8、标号过程调整过程),(min)(:),(,0.,),(.3),(min)(:),(,.,),(.2.,.1jiijjijjijiijijijijjijijijjijissfvlvlvlvvfvvvvfcvlvlvlvvcfvvvvvv其中标号给非零流弧若未标号已标号后向弧考虑其中标号给非饱和弧若未标号已标号前向弧考虑标上给(I)标号过程(II)调整过程:沿增广链调整流量.),(),(),(),(_jiijjiijjiijijtvvfvvfvvffvl调整量 结局：vt 被标上号，反向追踪 vs，找出增广链 结局：vt 未被标上号，标号过程进行不下去，则算法结束，当前的可行流就是最大流 同时获得
9、最小截集 ，已标号点集，未标号点集弧集合即为 最小截集),(11VV1V1V),(11VVv1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsv1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vs,).1(ssvv 标上首先给vs,+v1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+415,min)(),(min)(:,)(,5,1,),(.,),().2(11111111112ssssssssssfc
10、vlvlvlvvcfcfvvvv其中标号为的则上考虑弧不满足标号条件上考虑弧vS,4v1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+vS,4.,2,2,),(.11,4min),(min)()(,01),().3(13133121122122112足标号条件不满考虑弧这里记下标号则给考虑弧cfvvfvlvlvlvvfvv-v1,1v1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+vS,4-v1,1.11,1min),(min)(,)(,01),().
11、4(32233333223fvlvlvlvvfvv这里记下标号为则给考虑弧-v2,1v1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+vS,4(-v1,1)-v2,1.,.11,1min)(),(min)(:),(,2,1),.().5(333333333标号过程结束标号其中的标号为给则考虑弧tttttttttttvfcvlvlvlvvcfcfvvv3,1v1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+vS,4-v1,1-v2,1v3,1v1v2v4
12、v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+vS,4-v1,1-v2,1v3,1找出增广链按点的第一个标号找到一条按点的第一个标号找到一条增广链（由后向前）增广链（由后向前）v1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+vS,4-v1,1-v2,1v3,1找出增广链v1v2v4v3vt(3,3)(4,3)(5,1)(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsvs,+vS,4-v1,1-v2,1v3,1(二)调整过程011:011:21
13、1:,211:.1,),(),(,),(),(322131231231fufufufufuvvvvuvvvvutsts上调整在按显然显然v1v2v4v3vt(3,3)(4,3)(5,2)(2,2)(1,0)(1,0)(3,0)(5,3)(2,2)vsvs,+vS,4-v1,1-v2,1v3,1(二)调整过程v1v2v4v3vt(3,3)(4,3)(5,2)(2,2)(1,0)(1,0)(3,0)(5,3)(2,2)vsvs,+新一轮标号vS,3,3,.,1sssvvvv标以给标以给号对新的可行流再进行标v1v2v4v3vt(3,3)(4,3)(5,2)(2,2)(1,0)(1,0)(3,0)(
14、5,3)(2,2)vsvs,+vS,3.,0,),(),(2112131331算法结束进行下去标号过程无法均不符合条件上弧上考虑弧fvvcfvvv1v2v4v3vt(3,3)(4,3)(5,2)(2,2)(1,0)(1,0)(3,0)(5,3)(2,2)vsvs,+(二)调整过程vS,35)(.4321ttssfffffv这时的可行流为最大流v1v2v4v3vt(3,3)(4,3)(5,2)(2,2)(1,0)(1,0)(3,0)(5,3)(2,2)vsvs,+vS,3最大流容量为截集为5),(),(),(,312115432111vvvvVVvvvvVvvVssv1v2v4v3vt(3,3)(4,3)(5,2)(2,2)(1,0)(1,0)(3,0)(5,3)(2,2)vsvs,+(二)调整过程vS,3最大流容量为截集为5),(),(),(,312115432111vvvvVVvvvvVvvVss
