运筹学图与网络分析

1、8.1 图的基本概念与基本定理图的基本概念与基本定理8.2 树和最小支撑树树和最小支撑树8.3 最短路问题最短路问题8.4最小费用流问题最小费用流问题8.5最大流问题最大流问题8.6网络计划网络计划8.7中国邮递员问题中国邮递员问题8.7指派问题指派问题 图论是应用非常广泛的运筹学分支，它图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方生活中的许

2、多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。简便、快捷地加以解决。 随着科学技术的进步，特别是电子计随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描的工程系统和管理问题用图的理论加以描述，可以解决许

3、多工程项目和管理决策的述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。术人员和经营管理人员的重视。 关于图的第一篇论文是瑞士数学家欧拉关于图的第一篇论文是瑞士数学家欧拉（E. Euler）在）在1736年发表的解决年发表的解决“哥尼哥尼斯堡斯堡” 七桥难题的论文；七桥难题的论文； 德国的哥尼斯堡城有一条普雷格尔河，德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（见图座桥相互连接，（见图8.1 8.1 a a）当地的居民热当地的居民

4、热衷于这样一个问题，一个漫步者如何能够走衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，没有成功。为了寻找答案，1736年欧拉将这年欧拉将这个问题抽象成图个问题抽象成图8.1b所示图形的一笔画问题。所示图形的一笔画问题。图图 8.1 8.1 a aA AB BC CD DA AB BC CD DC CA AD DB B图图8.1 8.1 b b即能否从某一点开始不重复地一笔画出这个图形，即能否从某一点开始不重复地一笔画出这个图形，

5、最终回到原点。欧拉在他的论文中证明了这是不可最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。第一个著名问题。 在实际的生产和生活中，人们为了反映事物在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样之间的关系，常常在纸上用点和线来画出各式各样的示意图。的示意图。 图图8.28.2是我国北京、上海、重庆等是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点十四个城市之间的

6、铁路交通图，这里用点表示城市，用点与点之间的线表示城市之表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。管道图，民用航空线图等等。石家庄石家庄太原太原北京北京天津天津塘沽塘沽济南济南青岛青岛徐州徐州连云港连云港南京南京上海上海郑州郑州武汉武汉重庆重庆图图8.28.2 有六支球队进行足球比赛，我有六支球队进行足球比赛，我们分别用点们分别用点v1 ，v6表示这六支球队，它表示这六支球队，它们之间的比赛情况，也可以用图反映出来，们之间的比赛情况，也可以用图反映出来，已知已知v1 1队战胜队战胜v2 2 队，队，v2

7、 队战胜队战胜v3 3 队，队，v3 3 队队战胜战胜v5队，如此等等。这个胜负情况，可以队，如此等等。这个胜负情况，可以用图用图8.38.3所示的有向图反映出来所示的有向图反映出来图图8.38.3v3v5v2v4v6v1 从以上的几个例子可以看出，我们用从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下

8、，图中的相对定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图要，因此，图论中的图与几何图，工程图等本质上是不同的。等本质上是不同的。 综上所述，图论中的图是由点和点与点之间的综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把线所组成的。通常，我们把点与点之间不带箭头的点与点之间不带箭头的线叫做线叫做边边，带箭头的线叫做，带箭头的线叫做弧弧。 如果一个图是由点和边所构成的，那么，称为如果一个图是由点和边所构成的，那么

9、，称为无向图无向图，记作，记作G=(V，E)，其中，其中V表示图表示图G 的点集合，的点集合，E表示图表示图G的边集合。连接点的边集合。连接点vi , vjV 的边记作的边记作vi , vj，或者或者vj , vi。 如果一个图是由点和弧所构成的，那么称为它如果一个图是由点和弧所构成的，那么称为它为为有向图有向图，记作，记作D=(V, A)，其中，其中V表示有向图表示有向图D的点的点集合，集合，A表示有向图表示有向图D的弧集合。一条方向从的弧集合。一条方向从vi 指向指向vj 的弧，记作的弧，记作( (vi , vj) )。图图8.48.4是一个无向图是一个无向图G=（V，E），）， 其中其中

10、V=v1 , v2 , v3 , v4 E=v1 , v2,v2 ,v1,v2 ,v3, v3 ,v4,v1 ,v4, v2 ,v4, v3 ,v3v3v2v1v4图图8.48.4 是一个有向图是一个有向图D=（V，A）其中其中V=v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 A=(v1,v2),(v1,v3),(v3 ,v2)(v3 ,v4),(v2 ,v4),(v4 ,v5), (v4 ,v6),(v5 ,v3),(v5 ,v4), (v5 ,v6),(v6 ,v7)图图8.5v7v5v3v4v2v6v1 一个图一个图G或有向图或有向图D中的中的点数点数, ,记作记作P(G)或或P

11、(D), ,简记作简记作P, ,边数或者弧数边数或者弧数, ,记作记作q(G)或者或者q(D), ,简记作简记作q 。 如果边如果边 vi ,vj E ,那么称那么称vi , vj 是边的是边的端点端点，或者或者vi ,vj是是相邻的相邻的。如果一个图。如果一个图G中，中，一条边的两一条边的两个端点是相同的个端点是相同的, ,那么称为这条边是环，那么称为这条边是环，如图如图8.48.4中的边中的边 v3 ,v3 是环。是环。如果两个端点之间有两条以如果两个端点之间有两条以上的边，那么称为它们为多重边，上的边，那么称为它们为多重边，如图如图8.48.4中的边中的边v1 ,v2 ,v2 ,v1 。

12、一个无环，无多重边的图称为简一个无环，无多重边的图称为简单图，单图，一个无环，有多重边的图称为多重图。一个无环，有多重边的图称为多重图。 以点以点v为端点的边的个数称为点为端点的边的个数称为点v的度，的度，记 作记 作 d ( v ) , , 如 图如 图 8 8 4 4 中中 d ( v1) = 3= 3 ， d(v2 )=4,=4,d(v3 )=4,d(v4 )=3。 度为零的点称为弧立点，度为度为零的点称为弧立点，度为1 1的点称为的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。的点称为奇点，度为偶数的点称为偶点。

13、端点的度端点的度 d(v)：点：点 v 作为端点的边的个数作为端点的边的个数 奇点：奇点：d(v)= =奇数；奇数；偶点：偶点：d(v) = 偶数；偶数；悬挂点：悬挂点：d(v)=1；悬挂边：悬挂边：与悬挂点连接的边；与悬挂点连接的边；孤立点：孤立点：d(v)=0；空图：空图：E = ，无边图无边图v1v2v3v4v5v6v1v7v6v5v4v3v2V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 d(v1)=3 ; d(v2)=5 ;d(v3)=4 ; d(v4)=4 ;d(v5)=1 ; d(v6)=3;d(v7)=0其中其中 v5 为悬挂点，为悬挂点， v7 为孤立点。

14、为孤立点。 定理定理8.18.1 所有顶点度数之和等于所有边数所有顶点度数之和等于所有边数的的2 2倍。倍。 证明：证明：因为在计算各个点的度时，每条边因为在计算各个点的度时，每条边被它的两个端点个用了一次。被它的两个端点个用了一次。v1v5v4v3v2简单图简单图（2）（4）（3）（3）（2）v1v5v4v3v2多重图多重图（4）（6）（3）（3）（2） 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。设设 V1 1，V2 2 分别是图分别是图G中奇点和偶点的中奇点和偶点的 集合，由定理集合，由定理8.1 8.1 ，有，有 122VvVvVvqvdvdvd)()()(因为因为

15、 是偶数，是偶数， 也是偶数，因此也是偶数，因此 Vvvd)( 1Vvvd)( 2Vvvd)(也必是偶数，从而也必是偶数，从而V1 中的点数是偶数。中的点数是偶数。链：链：由两两相邻的点及其相关联的边构成的点由两两相邻的点及其相关联的边构成的点边序列。边序列。 如如: :v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ， vn ; v0 ，vn分别为链的起点和终点分别为链的起点和终点 。记作。记作（ v0 ,v1 , v2， ,v3 , , vn-1 , vn ）简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：初等链：链中所含的点均不相同链中所含的

16、点均不相同, , 也称通路；也称通路；圈：圈：若若 v0 vn 则称该链为开链，否则称则称该链为开链，否则称为为闭链或回路或圈闭链或回路或圈；简单圈：简单圈：如果在一个圈中所含的边均不相同如果在一个圈中所含的边均不相同初等初等圈：圈：除起点和终点外链中所含的点除起点和终点外链中所含的点 均均 不相同的圈；不相同的圈；连通图：连通图：图中任意两点之间均图中任意两点之间均 至少有一条通路，否则至少有一条通路，否则 称为不连通图。称为不连通图。v1v2v4v3v5v6v7v8v9初等链初等链: (v1 , v2 , v3 , v6 , v7 , v5 )初等圈：初等圈： (v1 , v2 , v3

17、, v5 , v4 , v1 )简单圈：简单圈： (v4 , v1 , v2 , v3 , v5 , v7 , v6 ,v3 , v4 )简单链：简单链：(v1 , v2 , v3 , v4 ,v5 , v3 ) 以后除特别声明，均指初等链和初等圈。以后除特别声明，均指初等链和初等圈。v1v2v3v4v5连通图连通图v1v5v4v3v2v6子图定义：子图定义：如果如果 V2 V1 , E2 E1 称称 G G2 2 是是 G G1 1 的子图；的子图；真子图：真子图：如果如果 V2 V1 , E2 E1 称称 G2 是是 G1 的真子图；的真子图；部分图：部分图：如果如果 V2 = V1 ,

18、E2 E1 称称 G2 是是 G1 的部分图或支撑子图；的部分图或支撑子图； 导出子图：导出子图： 如果如果V V2 2 V V1 1, , E2=vi,vj vi,vj V2, ,称称 G2 是是 G1 中由中由V2 导出导出的导出子图。的导出子图。G G1 1G G2 2真子图真子图G G3 3子图子图部分图部分图G G4 4导出子图导出子图 G G5 5生成树生成树 G G6 6G G5 5余树余树有向图：关联边有方向有向图：关联边有方向弧：弧：有向图的边有向图的边 a=(u ,v), ,起点起点u , ,终点终点v；路：路：若有从若有从 u 到到 v 不考虑方向的链不考虑方向的链, ,

19、且且 各方向一致各方向一致, ,则称之为从则称之为从u到到v 的路；的路；初等路初等路: : 各顶点都不相同的路；各顶点都不相同的路； 初等回路初等回路: :u = v 的初等路的初等路; 连通图：连通图： 若不考虑方向若不考虑方向 是无向连通图是无向连通图; ; 强连通图：强连通图：任两点有路任两点有路; ;v1v2v3v4v5一、树及其性质一、树及其性质 在各种各样的图中，有一类图是十在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是分简单又非常具有应用价值的图，这就是 例例8.38.3 已知有六个城市，它们之间已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以

20、要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。互相通话，并且电话线的总长度最短。如果用六个点如果用六个点v1 1v6 6代表这六个城市，在任代表这六个城市，在任意两个城市之间架设电话线，即在相应的两意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个个点之间连一条边。这样，六个城市的一个电话网就作成一个图。表示任意两个城市之电话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市

21、的一个掉一条边，剩下的图仍然是六个城市的一个电话网。图电话网。图8.88.8是一个不含圈的连通图，代表是一个不含圈的连通图，代表了一个电话线网。了一个电话线网。图图8.8v6v3v4v2v5v1 一个无圈的连通图叫做一个无圈的连通图叫做。 设图设图G=（V，E）是一个树是一个树 P(G) 2，那么图那么图G中至少有两个悬挂点。中至少有两个悬挂点。 定理定理8.4 8.4 图图G=（V，E）是一个树的充要条件是一个树的充要条件是是G 不含圈，并且有且仅有不含圈，并且有且仅有P-1条边。条边。 图图G=（V，E）是一个树的充要条件是是一个树的充要条件是G是连通图，并且有且仅有是连通图，并且有且仅有

22、 p1 条边。条边。 图图G是一个树的充分必要条件是任意两是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。个顶点之间有且仅有一条链。 从以上定理，不难得出以下从以上定理，不难得出以下结论结论： （1 1）从一个树中任意去掉一条边，那）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。同的图中，树是含边数最少的连通图。 （2 2）在树中不相邻的两个点之间加上）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。一条边，那么恰好得到一个圈。二二. .支撑树支撑树 设图设图K=( V , EI )是图

23、是图G=(V , E )的的 一支撑子图一支撑子图，如果图，如果图K=(V,EI) 是一个树是一个树, ,那么称那么称K 是是G 的一个支撑树。的一个支撑树。 例如例如, ,图图8.10b 8.10b 是图是图8.10a 8.10a 的一个支撑树的一个支撑树图图8.10v6v5v2v3v4v1av6v5v2v3v4v1b 显然显然, ,如果图如果图K=(V,EI)是图是图G=(V,E)的一个的一个支撑树支撑树, ,那么那么K 的边数是的边数是p(G)-1，G中不属于中不属于支撑树支撑树K 的边数是的边数是q(G)-p(G)+1。 一个图一个图G有支撑树的充要条件有支撑树的充要条件是是G 是连通

24、图是连通图。 证明：证明：充分性充分性: : 设图设图G是连通的，若是连通的，若G不不含圈，则按照定义，含圈，则按照定义，G是一个树，从而是一个树，从而G是是自身的一个支撑树。若自身的一个支撑树。若G含圈，则任取含圈，则任取G的的一个圈，从该圈中任意去掉一条边，得到图一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图的一支撑子图G1。若若G1不含圈，则不含圈，则G1是是G的一个支撑树。若的一个支撑树。若G1仍然含圈，则任取仍然含圈，则任取G G1 1的的一个圈，再从圈中任意去掉一条边，得到图一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图的一支撑子图G2。依此类推，可以得到图依此类推，可

25、以得到图G的一个支撑子图的一个支撑子图GK，且不含圈，从而且不含圈，从而GK是是一个支撑树。一个支撑树。 定理定理8.78.7充分性的证明，提供了一个充分性的证明，提供了一个寻找连通图支撑树的方法叫做寻找连通图支撑树的方法叫做“破圈法破圈法”。就是从图中任取一个圈，去掉一条边。再就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。为止，这样就得到一个支撑树。 例例8.48.4 用破圈法求出图用破圈法求出图8-118-11的一个支的一个支撑树。撑树。e e4 4e e6 6e e5 5e e3 3e e2 2e

26、e1 1e e7 7e e8 8v3v2v1v4v5图图8-118-11取一个圈取一个圈( (v1,v2,v3,v1) )，在一个圈中去掉边，在一个圈中去掉边e3 。在剩下的图中，再取一个圈（在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），），去掉边去掉边e4 。再从圈（。再从圈（v3,v4 v5,v3）中去掉边）中去掉边e6 。再从圈再从圈( (v1,v2,v5,v4,v3,v1 ）中去掉边）中去掉边e7， 这样，这样，剩下的图不含圈，于是得到一个剩下的图不含圈，于是得到一个 支撑树，如支撑树，如图图8.128.12所示。所示。v2e1e2e5e8v1v3v4v5图图8.128.1

27、2三三. .最小支撑树问题最小支撑树问题 定义定义8.38.3 如果图如果图G=（V，E），对于，对于G中的每一条边中的每一条边 vi ,vj ，相应地有一个数，相应地有一个数Wij ，那么称这样的图那么称这样的图G为赋权图，为赋权图，Wij称为边称为边 vi ,vj 的权。这里所指的权，是具有广义的数量值。的权。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。含义。例如长度，费用、流量等等。 赋权图在图论及实际应用方面有着重要赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程的

28、地位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的技术等领域，最小支撑树问题就是赋权图的最优化问题之一。最优化问题之一。 设设G=（V，E）是一个连通图，是一个连通图，G的每的每一条一条 vi ,vj 对应一个非负的权对应一个非负的权Wij。 定义定义8.48.4 如果图如果图T=（V，EI）是图是图G的的一个支撑树，那么称一个支撑树，那么称EI上所有边的权的和为上所有边的权的和为支撑树支撑树T的权，记作的权，记作S(T)。 如果图如果图G的支撑树的支撑树T*的权的权S(T*)，在在G 的的所有支撑树所有支撑树T中的权最小，即中的权最小，即S(T*)=minTS(T)，

29、那么称那么称T*是是G的最小支撑树。的最小支撑树。 如前所述，在已知的几个城市之间联结电话线如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个网，要求总长度最短和总建设费用最少，一个问题的问题的 解决可以归结为最小支撑树问题。解决可以归结为最小支撑树问题。 再如，城市间交通线的建造等，都可以归再如，城市间交通线的建造等，都可以归结为这一类问题。结为这一类问题。 下面介绍寻求最小支撑树的方法下面介绍寻求最小支撑树的方法-破圈法破圈法。在给定的连通图中任取一个圈，去掉权最大的在给定的连通图中任取一个圈，去掉权最大的一条边，如果有两条以上权最大的边，则任意一条边，如果有

30、两条以上权最大的边，则任意去掉一条。在剩下的图中，重复以上步骤，去掉一条。在剩下的图中，重复以上步骤，直到得到一个不含圈的连通图为止，这个图直到得到一个不含圈的连通图为止，这个图便是最小支撑树。便是最小支撑树。 例例8.58.5 某六个城市之间的道路网如图某六个城市之间的道路网如图8.138.13a 所示，要求沿着已知长度的道路联结所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度六个城市的电话线网，使得电话线的总长度最短。最短。图图8.13av3v2v1v4v6v553142图图8.13b3v6v5v2v3v46255441v17 73 3 解：解：这个问题的解决就是要求

31、所示赋权这个问题的解决就是要求所示赋权图图8.13a8.13a中的最小支撑树。用破圈法求解。中的最小支撑树。用破圈法求解。任取一个圈，例如（任取一个圈，例如（ v1 ,v2 ,v3 ,v1 ），去掉），去掉这个圈中权最大的边这个圈中权最大的边 v1 ,v3 。再取一个圈。再取一个圈（ v3 , v5 , v2 ,v3），去掉边），去掉边 v2 , v5 。再取一。再取一个圈（个圈（ v3 , v5 ,v4 , v2 ,v3），去掉边），去掉边 v3 ,v5 。再取一个圈（再取一个圈（v5 ,v6 ,v4 ,v5），这个圈中，有），这个圈中，有两条权最大的边两条权最大的边 v5 ,v6 和和v4

32、 ,v6。任意去掉。任意去掉其中的一条，例如其中的一条，例如 v5 , v6 。这时得到一个。这时得到一个不含圈的图，如图不含圈的图，如图8.138.13b 所示，即是最小支所示，即是最小支撑树。撑树。 关于破圈法正确性的证明略去。关于破圈法正确性的证明略去。 例例 用破圈法求出下图中的最小支撑树用破圈法求出下图中的最小支撑树3122353223225422232232122破圈法和生长法两个方法：破圈法和生长法两个方法：（1 1）在网络图中寻找一个圈。若不存在圈，）在网络图中寻找一个圈。若不存在圈， 则已经得到最短树或网络不存在最短树；则已经得到最短树或网络不存在最短树；（2 2）去掉该圈中

33、权数最大的边；）去掉该圈中权数最大的边； 反复重复反复重复 两步，直到最短树。两步，直到最短树。从网络图中任意节点开始寻找与该节点从网络图中任意节点开始寻找与该节点关联的权数最小的边，得到另一节点后，关联的权数最小的边，得到另一节点后，再从这个新节点开始寻找与该节点关联再从这个新节点开始寻找与该节点关联的权数最小的另一边的权数最小的另一边。注意寻找过。注意寻找过程中，节点不得重复，即在找最小权数程中，节点不得重复，即在找最小权数边时不考虑已选过的边边时不考虑已选过的边, ,反复进行，直反复进行，直到得到最短树或证明网络不存在最短树。到得到最短树或证明网络不存在最短树。例例 用成长法求出下图中的

34、最小支撑树（最短用成长法求出下图中的最小支撑树（最短 树）树）v1v2v3v4v5v6v7v1v2v3v4v5v6v731245223423122223一一. .引言引言 最短路径问题是图论中十分重要的最最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的局，设备更新等等。也可以用于解决其它的最优化问题。最优化问题。 如图如图8.148.14所示的单行

35、线交通网，每所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现个弧旁边的数字表示这条单行线的长度。现在有一个人要从在有一个人要从v v1 1出发，经过这个交通网到出发，经过这个交通网到达达v v8 8，要寻求是总路程最短的线路。，要寻求是总路程最短的线路。图图8.14v1v4v2v8v7v6v5v9636234102312624101 从从v1到到v8 的路线是很多的。比如从的路线是很多的。比如从v1出出发，经过发，经过v2 , v5到达到达v8 或者从或者从v1出发，经过出发，经过v4 ，v6 ，v7 到达到达v8 等等。但不同的路线，经等等。但不同的路线，经过的总长度是不同的。例

36、如，按照第一个过的总长度是不同的。例如，按照第一个线路，总长度是线路，总长度是6+1+6=136+1+6=13单位，按照第二单位，按照第二个路线，总长度是个路线，总长度是1+10+2+4=171+10+2+4=17单位。单位。从这个例子中，可以给出一般意义下的最从这个例子中，可以给出一般意义下的最短路问题。设一个赋权有向图短路问题。设一个赋权有向图D=（V，A），），对于每一个弧对于每一个弧a =（vi ,vj），相应地有一个，相应地有一个权权wij。Vs ,vt是是D中的两个顶点，中的两个顶点，P 是是D中从中从vs到到vt 的任意一条路，定义路的权是的任意一条路，定义路的权是P P 中所有

37、中所有弧的权的和，记作弧的权的和，记作S(p)。最短路问题就是要最短路问题就是要在所有从在所有从vs到到vt的路的路P0中，寻找一个权最小中，寻找一个权最小的路的路P0 ，亦即亦即S(P0)=minS(p)。P0 叫做从叫做从vs到到vs的最短路。的最短路。P0的权的权S S(P0) 叫做从叫做从vs到到vt 的的距离，记作距离，记作d（vs，vt）。）。由于由于D是有向图，是有向图，很明显很明显d（vs，vt）与与d（vt，vs）一般不相等一般不相等。 二二. .Dijkstra算法算法 下面介绍在一个赋权有向图中寻求最下面介绍在一个赋权有向图中寻求最短路的方法短路的方法Dijkstra算法

38、，它是在算法，它是在19591959年提出来的。目前公认，在所有的权年提出来的。目前公认，在所有的权wij 00时，这个算法是寻求最短路问题最好的时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻算法。并且，这个算法实际上也给出了寻求从一个始定点求从一个始定点vs到任意一个点到任意一个点vj的最短路。的最短路。Dijkstra算法的基本思想是从算法的基本思想是从vs出发，逐步出发，逐步向外寻找最短路。在运算过程中，与每个点向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它对应，记录一个数，叫做一个点的标号。它或者表示从或者表示从vs到该点的最短路权

39、（叫做到该点的最短路权（叫做P P 标标号），或者表示从号），或者表示从v vs s 到该点最短路权的上到该点最短路权的上界（叫做界（叫做T 标号）。算法的每一步是去修改标号）。算法的每一步是去修改T标号，把某一个具有标号，把某一个具有T 标号的点改变为具标号的点改变为具有有P 标号的点，使图标号的点，使图D中具有中具有P 标号的顶点标号的顶点多一个。这样，至多经过多一个。这样，至多经过P-1 步，就可求出步，就可求出从从vs 到各点到各点vj 的最短路。的最短路。 以例以例1 1为例说明这个基本思想。在例为例说明这个基本思想。在例1 1中，中，S=1。因为因为Wij 0，d（v1 ,v1）=

40、0。这时，这时，v1是具有是具有P标号的点。现在看从标号的点。现在看从v1出发的三条出发的三条弧弧（v1 ,v2），（），（v1 ,v3）和（）和（v1 ,v4）。）。如果一如果一个人从个人从v1出发沿（出发沿（v1 ,v2）到达）到达v2，这时的路，这时的路程是程是d（v1,v1）+w12=6单位。如果从单位。如果从v1出发，出发，沿沿（v1 ,v3）到达到达v3 ，则是则是d（v1 ,v1）+w13=3单位。同理，沿单位。同理，沿（v1 ,v4）到达到达v4，是，是d（v1, v1）+w14=1单位。因此，他从单位。因此，他从v1出发到达出发到达v4的的最短路必是最短路必是（v1 , v4

41、），），d（v1 ,v4）=1。这是因为从这是因为从v v1 1到达到达v4的任一条路的任一条路P P，假如不是，假如不是（v1 ,v4），），则必先沿则必先沿（v1 ,v2）到达到达v2，或者，或者沿沿（v1 ,v3）到达到达v3，而这时的路程已是而这时的路程已是6 6或者或者3 3单位。由于所有的权单位。由于所有的权wij 0，因此，不论他因此，不论他如何再从如何再从v2 或者或者v3 到达到达v4 ，所经过的总路程所经过的总路程都不会比都不会比1 1少，于是就有少，于是就有d（v1 ,v4）=1。这样这样就使就使v4 变成具有变成具有P标号的点。现在看从标号的点。现在看从v1 和和v4指

42、向其余点的弧。如上所述，从指向其余点的弧。如上所述，从v1出发，分出发，分别沿别沿（v1 ,v2），（），（v1 ,v3）到达到达v2，v3，经过经过的路程是的路程是6 6或者或者3 3单位。从单位。从v4出发沿出发沿（v4 ,v6）到达到达v6，经过的路程是，经过的路程是d（v1,v4）+ w46=1 +10=11单位。而单位。而min d（v1 ,v1）+w12，d（v1 ,v1）+w13，d（v1 ,v4）+w46=d（v1,v1）+w13=3单位。根据同样的理由，可以断定，单位。根据同样的理由，可以断定，从从v1 1 到达到达v3 3的最短路是（的最短路是（v1,v3），），d（v1,

43、v3）=3。这样，又使点这样，又使点v3 3变为具有变为具有P标号的点，标号的点，不断重复以上过程，就可以求出从不断重复以上过程，就可以求出从vs到达任到达任一点一点vj的最短路。的最短路。(0,0)(6,1)(3,1)(1,1)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101v1v4v2v8v7v6v5v9636234102312624101(6,1)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(6,1)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9

44、636234102312624101(5,2)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)

45、(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(

46、0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)从从v1 到到 v8 的最短路的长度为：的最短路的长度为：12从从v1 到到 v8 的最短路线为：的最短路线为：v8v5v2v1步骤：步骤：1、给起点一个永久标号给起点一个永久标号（0，0）。永久标。永久标号用下划线表示；标号中的第一个数表示号用下划线表示；标号中的第一个数表示从起点到该点的距离；第二个数表示该点从起点到该点的距离；第二个数表示该点的前面没有点了。的前面没有点了。2、修改非永久标号点修改非永久标号点 vi 的临时标号为的临时标号为

47、 (a,b), 其中其中 a 为以为以 vi 为终点的弧，如果其起点为永为终点的弧，如果其起点为永久标号，则求其永久标号的第一个数与弧长久标号，则求其永久标号的第一个数与弧长的和，如果这样的和有多个，则取最小值。的和，如果这样的和有多个，则取最小值。b为前一个点的下标。为前一个点的下标。3、在临时标号中取第一个标号的最小值，在临时标号中取第一个标号的最小值，将该标号该为永久标号，再返回到将该标号该为永久标号，再返回到 2步步三、含有负权的最短路的求法三、含有负权的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8例：例： 求从求从v1 到到v8 的最

48、短路的最短路83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-1583-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-1-583-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v

49、4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56从从v1 到到 v8 的最短路的长度为：的最短路的长度为：6从从v1 到到 v8 的最短路线为：的最短路线为：v8v6v3v1最小费用流问题最小费用流问题一一 引言引言 在许多实际的网络系统中都存在着流量在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十络系统流最大流问

50、题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。问题起着十分重要的作用。 图图8.198.19是联结某个起始地是联结某个起始地vs和目的地和目的地vt的的交通运输网，每一条弧交通运输网，每一条弧vi 旁边的权旁边的权cij表示这段表示这段运输线的最大通过能力，货物经过交通岗从运输线的最大通过能力，货物经过交通岗从vs运送到运送到vt.要求指定一个运输方案，使得从要求指定一个运输方案，使得从vs到到vt的货运量最大，这个问题就是寻求网络系统的货运量最大，这个问题就是寻求网络系统的最大流问题。的最大流问题。问题描述问题描述连

51、通网络连通网络 G(V, A) 有有 m 个节点个节点, n条弧条弧, 弧弧 eij 上的流量上界为上的流量上界为 cij, 求从起始节点求从起始节点 vs 到终点到终点 vt 的最大流量。的最大流量。图图8.198.19vtv3v2v1v4vs1735108611453Cij 定义定义8.58.5 设一个赋权有向图设一个赋权有向图D=（V,A）, ,在在V 中指定一个发点中指定一个发点vs和一个收点和一个收点vt , ,其它的其它的点叫做中间点。对于点叫做中间点。对于D中的每一个弧（中的每一个弧（vi ,vj）A, ,都有一个都有一个权权叫做弧的叫做弧的容量容量。我们把这样。我们把这样的图的

52、图D叫做一个叫做一个网络系统，简称网络网络系统，简称网络，记做，记做D=（V，A，C）。）。 网络网络D上的流上的流，是指定义在弧集合，是指定义在弧集合A上的上的一个函数一个函数f=f(vi ,vj)=fjj f(vi ,vj)=fij叫做弧叫做弧(vi ,vj)上的流量。上的流量。 例如图例如图8.198.19就是一个网络。每一个弧旁边就是一个网络。每一个弧旁边的权就是对应的容量（最大通过能力）的权就是对应的容量（最大通过能力）cij . 图图8.208.20表示的就是这个网络上的一个流表示的就是这个网络上的一个流（运输方案），每一个弧上的流量（运输方案），每一个弧上的流量fij就是运就是运

53、输量。例如输量。例如fs1=5 , fs2=3 , f13=2 等等。等等。 对于实际的网络系统上的流，有几个显著对于实际的网络系统上的流，有几个显著的特点：的特点：(1)(1)发点的总流出量和收点的总流入发点的总流出量和收点的总流入量必相等。量必相等。(2)(2)每一个中间点的流入量与流出每一个中间点的流入量与流出量的代数和等于零。量的代数和等于零。(3)(3)每一个弧上的流量每一个弧上的流量不能超过它的最大通过能力（即容量）不能超过它的最大通过能力（即容量） 于是有：于是有：v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt图图8.208.20 网络

54、上的一个流网络上的一个流f 叫做可行流，叫做可行流，如果如果f 满足以下条件满足以下条件 （1 1）容量条件：）容量条件：对于每一个弧对于每一个弧（vi ,vj）A, ,有有 0 fij cij . （2 2）平衡条件：）平衡条件： AvvAvvsjjsjssjfvff),(),()(对于发点对于发点vs, ,有有对于收点对于收点vt, ,有有 AvvAvvt jjtjttjfvff),(),()(对于中间点，有对于中间点，有 AvvAvvi jjijiijff),(),(0 任意一个网络上的可行流总是存在的。任意一个网络上的可行流总是存在的。例如零流例如零流v(f)=0, ,就是满足以上条件

55、的可行流。就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网网络系统中最大流问题就是在给定的网络上寻求一个可行流络上寻求一个可行流f f, ,其流量其流量v v( (f f) )达到最大达到最大值。值。 设流设流f =fij是网络是网络D上的一个可行流。我上的一个可行流。我们把们把D中中fij=cij的弧叫做饱和弧，的弧叫做饱和弧，fij0的弧为非零流弧，的弧为非零流弧，fij=0的弧的弧叫做零流弧叫做零流弧 . . 在图在图8.208.20中，中，(v4 ,v3)是饱和弧，其他的弧是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。是非饱和弧，并且都是非零流弧。 设设是网络是网络D中

56、连接发点中连接发点s和收点和收点vt的一条的一条链。定义链的方向是从链。定义链的方向是从s到到 vt ，于是链，于是链上的上的弧被分为两类：一类是弧的方向与链的方向相弧被分为两类：一类是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做同，叫做前向弧，前向弧的集合记做+。二类二类是弧的方向与链的方向相反，叫做后向弧，是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做后向弧的集合记做。 例如在图例如在图8.198.19中，在链中，在链（vs,v1,v2,v3,v4,vt)中，中， + = vs,v1,(v1,v2),(v2,v3),(v4,vt), = (v4 ,v3).如果链如果链满足以

57、下条件：满足以下条件： 1 1在弧在弧（vi ,vj）+上，有上，有0 fijcij, ,即即+中的每一条弧是非饱和弧。中的每一条弧是非饱和弧。 2 2在弧在弧（vi,vj）上，有上，有0fij cij,即即中中的每一条弧是非零流弧。的每一条弧是非零流弧。 例如在图例如在图8.208.20中，链中，链=（vs,v1,v2,v3,v4,vt）就就是一条增广链。是一条增广链。 设图设图D=(V，A，C)，点集点集S，T V,ST=。将起点在将起点在S，终点在终点在T T 的所有弧作成集合，记的所有弧作成集合，记做做（S，T）。）。 定义定义8.88.8 设一个网络设一个网络D=（V，A，C）。如果

58、点集如果点集V 被剖分为两个非空集合被剖分为两个非空集合v1和和 ，发点发点vsv1,收点收点vt , ,那么将弧集（那么将弧集（v1 ， ）叫做是分离叫做是分离vs和和vt的截集。的截集。1V1V1V 定义定义8.98.9 设一个截集设一个截集（V1 , ）.将阶截集将阶截集（V1 , ）中所有的弧的容量的和叫做截集的中所有的弧的容量的和叫做截集的截量，记做截量，记做 s( V1 , ) , 亦即亦即1V1V1V ),(),(,1111VVvvjijicVVs下面的事实是显然的：一个网络下面的事实是显然的：一个网络D中，任何一中，任何一个可行流个可行流 f 的流量的流量v (f ) 都小于或

59、等于这个网络都小于或等于这个网络中任何一个截集中任何一个截集(V1 , )的截量。并且，如果的截量。并且，如果1V网络上的一个可行流网络上的一个可行流 f * * 和网络中的一个截和网络中的一个截集（集（V1*, ），满足条件，满足条件v*(f* )=c (V1* , ) ,那么那么f * 一定是一定是D D上的最大流，而上的最大流，而（V1*, ）一一定是定是D的所有的截集中截量最小的一个（即最的所有的截集中截量最小的一个（即最小截集）小截集）*1V*1V*1V 定理定理8.88.8 网络中的一个可行流网络中的一个可行流f*是最大流是最大流的充分必要条件是，不存在关于的充分必要条件是，不存在

60、关于f*的增广链。的增广链。 定理定理8.98.9 在一个网络在一个网络D中，最大流的流量中，最大流的流量等于分离等于分离vs 和和vt 的最小截集的截量。的最小截集的截量。 定理定理8.88.8为我们提供了一个寻求网络系为我们提供了一个寻求网络系统最大流的方法。亦即，如果网络统最大流的方法。亦即，如果网络D中有一中有一个可行流个可行流 f，只要判断网络是否存在关于可，只要判断网络是否存在关于可行流行流 f 的增广链的增广链 。如果没有增广链，那么。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照一定是最大流。如有增广链，那么可以按照定理定理 8.98.9中必要性，不断改进和增大可