第六章图与网络分析2ppt课件

1、F1.图的基本概念图的基本概念F2.树树F3.最短路最短路F4.最大流问题最大流问题F5.最小费用最大流最小费用最大流F6.中国邮递员问题中国邮递员问题运筹学F问题提出问题提出F运用：生产组织，邮递员问题，通讯网运用：生产组织，邮递员问题，通讯网络等。络等。F哥尼斯堡七桥问题哥尼斯堡七桥问题运筹学ABCDF哥尼斯堡七桥问题哥尼斯堡七桥问题F在图中找一条经过每边一次且仅一次的在图中找一条经过每边一次且仅一次的路路欧拉回路。欧拉回路。ADBC由点和边组成运筹学F“环球旅行环球旅行问题问题F在图中找一条经过每个点一次且仅一次在图中找一条经过每个点一次且仅一次的路的路哈密尔顿回路。哈密尔顿回路。F“中

2、国邮路问题中国邮路问题”F在图中找一条经过每边的最短路在图中找一条经过每边的最短路类类似带权的欧拉回路。似带权的欧拉回路。F“货郎担问题货郎担问题”F在图中找一条经过每个点一次且仅一次的最在图中找一条经过每个点一次且仅一次的最短路短路带权的哈密尔顿回路。带权的哈密尔顿回路。运筹学 例例 1: 铁路交通图铁路交通图 例例 2: 球队比赛图球队比赛图点点: 表示研究对象表示研究对象.连线：表示两个对象之间的某种特定关系连线：表示两个对象之间的某种特定关系。关系的对称性：两对象之间的关系可互换关系的对称性：两对象之间的关系可互换。运筹学F边：不带箭头的联线，表示对称关系。边：不带箭头的联线，表示对称

3、关系。F弧：带箭头的联线，表示不对称关系。弧：带箭头的联线，表示不对称关系。F无向图：简称图，有点和边组成。无向图：简称图，有点和边组成。F 表示为：表示为： G=（V，E）F V-点集合点集合 E-边集合边集合F例：右图例：右图V=v1，v2，v3，v4 E=e1，e2，,e7e1=v1,v2e2=v1,v2, ,e7=v4,v41v2v3v4v1e2e3e4e5e6e7e运筹学F 有向图：由点和弧组成。表示为：有向图：由点和弧组成。表示为：F D=（V，A）F V-点集合点集合 A-弧集合弧集合F点数点数: p(G) 或或 p(D)F边数边数: q(G)F弧数弧数:q(D)v1v2v3v4

4、v5例：右图V=v1，v2,v5A=a1，a2,a7a1=v1,v5,a2=v5,v4,a7=v1,v4运筹学F端点端点: e=u,vE, : e=u,vE, 则则u,vu,v是是e e的端点的端点, , 称称u,vu,v相邻相邻. .F关联边关联边: e: e是点是点u,vu,v的关联边的关联边. .F环环: : 若若u=v, eu=v, e是环是环. .F多重边多重边: : 两点之间多于一条边两点之间多于一条边. .F简单图简单图: : 无环无环, ,无多重边的图无多重边的图. .F多重图多重图: : 无环无环, ,允许有多重边的图允许有多重边的图. .运筹学1v2v3v4v1e2e3e4

5、e5e6e5vF次或度）次或度）: : 以点以点v v为端点的边的个数称为端点的边的个数称为为v v的次的次. . 表示为表示为: d(v): d(v)F悬挂点悬挂点: : 次为次为1 1的点的点. .F悬挂边悬挂边: : 悬挂点的关联边悬挂点的关联边. .F孤立点孤立点: : 次为次为0 0的点的点. .F奇点奇点: : 次为奇数的点次为奇数的点. .F偶点偶点: : 次为偶数的点次为偶数的点. .孤立点悬挂边12( )3, ()3d vd v运筹学F定理1: 图G=(V,E)中,所有点的次之和是边数的两倍, 即:F定理2: 任意一图中, 奇点的个数为偶数.F 证明:设 V1-奇点的集合,F

6、 V2-偶点的集合qvdVv2)(qvdvdvdVvVvVv2)()()(21偶数偶数偶数运筹学F链：点边交错系列，链：点边交错系列， 记为：记为：F圈：圈： 的链。的链。 F初等链：点初等链：点 均不相同。均不相同。F初等圈：点初等圈：点 均不相同。均不相同。F简单链：链中边均不相同。简单链：链中边均不相同。F简单圈：圈中边均不相同。简单圈：圈中边均不相同。F例：右图例：右图 ),.,(1211kkkiiiiiivevvevkiivv1kiiivvv,.,21121,.,kiiivvv1v2v3v4v1e2e3e4e5e6e7e无重复点,无重复边有重复点,无重复边运筹学F连通图：任意两点之间

7、至少有一条链。连通图：任意两点之间至少有一条链。F不连通图：不连通图：F连通分图：对不连通图，每一连通的部连通分图：对不连通图，每一连通的部分称为一个连通分图。分称为一个连通分图。F支撑子图：对支撑子图：对G=（V，E），若），若G=(V,E), 使使V=V, E E, 则则G是是G的的一个支撑子图生成子图）一个支撑子图生成子图）.FG-v: 图图G去掉点去掉点v及及v的关联边的图的关联边的图.运筹学F基础图基础图: 对对D=(V, A), 去掉图上的箭头去掉图上的箭头.F始点和终点始点和终点: 对弧对弧a=(u,v), u为为a的始点的始点, v为为a的终点的终点.F链链: 点弧交错序列点弧

8、交错序列, 若在其基础图中对应若在其基础图中对应一条链一条链, 则称为则称为 D的一条链的一条链.F圈圈, 初等链初等链,初等圈初等圈: 类似定义类似定义.方向可以不同运筹学F道路道路:假设假设 是是D中的一条链，且中的一条链，且 ，t=1,2,k-1,称之为从称之为从 到到 的一条道路。的一条道路。F回路回路: 的路的路.F初等路初等路: 道路中点不相同道路中点不相同.F初等回路初等回路: 回路中点不相同回路中点不相同.F简单有向图简单有向图: 无自环无自环, 无多重弧无多重弧.F多重有向图多重有向图: 有多重弧有多重弧.),.,1112211kkkiiiiiiivavavav（kiivv1

9、),(1tttiiivva1ivkiv方向相同运筹学F设图设图G=（V，E），其中），其中Fn阶方阵阶方阵 称为的邻接矩阵，其中称为的邻接矩阵，其中12,nVv vv()ijAa10ijaij或权值，若(v ,v ) E或 ，否则运筹学F欧拉图：具有欧拉回路的图F定理3 一个连通图 为欧拉图的充要条件是 的每一个结点的度均为偶数。F例如，哥尼斯堡七桥不存在一条欧拉回路，所以哥尼斯堡七桥问题的回答是否定的。GG运筹学F哈密顿回路：经过图的每个结点一次且哈密顿回路：经过图的每个结点一次且仅一次的回路。仅一次的回路。F类似于确定哈密顿回路的问题是流动售类似于确定哈密顿回路的问题是流动售货员的问题，流

10、动售货员要从公司出发货员的问题，流动售货员要从公司出发走销附近的所有城镇，然后返回所在地走销附近的所有城镇，然后返回所在地，那么如何安排他的路线，使得旅行的，那么如何安排他的路线，使得旅行的总距离最小。总距离最小。运筹学F2.1 树及其性质树及其性质F2.2 图的支撑树生成树）图的支撑树生成树）F2.3最小支撑树问题最小支撑树问题F2.4 根树及其应用根树及其应用运筹学例例: 电话线架设、比赛程序、组织结构等。电话线架设、比赛程序、组织结构等。 树树:连通的无圈的无向图称为树。连通的无圈的无向图称为树。运筹学 图图G=G=（V V，E E），），p p个点、个点、q q条边下列说法是等价的条边

11、下列说法是等价的（1 1G G是一个树是一个树（2 2G G连通，且恰有连通，且恰有p-1p-1条边。条边。（3 3G G无圈，且恰有无圈，且恰有p-1p-1条边。条边。（4 4G G连通，但每舍去一边就不连通。连通，但每舍去一边就不连通。（5 5G G无圈，但每增加一边即得唯一一个圈。无圈，但每增加一边即得唯一一个圈。 （6 6G G中任意两点之间恰有一条链中任意两点之间恰有一条链( (简单链简单链) )。运筹学F定义定义: :设图设图T=(VT=(V，E) E) 是图是图G=(V,E)G=(V,E)的支的支撑子图撑子图, ,如果如果T T是一个树是一个树, , 则称则称T T是是G G的一

12、的一个支撑树。个支撑树。F定理定理5 5：图：图G=G=（V V，E E有支撑树的充分必有支撑树的充分必要条件是要条件是G G是连通的。是连通的。运筹学F求支撑树的破圈法求支撑树的破圈法运筹学F求支撑树的避圈法求支撑树的避圈法深探法广探法运筹学F赋权图赋权图( (网络）网络）: : 给图给图G=(V,E), G=(V,E), 对对G G中的中的每一条边每一条边vi,vj, vi,vj, 相应地有一个数相应地有一个数wij, wij, 则称这样的图为赋权图则称这样的图为赋权图, wij , wij 称为边称为边vi,vjvi,vj上的权上的权. .F支撑树的权支撑树的权: :若若T=(V,E)

13、T=(V,E) 是是G G的一个支撑的一个支撑树树, E, E中的所有边的权之和称为支撑树中的所有边的权之和称为支撑树的权的权, , 记为记为w(T):w(T):TvvijjiwTw,)(运筹学F定义定义: : 最小支撑树最小支撑树( (最小树最小树)T)T* *: :F求最小树的求最小树的 避圈法避圈法: : 例例: : 图图8-278-27F求最小树的求最小树的 破圈法破圈法: : 例例: : 图图8-28 8-28 )()(min*TwTwT运筹学有向树中根树有向树中根树在计算机科学、决策论的应用在计算机科学、决策论的应用F有向树：有向树：F根树：有向树根树：有向树T，恰有一个结，恰有一

14、个结点入次为点入次为0，其余各点入次为，其余各点入次为1，则称，则称T为根树。为根树。FM叉树：叉树：F二叉树：结点的出度都小于二叉树：结点的出度都小于等于等于2。根叶分点枝第一层第三层第二层三叉树运筹学F带权的二叉树带权的二叉树T：有：有s个叶子，权分别为个叶子，权分别为pi，F根到各叶子的距离层次为根到各叶子的距离层次为F二叉树的总权数二叉树的总权数F最优二叉树（最优二叉树（ Huffman树）：总权数最小的二叉树树）：总权数最小的二叉树F算法步骤：算法步骤：Huffman算法算法F将将s个叶子按权由小到大排列，个叶子按权由小到大排列，F将两个最小的叶子合并为一个分枝点，其权为两者将两个最

15、小的叶子合并为一个分枝点，其权为两者之和，将新的分枝点作为一个叶子，转上一步，直之和，将新的分枝点作为一个叶子，转上一步，直到结束。到结束。), 2 , 1( ,silisiiilpTm1)(运筹学F例例1、s=6，其权分别为，其权分别为4，3，2，2，1，求最优二叉树。求最优二叉树。123243365运筹学F例例1、s=6，其权分别为，其权分别为4，3，2，2，1，求最优二叉树。求最优二叉树。123243396515123243396515运筹学F例例2、最优检索问题。、最优检索问题。F 使用计算机进行图书分使用计算机进行图书分 类。现有五类类。现有五类图书共图书共100万册，其中有万册，其

16、中有A类类50万册，有万册，有B类类20万册，万册，C类类5万册，万册，D类类10万册，万册，E类类15万册，问如何安排分检过程，可使总万册，问如何安排分检过程，可使总的运算比较次数最小？的运算比较次数最小？运筹学F例例3：P235、例、例110.050.450.050.080.120.25一等品一等品五等品五等品四等品四等品三等品三等品二等品二等品等外品等外品0.100.300.180.551.0测试顺序运筹学3.1 引例引例单行线交通网：单行线交通网：v1到到v8使总费用最小的旅行使总费用最小的旅行路线。路线。最短路问题的一般描述：最短路问题的一般描述： 对对D=（V，A），）， a=（v

17、i，vj），），wa）=wij，P是是vs到到vt的路，定义路的路，定义路P的权的权是是P中所有弧的权的和，记为中所有弧的权的和，记为wP）运筹学F路路P0的权称为从的权称为从vs到到vt的距离，记为：的距离，记为：Fd（ vs，vt ）F3.2最短路算法最短路算法FDijkstra算法算法 ：有向图：有向图 ，wij0F一般结论一般结论)()(min0PwPwP 的最短路到的最短路到isjsvvisvvjisvvvvv,.,.,.,则最短路问题为：则最短路问题为：运筹学Dijkstra算法基本思想P标号：已确定出最短路的节点的距离。T标号：为确定出最短路的节点，但表示其距离的上限。Si：P标

18、号节点的集合。(v)：最短路中前一个节点的编号。初始值： () () ()0sssTvvvvsvvv 运筹学例:011122330 1 ()0 ()0 () ()1 () ()1 . . iSvkP vvT vvT vv 99 () ()1T vv 运筹学 12112222131133331411444( ,):()066() ()6 ()1 ( ,):()033() ()3 ()1 ( ,):()011() ()v vP vwT vT vvv vP vwT vT vvv vP vwT vT v423456789411441 ()1min (),(),(),(),(), (),(),()()

19、1 , ()1 4vT vT vT vT vT vT vT vT vT viSv vP vk运筹学 3 3)( , 2 )()(),( ),(),(),(),(),( min4)( 11)( )(11101)(: ),(334123987653266646464kvPvvvSivTvTvTvTvTvTvTvTvvTvTwvPvv运筹学 2 5)( , 3 )()(),(),( ),(),(),( min3)( 5)( 6)(523)(: ),(223413298765222232323kvPvvvvSivTvTvTvTvTvTvTvvTvTwvPvv运筹学 252255555678954143

20、255(,):()5 16() ()6 ()2min (), (), (), (), ()() 4 , ()6 5v vP vwT vT vvT vT vT vT vT vT viSv v v v vP vk 运筹学 7 9)( , 5 )()(),(),( ),(min5)( 12)( )(1266)(: ),( 5)( 9)( )(936)(: ),( 5)( 10)( )(1046)(: ),(77523415798768845858577757575610656565kvPvvvvvvSivTvTvTvTvTvvTvTwvPvvvvTvTwvPvvvvTvTwvPvv运筹学 78778

21、88856896614325766( ,): ( )9 413( )12 ( ) =12 ( )min ( ), ( ), ( )( ) 6 , , , ( )10 6v vP vwT vT vvvT vT vT vT viSv v v v v v vP vk 运筹学 6689871432576888899,min (),()() 7 , ()12 8,min() () . vST vT vT viSvvvvvvvvP vkvST vT v 无 指 向 不 属 于的 点 转 向 无 指 向 不 属 于的 点 转 向 算 法 终 止运筹学总结: 算法步骤:MvvTvvPvvPvvPvvPvvPv

22、vPvvPvvP)( )(5)( 12)(5)( 9)(5)( 10)(2)( 6)(1)( 1)(1)( 3)(3)( 5)(0)( 0)(998877665544332211运筹学FDijkstra算法算法 ：无向图求最短链，：无向图求最短链，wij0F存在负权时求最短路问题存在负权时求最短路问题 ),(: ),(:jijjkjijjkvSvEvvvSvAvv的点且考察修改为的点且考察算法修改运筹学4.1基本概念和基本定理基本概念和基本定理网络与流网络与流定义定义: 对有向图对有向图D=(V,A):vs 源源 vt 汇汇 其他其他 - 中间点中间点c(vi,vj) - 弧弧(vi,vj)的

23、容量的容量, 简写为简写为cijD=(V,A,C) - 网络网络 fij - 弧弧(vi,vj)上的流量上的流量运筹学运筹学F可行流与最大流可行流与最大流F可行流满足可行流满足:称为可行流的流量有对有对有对平衡条件（对容量限制条件)()( :)( :0:,:)20 ),:) 1),(),(),(),(),(),(fvfvffvfvffvfftsivcfAvvAvvjtAvvtjtAvvjsAvvsjsAvvjiAvvijiijijjitjjtsjjsijji流入量=流出量流出量流入量运筹学最大流问题tifvfftsiffsifvffAvvcffvAvvjtAvvtjAvvjiAvvijAvvj

24、sAvvsjjiijijtjjtijjisjjs )(, 0 )( ),( 0)(max),(),(),(),(),(),(运筹学F增广链增广链: F几个概念几个概念: 对可行流对可行流F例例:图图10-23其全体记为后向弧反弧的方向与链的方向相其全体记为前向弧致弧的方向与链的方向一网络中的一条链非零流弧零流弧非饱和弧饱和弧- ),.,( 0 0 tsijijijijijijvvffcfcfijff 运筹学增广链: 设f是一可行流, 时从始点到终点的一条链, 若满足下列条件,称其为一条增广链.例: 图10-24截集和截量设 把始点在S,终点在T中的所有弧构成的集合, 记为(S,T).非零流弧对

25、后向弧非饱和弧对前向弧ijijijijcfcf0:0:TSVTS,可增加流量的链运筹学F定义定义: 截集截集F定义定义: 截量截量 .),(,),( _11_11_11称为截集则把弧集且和被分为两个非空集合若对网络VVVvVvVVVCAVDts),(),(_11_11_11_11),( :),(,),( VVvvijjicVVcVVcVV即记为简称截量集的容量为截中所有弧的容量之和称把截集运筹学F几点结论几点结论最小截集容量最大流量最大流量最小截集定理的增广链不存在关于是最大流可行流 : ) 3 2),()( ) 1*_11ffVVcfv运筹学F网络中的点分为网络中的点分为:F标号点标号点F标

26、号未检查点标号未检查点F标号已检查点标号已检查点F未标号点未标号点运筹学F1) 标号过程标号过程., .,),(min)( :),(,( 0,),(),(min)( :),(,( ,),()(,), 0( 停止则已得到最大流没有得到标号若进入调整过程已找到一条增广链已标号若其中标号给非零流弧后向弧对其中标号给非饱和弧若前向弧对标号未检查点对一般地标上给ttjiijjijjiijijijijjijijijjiisvvfvlvlvlvvfvvfcvlvlvlvvcfvvvv运筹学F 2) 调整过程调整过程: 沿增广链调整流量沿增广链调整流量.F例例: 图图10-25运筹学F定义定义: 对对D=(V

27、,A,C), 给定一个单位流量给定一个单位流量的费用的费用bij0, 最小费用最大流即最小费用最大流即:求一最求一最大流大流f, 使使F 对增广链对增广链, 若调整流量若调整流量=1, 那么新可行那么新可行流流f的费用比原可行流的费用比原可行流f的费用增加的费用增加:Avvijijjifbfb),()(min运筹学F此为增广链此为增广链的费用的费用.F最小费用最大流的求解最小费用最大流的求解F构造赋权有向图构造赋权有向图w(f), 定义定义:ijijbbfbfb)()(0 0 ijijijjiijijijijijijffbwcfcfbw运筹学在w(f)中找最小费用增广链, 直至没有最小费用增广

28、链为止.若存在最小费用增广链, 调整流量如下: ),( ),( ),( )(min),(minmin)1()1()1()1()1(jikijjikijjikijkijkijkijijvvfvvfvvffffc运筹学初初始始网网络络数数值值VsV1 V2 V3 Vt 运筹学(4,10)(1, 8)(2, 4)(1, 7)(2, 5)(6, 2)(4,10)bij Cij初初始始网网络络数数值值VsV1 V2 V3 Vt 运筹学取初始取初始可行流可行流f (0) =0V1 V2 V3 Vs Vt 运筹学(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行

29、流可行流f (0) =0V1 V2 V3 Vs Vt bij fij运筹学(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行流可行流f (0) =0构造赋构造赋权图权图W(f (0)V1 V2 V3 Vs Vt 0 0 ijijijjiijijijijijijffbwcfcfbw运筹学(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行流可行流f (0) =0构造赋构造赋权图权图W(f (0)V1 V2 V3 Vs Vt 运筹学(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0

30、)取初始取初始可行流可行流f (0) =0构造赋构造赋权图权图W(f (0)( +, 0 )V1 V2 V3 Vs Vt 运筹学(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)在初始在初始赋权图赋权图W(f (0)上求出上求出最短路最短路V1 V2 V3 Vs Vt 运筹学(4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量V1 V2 V3 Vs Vt ),( ),( ),( )(min),(minmin)0()0()0()1()0()0(jiijjiijjiijijijijijvvfvvfvvfff

31、fc运筹学(4,0)(2, 0)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量原流量原流量如图所如图所示示V1 V2 V3 Vs Vt (1, 0)(1, 0)(2, 0)运筹学(4,0)(2, 0)(6, 0)(4,0)求求增增加加的的流流量量V1 V2 V3 Vs Vt 8 - 0 5 - 0 7 - 0最小最小f (0) (1, 0)(1, 0)(2, 0)运筹学(4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量 = 5得到新得到新的流量的流量f (1)=5V1 V2 V3 Vs Vt 运筹学(4,0)(1, 5

32、)(2, 0)(1,5) (2, 5)(6, 0)(4,0)依据新依据新的流量的流量构造又构造又一赋权一赋权图图W(f (1)*只对只对增广链增广链V1 V2 V3 Vs Vt 80 0 ijijijjiijijijijijijffbwcfcfbw运筹学(4,0)(2, 0)(1,5) (2, 5)(6, 0)(4,0)赋赋权权图图W(f (1)的构造的构造*只对只对增广链增广链V1 V2 V3 Vs Vt 8(-1, 5)(1, 5)运筹学(4,0)(2, 0)(1,5)(2, 5)(6, 0)(4,0)赋赋权权图图W(f (1)的构造的构造*只对只对增广链增广链V1 V2 V3 Vs Vt

33、 8 5(-1, 5)(1, 5)0 0 ijijijjiijijijijijijffbwcfcfbw运筹学(4,0)(2, 0)(1,5)(6, 0)(4,0)赋赋权权图图W(f (1)的构造的构造*只对只对增广链增广链V1 V2 V3 Vs Vt 8 5(-2, 5) 7(-1,5)(-1, 5)(1, 5)运筹学(4,0)(2, 0)(1,5)(6, 0)(4,0)构造的构造的赋权赋权图图W(f (1)*只对只对增广链增广链V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-1, 5)(1, 5)运筹学(4,0)(2, 0)(1,5)(6, 0)(4,0)在赋在赋权图权图W(f

34、(1)上求出上求出最短路最短路V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-1, 5)(1, 5)运筹学Vs (4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量V1 V2 V3 Vs Vt 7 - 5 = 2 10 - 0 最小最小运筹学Vs (4,2)(1, 5)(2, 0)(1,7)(2, 5)(6, 0)(4,0) = 2得到新得到新的流量的流量f (2)=7新的流新的流量图如量图如图所示图所示V1 V2 V3 Vs Vt 运筹学依据新依据新的流量的流量构造又构造又一赋权一赋权图图W(f (2)*只对只对增广链

35、增广链V1 (4,0)(1, 5)(2, 0)(1,5)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5)(-1,5)运筹学对最短对最短路上求路上求新的权新的权值值V1 (4,2)(1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5) 100 0 ijijijjiijijijijijijffbwcfcfbw运筹学赋赋权权图图的构造的构造W(f (2)*只对只对增广链增广链V1 (4,2)(1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5)(-4

36、,2)0 0 ijijijjiijijijijijijffbwcfcfbw运筹学赋赋权权图图的构造的构造W(f (2)*只对只对增广链增广链V1 (4,2)(-1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (1, 5)(-2, 5) 7(-4,2)0 0 ijijijjiijijijijijijffbwcfcfbw运筹学赋赋权权图图的构造的构造W(f (2)*只对只对增广链增广链V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)运筹学新新赋赋权权图图W(f (2)

37、*只对只对增广链增广链V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)运筹学在赋在赋权图权图W(f (2)上求出上求出最短路最短路V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)运筹学(4,2)(1, 5)(2, 0)(1,7)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量 = 3V1 V2 V3 Vt 8 - 5 = 3 最小最小 10 - 0 4 - 0运筹学(4,2)(1,

38、8)(2, 3)(1,7)(2, 5)(6, 0)(4,3)在最短在最短路上增路上增加流量加流量 = 3得到新得到新的流量的流量f (3)=10V1 V2 V3 Vt 运筹学依据新依据新的流量的流量构造又构造又一赋权一赋权图图W(f (3)*只对只对增广链增广链V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4,2)(1, 8) 8 10 4运筹学赋赋权权图图W(f (3)的构造的构造*只对只对增广链增广链V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4,2)(-1, 8)(-4,3)(-2, 3)运筹学在赋权在赋权图图W(f (3)上求出上求出最短路最短路V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4