第11章图与网络分析(最大流问题)课件.ppt
网络最大流问题,下图看做输油管道网，vs为起点，vt为终点，v1,v2,v3,v4,v5为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大？,网络最大流问题v1v2v4v3v5vtvsff6243743,网络最大流问题,管道网络中每一弧的最大通过能力即容量是有限的，实际流量也并一定等于容量，此类问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为网络最大流问题。,网络最大流问题管道网络中每一弧的最大通过能力即容量是有限的，,例 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,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。,网络最大流问题基本概念：,可行流,可行流满足:容量限制条件：,平衡条件：中间点：发点净流出量收点净流入量v(f).v(f)称为可行流的流量,可行流可行流满足:平衡条件：,注:(容量，流量),v1v2v4v3v5vtvsff(6,3)(2,1)(4,使流量v(f)达到最大的可行流 fij,最大流,最大流问题：,使流量v(f)达到最大的可行流 fij 最大,增广链（可增值链）,几个概念：,1,2,增广链（可增值链）v2v1(5，5)v2v1(5，3)v,3,3,增广链：设 f 是一可行流，时从始点到终点的一条链，若满足下列条件，称其为一条增广链,增广链：设 f 是一可行流，时从始点到终点的一条链，若满,v1v2v4v3v5vtvsff(6,3)(2,1)(4,v1v2v4v3v5vtvsff(6,3)(2,0)(4,截割集与割集容量（截量）,定义：,定义：,截割集与割集容量（截量）定义：定义：,v1v2v4v3v5vtvsff(6,3)(2,0)(4,v1v2v4v3v5vtvsff(6,3)(2,0)(4,v1v2v4v3v5vtvsff(6,3)(2,0)(4,v1v2v4v3v5vtvsff(2,0)(4,2)(3,v1v2v4v3v5vtvsff(6,3)(2,0)(4,v1,v2,v4,v3,v5,vt,vs,f,f,(6,3),(2,0),(4,2),(3,2),(7,3),(4,4),(7,1),(8,2),(8,5),v1v2v4v3v5vtvsff(6,3)(2,0)(4,vs其它各点(vs,v1)15vs,基本定理：,定理 1：（最大流最小割定理）最大流量最小截集容量,定理 2：,基本定理：定理 1：（最大流最小割定理）定理 2：,寻求网络最大流的方法：,寻求网络最大流的方法：可行流 f有无关于可行流调整可行流无,寻求最大流的方法Ford标号法,Ford 标号法,标号过程,调整过程,寻求最大流的方法Ford标号法Ford 标号法标号过程,(I)标号过程,(I)标号过程,(II)调整过程:沿增广链调整流量.,结局：vt 被标上号，反向追踪 vs，找出增广链,(II)调整过程:沿增广链调整流量.结局：vt,结局：vt 未被标上号，标号过程进行不下去，则算法结束，当前的可行流就是最大流,同时获得最小截集，已标号点集，未标号点集弧集合即为 最小截集,结局：vt 未被标上号，标号过程进行不下去，则算法结,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),vs,+,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),vs,+,vS,4,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),vs,+,vS,4,-v1,1,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),vs,+,vS,4,-v1,1,-v2,1,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),vs,+,vS,4,(-v1,1),-v2,1,v3,1,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),vs,+,vS,4,-v1,1,-v2,1,v3,1,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),vs,+,vS,4,-v1,1,-v2,1,v3,1,找出增广链,按点的第一个标号找到一条增广链（由后向前）,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,1),(2,2),(1,1),(1,1),(3,0),(5,3),(2,1),vs,vs,+,vS,4,-v1,1,-v2,1,v3,1,找出增广链,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,1),(2,2),(1,1),(1,1),(3,0),(5,3),(2,1),vs,vs,+,vS,4,-v1,1,-v2,1,v3,1,(二)调整过程,v1v2v4v3vt(3,3)(4,3)(5,1)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,2),(2,2),(1,0),(1,0),(3,0),(5,3),(2,2),vs,vs,+,vS,4,-v1,1,-v2,1,v3,1,(二)调整过程,v1v2v4v3vt(3,3)(4,3)(5,2)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,2),(2,2),(1,0),(1,0),(3,0),(5,3),(2,2),vs,vs,+,新一轮标号,vS,3,v1v2v4v3vt(3,3)(4,3)(5,2)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,2),(2,2),(1,0),(1,0),(3,0),(5,3),(2,2),vs,vs,+,vS,3,v1v2v4v3vt(3,3)(4,3)(5,2)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,2),(2,2),(1,0),(1,0),(3,0),(5,3),(2,2),vs,vs,+,(二)调整过程,vS,3,v1v2v4v3vt(3,3)(4,3)(5,2)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,2),(2,2),(1,0),(1,0),(3,0),(5,3),(2,2),vs,vs,+,vS,3,v1v2v4v3vt(3,3)(4,3)(5,2)(2,2),v1,v2,v4,v3,vt,(3,3),(4,3),(5,2),(2,2),(1,0),(1,0),(3,0),(5,3),(2,2),vs,vs,+,(二)调整过程,vS,3,v1v2v4v3vt(3,3)(4,3)(5,2)(2,2),
