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

1、第第1页页第八章第八章图与网络分析图与网络分析 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第2页页第八章第八章图与网络分析图与网络分析 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第3页页最短路问题最短路问题第第4页页最短路问题提出最短路问题提出在现实生活中，除公路运输网络、电讯网络在现实生活中，除公路运输网络、电讯网络等网络图以外，还有输油管线这样的图。在输油等网络图以外，还有输油管线这样的图。在输油管线图中，为反映油的输送情况，两点间不仅有管线图中，为反映油的输送情况，两点间不仅有连线，线上往

2、往还标有箭头，以表示油的流动方连线，线上往往还标有箭头，以表示油的流动方向。又如，指挥系统图、控制系统图等图中都标向。又如，指挥系统图、控制系统图等图中都标有指向。从这样的一类图中就可以概括为有向图有指向。从这样的一类图中就可以概括为有向图的概念。的概念。第第5页页有向网络与混合图有向网络与混合图 如果在图如果在图D=D=（V V，A A中，给每一弧赋予权值，如中，给每一弧赋予权值，如 将弧将弧aij=(vi,vj)aij=(vi,vj)有权值有权值 wij wij，记为，记为w(aij)=wijw(aij)=wij则赋权有向图则赋权有向图D=D=（V V，A A称为有向网称为有向网络，在不至

3、于混淆时，也简称网络。络，在不至于混淆时，也简称网络。 混合图如果一个图中既有边，也有弧，那么称这混合图如果一个图中既有边，也有弧，那么称这种图为混合图。它往往出现在既有单行线，又有种图为混合图。它往往出现在既有单行线，又有双行线的交通图中。双行线的交通图中。12534372第第6页页最短路问题引例最短路问题引例下图为单行线交通网，每弧旁的数字表示通过这条下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从线所需的费用。现在某人要从v1v1出发，通过这个交出发，通过这个交通网到通网到v8v8去，求使总费用最小的旅行路线。去，求使总费用最小的旅行路线。v2v523464v3v1

4、v4v6121061210v8v9v72363从从v1v1到到v8v8：P1=P1=（v1v1，v2v2，v5v5，v8v8） 费用费用 6+1+6=13 6+1+6=13P2=P2=（v1v1，v3v3，v4v4， v6 v6， v7 v7， v8 v8） 费用费用 3+2+10+2+4=21 3+2+10+2+4=21P3= P3= 从从v1v1到到v8v8的旅行路线的旅行路线 从从v1v1到到v8v8的路。的路。旅行路线总费用旅行路线总费用 路上所有弧权之和。路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。最短路问题中，不考虑有向环、并行弧。v2v523464v3v1v4v6121

5、061210v8v9v72363第第8页页几个概念几个概念路：设路：设p是是D中一个首尾相连的弧的集合，如果中一个首尾相连的弧的集合，如果vs是是它的第一条弧的始点，它的第一条弧的始点，vt是它的最后一条弧的是它的最后一条弧的终点，则称它是以点终点，则称它是以点vi为始点，以点为始点，以点vt为终点的为终点的一条路。一条路。路长：路路长：路p中所有弧的权值的和称为路中所有弧的权值的和称为路p的长，记为的长，记为设图设图D=D=（V V，A A是一有向网络是一有向网络paijijawpw)()( v2v523464v3v1V4 v6121061210v8v9v72363第第9页页设设P P是以点

6、是以点vsvs为始点，以点为始点，以点vtvt为终点的所有路的集合，为终点的所有路的集合， 假如假如 , ,且且 ，则称，则称p0p0是以点是以点vsvs 为始点，以点为始点，以点vtvt为终点的最短路。而称其路长为为终点的最短路。而称其路长为点点 vs vs到点到点vtvt的距离，记为的距离，记为 。几个概念几个概念Pp 0)()(0pwMinpwPp)(),(0pwvvdts注意：在有向网络中注意：在有向网络中, ,一般一般),(),(sttsvvdvvd最短路及一点到另一点的距离最短路及一点到另一点的距离第第10页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近

7、算法逐步逼近算法 路矩阵算法路矩阵算法第第11页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第12页页求解最短路问题的求解最短路问题的Dijkstra算法算法条件：当所有条件：当所有wij0时，用来求给定点时，用来求给定点vs到任一到任一个点个点vj最短路的公认的最好方法。最短路的公认的最好方法。事实：如果事实：如果P是是D中从中从vs到到vj的最短路，的最短路，vi是是P中的一中的一基解基解个点，那么，从个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到vi的的最基解最基解短路。短路。 Dijkstra算法是Dijk

8、stra在1959年提出的，可用于求解指定两点间的最短路问题，或从指定点到其余各点的最短路问题。由于其以标号为主要特征，又称为标号法。v1v2v3v4v5最短路的子路是最短路最短路的子路是最短路第第13页页Dijkstra算法算法0ijw 第第14页页 1. 1.标号标号 P P固定标号或永久性标号）固定标号或永久性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权ui ui 。 2. 2.标号标号 T T临时性标号）临时性标号）从始点到该标号点的最短路权上界从始点到该标号点的最短路权上界ui ui 。选用符号的意义选用符号的意义P( i, ui)3.前点标号前点标号i表示点表示点vs

9、到到vj的最短路上的最短路上vj的前一点。的前一点。T( i, ui)Dijkstra算法步骤：算法步骤： ijijjwvPvTvT)(),(min)( ,)ijv vE0)(1 vP0jv )()(min0jsvjvTvTj 1,6图上标号法图上标号法v5v223464v3v1v4121061210v8v9v72363v60,01,1,1,31,1,1,1,11,1永久标号永久标号永久标号永久标号临时标号临时标号1,6图上标号法图上标号法v5v223464v3v1v4121061210v8v9v72363v60,01,1,11,1,31,1,1,0,01,14,111,3永久标号永久标号临时

10、标号临时标号v5v223464v3v1v4121061210v8v9v72363v60,01,1,1,11,1,1,1,3图上标号法图上标号法4,111,31,63,53,5永久标号永久标号临时标号临时标号v5v223464v3v1v4121061210v8v9v72363v60,01,4,111,11,1,1,1,3图上标号法图上标号法3,52,62,6永久标号永久标号临时标号临时标号v5v223464v3v1v4121061210v8v9v72363v60,01,4,111,11,1,1,35,125,95,9图上标号法图上标号法3,52,6永久标号永久标号临时标号临时标号v5v22346

11、4v3v1v4121061210v8v9v72363v60,04,111,11,5,121,35,95,123,52,6图上标号法图上标号法永久标号永久标号临时标号临时标号4,11v5v223464v3v1v4121061210v8v9v72363v64,110,01,11,1,35,123,52,6图上标号法图上标号法5,9永久标号永久标号临时标号临时标号标号结束标号结束反向追踪反向追踪第第23页页例例 求如下交通网络中各对点间最短路路长。求如下交通网络中各对点间最短路路长。DijkstraDijkstra算法标号法算例算法标号法算例31025v4v1v2v5v312262448混合图混合图

12、第第24页页 无向网络无向网络: :负权弧时。负权弧时。wijvivjwijwijvjvi无向网络中，最短路无向网络中，最短路最短链。最短链。多个点对之间最短路？多个点对之间最短路？v1v2v312-3Dijkstra算法失效算法失效Dijkstra算法注意的问题算法注意的问题逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法第第25页页5727461263202657710v3v1v2v4v5v6v7练习：求如下无向网络中练习：求如下无向网络中v1v1到到v7v7的最短路的最短路Dijkstra算法求最短链算法求最短链第第26页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步

13、逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第27页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第28页页逐次逼近算法逐次逼近算法 计算指定点计算指定点v1v1到其余各点的最短路时，到其余各点的最短路时，某些问题会出现有负权弧的图某些问题会出现有负权弧的图, ,如：如： 此时此时DijkstraDijkstra算法标号法有可能失效。算法标号法有可能失效。逐次逼近法对于这类问题的解决很有帮助。逐次逼近法对于这类问题的解决很有帮助。 v1v2v312-3第第29页页逐次逼近算法思想逐次逼近算法思想该公式表明，该公式表明，P(1)

14、1j中的第中的第j个分量等于个分量等于P(0)1j的分量的分量与基与基本表中第本表中第j列相应元素路长的最小值，它相当于在点列相应元素路长的最小值，它相当于在点v1与与vj之间插入一个转接点之间插入一个转接点v1,v2,vn中的任一个，含点中的任一个，含点v1与与vj后所有可能路中的最短路的路长；每迭代一次，就相后所有可能路中的最短路的路长；每迭代一次，就相当于增加一个转接点，而当于增加一个转接点，而P(k)1j中的每一个分量则随着中的每一个分量则随着k的的增增加呈不增的趋势，直到出现稳定。加呈不增的趋势，直到出现稳定。)1(11)(1ijkinikjwPMinP第第30页页用于计算指定点用于

15、计算指定点v1v1到其余各点的最短路到其余各点的最短路)1(11)(1ijkinikjwPMinPj=1,2,n. k=1,2,tn.2.2.计算计算逐次逼近算法基本步骤逐次逼近算法基本步骤jjwP1)0(1 j=1,2,n.1.1.令令(k)(1)11kjjPP其元素既是其元素既是v1v1到到vjvj的最短路长。的最短路长。3.3.当出现当出现时，时，例例 计算从点计算从点v1v1到所有其它顶点的最短路到所有其它顶点的最短路解：初始条件为解：初始条件为 3, 5, 2, 0114113112111PPPP 以后按照公式以后按照公式 进行迭代。进行迭代。 直到得到直到得到 ，迭代停止。，迭代停

16、止。v1v2v3v4v6v5v8v72-35467-24-3342-1)1(11)(1ijkinikjwPMinP) 1(1)(1tjtjPPv1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 11jP 21jP 31jP 41jP 51jP 61jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-2042000253021230312561361102123031256123661368150212303123653123661236613687141236810021230312365312366123687912

17、3681002123031236612368791236810123653利用下利用下标追踪标追踪路径路径第第33页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第34页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第35页页 某些问题需要求网络上任意两点间的最短路。某些问题需要求网络上任意两点间的最短路。当然，它也可以用标号算法依次改变始点的办法当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。来计算，但是比较麻烦。 这里介绍这里介绍Floyd

18、Floyd在在19621962年提出的路矩阵法，年提出的路矩阵法，它可直接求出网络中任意两点间的最短路。它可直接求出网络中任意两点间的最短路。FloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想第第36页页 网络D=（V，A，W），令U=(dij)nn， 表示D中vi到vj的最短路的长度。iju 考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉，得只剩vi，vj的一个子网络D0，记ij(0)ij ,A ijwv vd当否wij为弧（为弧（ vi，vj的权。的权。 在D0中加入v1及D中与vi，vj，v1相关联的弧，得D1，D1中vi到vj的最短路记为 ,则一定有(1)i

19、jd(1)(0)(0)(0)i11j min, ijijddddvivjv1wijFloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想第第37页页 再在D1中加入v2及D中与vi，vj，v1， v2相关联的弧，得D2，D2中vi到vj的最短路长记为 ，则有(2)ijd(2)(1)(1)(1)iji22 j min, ijdddd随着转接点的逐步增加随着转接点的逐步增加, ,我们会发现我们会发现 二指定点间路的条数也会随之增加，但是其最短路二指定点间路的条数也会随之增加，但是其最短路及路长可以确定；及路长可以确定； 当当V V中所有的点都可以作为转接点时，指定点中所有的点都可以作为转

20、接点时，指定点vivi到到vjvj间所有路中的最短路自然是图中指定点间所有路中的最短路自然是图中指定点vivi到到vjvj间的最短路。间的最短路。FloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想第第38页页FloydFloyd算法算法( (路矩阵法路矩阵法) )步骤步骤设有有向网络设有有向网络D=D=（V V，A A），其权矩阵为），其权矩阵为A=(aij)nnA=(aij)nn，AvvjiAvvwajijiijij),( , 0),( ,如下构造路矩阵序列：如下构造路矩阵序列：则则n n阶路矩阵阶路矩阵D(n)D(n)中的元素中的元素d(n)ijd(n)ij就是就是vivi到

21、到vjvj的最短路的路长。的最短路的路长。令权矩阵令权矩阵A为初始路矩阵为初始路矩阵D0），即令），即令D0）=A2. 2. 依次计算依次计算K K阶路矩阵阶路矩阵D DK K）= =（d(k)ijd(k)ijnn, k=1,2,nnn, k=1,2,n，,) 1() 1() 1()(kkjkikkijkijdddMind这里这里第第39页页路矩阵序列的含义路矩阵序列的含义 K K阶路矩阵阶路矩阵D DK K） 其中的元素表示相应两点间可能以点其中的元素表示相应两点间可能以点v1v1、v2v2、vkvk为为 转接点的所有路中路长最短的路的路长。转接点的所有路中路长最短的路的路长。D0）其中的任

22、一元素表示相应两点间无转接点时最短路路长。其中的任一元素表示相应两点间无转接点时最短路路长。一阶路矩阵一阶路矩阵D D1 1） 其中的元素表示相应两点间可能以点其中的元素表示相应两点间可能以点v1v1为转接点的所为转接点的所有路中路长最短的路的路长；有路中路长最短的路的路长；为使计算程序化，转接点按顶点下标的顺序依次加入为使计算程序化，转接点按顶点下标的顺序依次加入n n阶路矩阵阶路矩阵D(n)D(n) 其中的元素其中的元素d(n)ijd(n)ij就是就是vivi到到vjvj的可能以点的可能以点v1v1、v2v2、vnvn为转接点的所有路中路长最短的路的路长。既是为转接点的所有路中路长最短的路

23、的路长。既是vivi到到vjvj的最短路的路长。的最短路的路长。第第40页页例例 求如下交通网络中各对点间最短路路长。求如下交通网络中各对点间最短路路长。051250 102 A2302826042440该图的权矩阵为：该图的权矩阵为：FloydFloyd算法算法( (路矩阵法路矩阵法) )算例算例31025v4v1v2v5v312262448第第41页页例例 求如下交通网络中各对点间最短路路长。求如下交通网络中各对点间最短路路长。FloydFloyd算法算法( (路矩阵法路矩阵法) )算例算例 0051250 102 D =A230282604244031025v4v1v2v5v312262

24、448 0051250 102 D =A2302826042440(1)(0)(0)(0)i11j min, ijijdddd利用公式利用公式发现第一行，第一列元素不变发现第一行，第一列元素不变 105125 D220213621472302841274133042440031025v4v1v2v5v312262448 105125 D2202136214723028412741330424400(2)(1)(1)(1)i22j min, ijijdddd利用公式利用公式发现第二行，第二列元素不变发现第二行，第二列元素不变 255 D021362341272214721470232554133

25、44400121257202521731025v4v1v2v5v312262448 255 D0213621472302325541274133042440012214712572025217(3)(2)(2)(2)i33j min, ijijdddd利用公式利用公式发现第三行，第三列元素不变发现第三行，第三列元素不变0 3 D21363232554133412001324213256502147224132604531624031025v4v1v2v5v31226244802147204127042400221471257 3 D2136323255413341200132421325650

26、21472241326045316240 4 D0213623032552011325/1456202413264133440221472531/5416413245(4)(3)(3)(3)i44j min, ijijdddd利用公式利用公式发现第四行，第四列元素不变发现第四行，第四列元素不变31025v4v1v2v5v31226244831025v4v1v2v5v312262448 4 D021362147230325502401202413264133440221472531/54164132451325/1456 5 D0213621472303255024012024132641334

27、40221472531/54164132451325/1456D(5)中的元素给出相应两点间中的元素给出相应两点间的最短路，其下标给出最短路的最短路，其下标给出最短路个顶点下标个顶点下标,比如：比如：第第47页页练习练习 已知有已知有7 7个村子，相互间道路的距离如下图个村子，相互间道路的距离如下图示。拟合建一所小学，已知示。拟合建一所小学，已知A A处有小学生处有小学生3030人，人，B B处处4040人，人，C C处处2525人，人，D D处处2020人，人，E E处处5050人，人，F F处处6060人，人， G G处处6060人人, ,问小学应建在哪一个村子，使学生上学最问小学应建在哪

28、一个村子，使学生上学最方便原则所有人走的总路程最短；尽可能公方便原则所有人走的总路程最短；尽可能公平。）。平。）。FloydFloyd算法算法( (路矩阵法路矩阵法) )算例算例AGFECB522747163D26第第48页页第八章第八章图与网络分析图与网络分析 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第49页页第八章第八章图与网络分析图与网络分析 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第50页页网络最大流问题网络最大流问题50年代福特年代福特Ford）、富克逊）、富克逊Fulkerson

29、建立建立的的“网络流理论网络流理论”，是网络应用的重要组成部分。，是网络应用的重要组成部分。第第51页页问题的提出问题的提出 在一个输油管网中，有生产石油的油井、储存石油的油在一个输油管网中，有生产石油的油井、储存石油的油库、转运石油的中间泵站，同时，还有各种口径不同的输油库、转运石油的中间泵站，同时，还有各种口径不同的输油管。当一个输油管网给定后，单位时间内最多可把多少石油管。当一个输油管网给定后，单位时间内最多可把多少石油从油井输送到油库？具体方案如何？从油井输送到油库？具体方案如何？ 分析：就输油管网络问题，可用顶点表示油井、油分析：就输油管网络问题，可用顶点表示油井、油库和中间泵站，用

30、有向边表示输油管，用有向边上库和中间泵站，用有向边表示输油管，用有向边上的权表示单位时间沿相应的输油管可以输送石油的的权表示单位时间沿相应的输油管可以输送石油的最大数量容量）。最大数量容量）。 第第52页页tvsv1234,v v v vtvsv问题的提出问题的提出管道网络中每边的最大通过能力即容量是有限的，实际流管道网络中每边的最大通过能力即容量是有限的，实际流量也不一定等于容量，上述问题就是要讨论如何充分利用量也不一定等于容量，上述问题就是要讨论如何充分利用装置的能力，以取得最好效果流量最大），这类问题通装置的能力，以取得最好效果流量最大），这类问题通常称为最大流问题。常称为最大流问题。v

31、sv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第第53页页容量容量发点源）发点源）收点汇）收点汇）中间点中间点容量网络容量网络( ,)ijDv v的每条弧上有非负数的点的点一个入次为一个入次为0sv的点的点一个出次为一个出次为0tv其余点其余点( , ,)DV A Cijc网络有向图网络有向图D=D=（V V，A A，C C） 网络上流的基本概念网络上流的基本概念vsv1v3vtv2v48799562510第第54页页流流( ,)ijijv vf对D中任一弧都给定一个实际流量ijff 集合集合(1)(2)满足下面条件的流：容量限制条件中间点平衡

32、条件ijijcf 0 jijkkiff输出量输出量中间点的输入量中间点的输入量 ( )( )sjjtjjv fstv fff用表示网络中从的流量 vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)00f 任何网络必存在可行流，如流量为 的可行流：运输问题中，每个运运输问题中，每个运输方案就是一个流输方案就是一个流可行流可行流第第55页页 ( )ijfv f在容量网络中，寻求一个流使其流量最大网络最大流问题网络最大流问题ijijcf 0( )0( )ijjiv fffv f( , )tjv vA()is(, )is t()i t且满足此为一个特殊的

33、线性规划问题，将会看到利用图的特点，此为一个特殊的线性规划问题，将会看到利用图的特点，解决这个问题的方法要比单纯形法较为直观方便。解决这个问题的方法要比单纯形法较为直观方便。第第56页页设设是网络是网络D=（V，A，C的一个可行流的一个可行流（v1，v2是饱和的是饱和的2、如果、如果fij0，该弧是非，该弧是非0弧；弧；（v1，v2是非是非0弧弧3、如果、如果fij=0，该弧是，该弧是0流弧；流弧；弧关于流的分类弧关于流的分类ijffv1v2v1v2第第58页页割集和割集的容量割集和割集的容量vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)(1

34、11VVVV和11,VvVvts1V1V),(11VV设有网络设有网络D=V，A，C，点，点vs与点与点vt的是集合的是集合V中中的任意两点，若点集的任意两点，若点集V被剖分成两个非空集被剖分成两个非空集合合，使，使，记以，记以中的点为始点，中的点为始点，的的A A中弧的集合记为中弧的集合记为则称这个弧的集合是分离点则称这个弧的集合是分离点vs与点与点vt的割集又称截集）。的割集又称截集）。中的点为终点中的点为终点割集的容量是割集中各弧的容量之和，用割集的容量是割集中各弧的容量之和，用 表示。表示。11( ,)c V V1324( ,),(,)v vv v112134 , , tVs v vV

35、v v v割集的容量为割集的容量为9+9=189+9=18割集割集如图如图KK割集的意义：若把某一割集的弧从网络中丢去，则从割集的意义：若把某一割集的弧从网络中丢去，则从vs到到vt便不存便不存路，即割集是从路，即割集是从vs到到vt的必经之道！这里的必经之道！这里(v3,v2)不属于此割集不属于此割集第第59页页考虑考虑KK的不同画法的不同画法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)1234,v v v v t34(, ),(, )v tvt12( ,),( ,)s vs v1 , s v s2 ,s v12 ,s v v13 ,s

36、v v24 ,s v v123 ,s v v v124 ,s v v v1234 ,s v v v v234,v v v t134,v v v t134,v v v t24,v v t13,v v t1234,v v v v t4,v t t21213( ,),(,),(,)s vv vv v124( ,),(,)s vvv1324(,),(,)v vvv212323( ,),(,),(,),(, )s vv vv vv t1434( ,),(,),(, )s vvvvt243(,),(, )vvv t13434(,),(,),(, )v vvvvt152117181924142515VV割集

37、割集割集容量割集容量由于有限网络的割集只有有限多个，则截集容量的集由于有限网络的割集只有有限多个，则截集容量的集合合是有限的实数集合，令是有限的实数集合，令称割集容量为称割集容量为C0的割集为的割集为D的最小截集。的最小截集。11(,)C V V011 ( ,)Cmin C V V第第60页页111111( , ,),( ),( ,),( ,)( )( ,)ststfDV A CvvW fV Vv vV VW fC V V设 为网络的任一可行流( 为发点为收点），流量为是分离的任一割集，割集容量为C则有基本定理基本定理(可行流与割集的关系可行流与割集的关系)割集的意义：若把某一割集的弧从网络中

38、丢去，则从割集的意义：若把某一割集的弧从网络中丢去，则从vs到到vt便不存便不存路，即割集是从路，即割集是从vs到到vt的必经之道！的必经之道！最大流最大流-最小割定理：最小割定理：的最小割的容量的最小割的容量分离分离的最大流的流量的最大流的流量到到从从中，中，任一个网络任一个网络tstsvvvvG, 的的可可增增广广链链到到不不存存在在从从是是最最大大流流可可行行流流tsvvf第第61页页链及可增广链链及可增广链链链在最大流问题中，研究的是有向网络图。在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使用无向但是在求最大流的方法中，则要使用无向网络中的链。这时，就要将它看成无向

39、网网络中的链。这时，就要将它看成无向网络图，即将网络中的弧看成边。那么，以络图，即将网络中的弧看成边。那么，以发点发点vsvs为始点、以收点为始点、以收点vtvt为终点的点、边为终点的点、边交错序列即无向图中的链称为连接点交错序列即无向图中的链称为连接点vsvs、vtvt的链，并用其顶点序列来表示。的链，并用其顶点序列来表示。第第62页页( ,)( ,)ijijijijijfv vffv vf非增广链上的弧(,)(,)min0ijijijijijijijcfv vfv v()( )v fv f,ststvvvvD中，若 为从 到 的一条链，给 定向为从 到前向弧集 ：与 同向后向弧集 ：与 反

40、向，11fc30f 10nf22fcnnfc0( ,)0( ,)ijijijijijijstffcv vfcv vvv 是可行流，若则称 为从 到 的可增广链。非饱和弧非饱和弧非非0流弧流弧可增广链可增广链第第63页页这样就得到了一个寻求最大流的方法这样就得到了一个寻求最大流的方法(算法思想算法思想)：从一个可行流开始，寻求关于这个可行流的可增从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时过程，直

41、到不存在关于该流的可增广链时就得到了最大流。就得到了最大流。沿着这条链从沿着这条链从 vs vs 到到 vt vt 输送流，还有潜力可挖，输送流，还有潜力可挖，只需按照调整方法，就可以把流量提高，调整后只需按照调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。即仍为可行流。可增广链的实际意义可增广链的实际意义第第64页页求解最大流的标号算法：求解最大流的标号算法：1.()1( ,)2,:( ),min,(,)( )0,min,(,)(3)(2siijjiijijjijijiijjijijjiiijvvvvavvf

42、ccfvbvvffv 标号过程 寻找可增广链 ：（ ）给 以标号（ ）对已标号的对于 的所有未标号的邻接点若是 发出的前向非饱和弧的终点， 即令标号为；否则不标号对是 发出的后向非零弧的起点， 即令标号为；否则不标号重复)2.121tstijtijijtijvvvfffff直到 若 未得到标号，说明不存在 到 的增广链； 否则按如下方法调整。调整过程（增加流量）：增广链上的前向弧（ ）令增广链上的后向弧不在增广链上（ ）去掉所有标号，回到第 步，对可行流重新标号。()( )tw fw f则有第第65页页1v2v3vb) b) 接着检查与相邻接的点接着检查与相邻接的点1v3v2v4v5vsvtv

43、6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),( 已饱和，流量不可再增。再检查已饱和，流量不可再增。再检查 ，可调整量为，可调整量为 4-2=2，可提供量可提供量+，取调整量，取调整量1v2v2min42,2 先给标号先给标号 （，+）1） 寻找可增广链：寻找可增广链：sv第第66页页1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),(3v)

44、 1,(sv 下对已标号点可望调整点接着向下检查。下对已标号点可望调整点接着向下检查。 已饱已饱 和。再检查与和。再检查与 相邻接且未标号的点相邻接且未标号的点 6v2v,5v6v给给 标号标号 ，其中，其中 表示表示 的所调整量的所调整量2来自来自 ，且为正向流向前流）且为正向流向前流） 。)2 ,(svsv2vsv2v)2 ,(sv) 1 ,(sv第第67页页调整量为调整量为1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(

45、sv5min30, 22)2 ,(2v5v给给 标号为标号为)2 ,(2v第第68页页1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v可令调整量为可令调整量为1min3, 22)2 ,(5v给给 标号为标号为)2 ,(5v1v表示可控量，反方向流量。表示可控量，反方向流量。5v, 015 fd) 检查与 相邻接且未标号的点 ， 。而 对 来讲是流入，现欲增加流出量，应压缩 的流入量，只要的流入量1vtv1v5

46、v1v第第69页页1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5vf) 下面检查与下面检查与 相邻接且未标号的点相邻接且未标号的点 ，同理，调整量：，同理，调整量：1v4v4min52, 22给给 标号为标号为).2 ,(1v4v)2 ,(1v)2 ,(4vg) 最后，给最后，给 标号标号tv).2 ,(4vmin42, 22t第第70页页1v3v2v4v5vsvtv6v)5 , 5()2 ,

47、3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v2调整流量：从调整流量：从 到到 所画出的红线即为可增广链。沿所画出的红线即为可增广链。沿该可增广链，从该可增广链，从 倒推，标倒推，标“”号的在实际流量上加上号的在实际流量上加上该调整量，标该调整量，标“”符号的在实际流量上减去该调整量。完符号的在实际流量上减去该调整量。完成调整过程。成调整过程。svtvtv反反向向追追踪踪第第71页页1v3v2v4v5vsvtv6v)5

48、, 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 , 4()4 , 5()4 , 4()4 , 5()3 , 3() 1 , 3()2 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v第第72页页1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 ,

49、 4()4 , 5()4 , 4()4 , 5()3 , 3() 1 , 3()2 , 3()2 , 2()2 , 2(),() 1 ,(sv当标到当标到 时，与时，与 ， 相邻接的点相邻接的点 ， ， 都不满足标都不满足标号条件，标号无法继续，且没有完成标号。此时最大流量即号条件，标号无法继续，且没有完成标号。此时最大流量即为所求。为所求。) 1 ,(svsv3v1v2v6vtv12354211ssswfff312456 ,; ,;stVv vVv v v v v v标号点集未标号集12361236( , )( , ),( ,),( ,)( , )11ssssV Vv vv vv vC V

50、Vccc割集割集容量重新开始标号，寻找可增广链。重新开始标号，寻找可增广链。第第73页页最小割的意义最小割的意义第第74页页tusu1234,u u u utusu解决问题解决问题vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第第75页页vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(3)10(8),(vs,2)(-v2,2)(v1,1)(-v3,1)(v4,1)vsv1v3vtv2v48(8)7(6)9(5)9(9)5(5)6(0)2(0)5(3)10(9),(vs,1)(-v2,1)(v1,2)KKW=

51、5+9=14第第76页页下图中，下图中，A,B,C,D,E,FA,B,C,D,E,F分别表示陆地和岛屿，分别表示陆地和岛屿， 表示桥梁及其表示桥梁及其编号。若河两岸分别为互为敌对的双方部队占领，问至少应切断几座桥梁编号。若河两岸分别为互为敌对的双方部队占领，问至少应切断几座桥梁具体指出编号才能达到阻止对方部队过河的目的。试用图论方法进行分具体指出编号才能达到阻止对方部队过河的目的。试用图论方法进行分析。析。14ABCDEF8911101314127123456最大流问题应用举例最大流问题应用举例第第77页页在图中任给可在图中任给可行流，用标号行流，用标号法寻找网络最法寻找网络最大流！大流！弧容

52、量：两点间的桥梁数。弧容量：两点间的桥梁数。ABCDFE122211221122ABCDEF8911101314127123456转化为求网络最小割转化为求网络最小割第第78页页 设容量网络设容量网络G G有若干发点，若干个点，有若干发点，若干个点，可以添加两个新点可以添加两个新点vsvs，vt vt ，用容量为，用容量为 的有向边分别连结的有向边分别连结vs vs 与发点，收点与与发点，收点与vtvt，得到新的网络得到新的网络GG，G G 为只有一个发点，为只有一个发点，一个收点的网络，求解一个收点的网络，求解G G 的最大流问题的最大流问题即可得到即可得到G G的解。的解。多发点多收点网络

53、的最大流问题多发点多收点网络的最大流问题最大流问题应用举例最大流问题应用举例第第79页页 设有设有5位待业者，位待业者，5项工作，他们各自能胜任工作项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽的情况如图所示，要求设计一个就业方案，使尽量多的人能就业。量多的人能就业。1x2x3x4x5x1y2y3y4y5y其中其中51,xx 表示工人。表示工人。51,yy 表示工作。表示工作。最大匹配问题最大匹配问题第第80页页1x2x3x4x5x1y2y3y4y5y图中最大匹配问题，可以转化为最大流问题求解。在图中最大匹配问题，可以转化为最大流问题求解。在图中增加两个新点图中增加两个新

54、点 分别作为发点，收点。并用分别作为发点，收点。并用有向边把它们与原图中顶点相连，令全部边上的容量有向边把它们与原图中顶点相连，令全部边上的容量均为均为1。当网络流达到最大时，假如。当网络流达到最大时，假如 上的流量为上的流量为1，就让就让 作作 工作，此即为最大匹配方案。工作，此即为最大匹配方案。svtv,svtv),(jiyxixjy第第81页页1x2x3x4x5x1y2y3y4y5ysvtv),() 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(1x) 1 ,(1y第第82页页1x2x3x4x5x1

55、y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(4y) 1 , 1 () 1 , 1 () 1 ,(sv) 1 ,(2x)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (第第83页页1x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (第第84页页1x2x3x4

56、x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(5y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 () 1 ,(3x第第85页页1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (

57、)0 , 1 (第第86页页1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(2y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(4x) 1 ,(5y) 1 ,(3x) 1 ,(4y)0 , 1 () 1 ,(2x) 1 ,(1y) 1 ,(4x)0 , 1 (第第87页页1x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 () 1 , 1 () 1 , 1 ()

58、1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (第第88页页1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1

59、() 1 ,(sv)0 , 1 () 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(5y第第89页页1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 ,(2y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(2x) 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(

60、5y,1x,2x,3x4x,2y,1y,4y5y第第90页页第八章第八章图与网络分析图与网络分析 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第91页页第八章第八章图与网络分析图与网络分析 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用流问题最小费用流问题 第第92页页最小费用流问题最小费用流问题 最大流问题仅注意网络流的流通能力，没有考最大流问题仅注意网络流的流通能力，没有考 虑流通的费用。虑流通的费用。 实际上费用因素是很重要的。例如在交通运输实际上费用因素是很重要的。例如在交通运输 问题中，往往要求在完成运输任务的前提下，问题