运筹学8图与网络分析.ppt

《运筹学8图与网络分析.ppt》由会员分享，可在线阅读，更多相关《运筹学8图与网络分析.ppt（167页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 图与网络分析图与网络分析主要内容：主要内容：8.1 图的基本概念与基本定理图的基本概念与基本定理8.2 树和最小支撑树树和最小支撑树8.3 最短路问题最短路问题8.4最小费用流问题最小费用流问题8.5最大流问题最大流问题8.6网络计划网络计划8.7中国邮递员问题中国邮递员问题8.7指派问题指派问题8.1 图的基本概念与基本定理图的基本概念与基本定理 图图论论是是应应用用非非常常广广泛泛的的运运筹筹学学分分支支，它它已已经经广广泛泛地地应应用用于于物物理理学学控控制制论论，信信息息论论，工工程程技技术术，交交通通运运输输，经经济济管管理理，电电子子计计算算机机等等各各项项领领域域。

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

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

4、图座桥相互连接，（见图8.1 a8.1 a）当地的居民热当地的居民热衷于这样一个问题，一个漫步者如何能够走衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，没有成功。为了寻找答案，1736年欧拉将这年欧拉将这个问题抽象成图个问题抽象成图8.1b所示图形的一笔画问题。所示图形的一笔画问题。哥尼斯堡七桥问题哥尼斯堡七桥问题图图 8.1 a8.1 aA AB BC CD D哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形其

5、中的四个顶点都是奇顶点其中的四个顶点都是奇顶点A AB BC CD DC CA AD DB B图图8.1 b8.1 b即能否从某一点开始不重复地一笔画出这个图形，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。第一个著名问题。在实际的生产和生活中，人们为了反映事物在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上

6、用点和线来画出各式各样之间的关系，常常在纸上用点和线来画出各式各样的示意图。的示意图。例例8.18.1 图图8.28.2是我国北京、上海、重庆等是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。管道图，民用航空线图等等。石家庄石家庄太原太原北京北京天津天津塘沽塘沽济南济南青岛青岛徐州徐州连云港连云港南京南京上海上海郑州郑州武汉武汉重庆重庆图图8.28.2 例例8.28.2 有六支球

7、队进行足球比赛，我有六支球队进行足球比赛，我们分别用点们分别用点v1，v6表示这六支球队，它表示这六支球队，它们之间的比赛情况，也可以用图反映出来，们之间的比赛情况，也可以用图反映出来，已知已知v1 1队战胜队战胜v2 2 队，队，v2 队战胜队战胜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的的弧弧集集合

10、合。一一条条方方向向从从vi 指指向向vj 的的弧，记作弧，记作(vi,vj)。例如例如.图图8.48.4是一个无向图是一个无向图G=（V，E），），其中其中V=v1,v2,v3,v4 E=v1,v2,v2,v1,v2,v3,v3,v4,v1,v4,v2,v4,v3,v3v3v2v1v4图图8.48.4图图8.58.5 是一个有向图是一个有向图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.5

11、v7v5v3v4v2v6v1下面介绍一些常用的名词：下面介绍一些常用的名词：下面介绍一些常用的名词：下面介绍一些常用的名词：一一个个图图G或或有有向向图图D中中的的点点数数,记记作作P(G)或或P(D),简简记记作作P,边边数数或或者者弧弧数数,记记作作q(G)或或者者q(D),简简记作记作q。如如果果边边 vi ,vj E,那那么么称称vi,vj 是是边边的的端端点点，或或者者vi,vj是是相相邻邻的的。如如果果一一个个图图G中中，一一条条边边的的两两个个端端点点是是相相同同的的,那那么么称称为为这这条条边边是是环环，如如图图8.48.4中中的的边边 v3,v3 是是环环。如如果果两两个个端

12、端点点之之间间有有两两条条以以上上的的边边，那那么么称称为为它它们们为为多多重重边边，如如图图8.48.4中中的的边边v1,v2,v2,v1。一一个个无无环环，无无多多重重边边的的图图称称为为简单图，简单图，一个无环，有多重边的图称为多重图。一个无环，有多重边的图称为多重图。以以点点v为为端端点点的的边边的的个个数数称称为为点点v的的度度，记记作作d(v),如如图图8484中中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 为为悬挂点，悬挂点

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

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

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

17、链：(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,E2 E1 称称 G2 是是 G1 的部分图或支撑子图；的部分图或支撑子图；导出子图：导出子图：如果如果V V2 2 V V1 1,E2=vi,vj vi,vj V2,称称 G2 是是

18、G1 中由中由V2 导出导出的导出子图。的导出子图。设设 G G1 1=V=V1 1,E,E1 1,G,G2 2=V=V2 2,E,E2 2 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 不考虑方向的链不考虑方向的链,且且 各方向一致各方向一致,则称之为从则称之为从u到到v 的路；的路；初等路初等路:各顶点都不相同的路；各顶点都不相同的路；初

19、等回路初等回路:u=v 的初等路的初等路;连通图：连通图：若不考虑方向若不考虑方向 是无向连通图是无向连通图;强连通图：强连通图：任两点有路任两点有路;v1v2v3v4v58.2 树和最小支撑树树和最小支撑树一、树及其性质一、树及其性质 在在各各种种各各样样的的图图中中，有有一一类类图图是是十十分分简单又非常具有应用价值的图，这就是简单又非常具有应用价值的图，这就是树。树。例例8.38.3 已已知知有有六六个个城城市市，它它们们之之间间 要要架架设设电电话话线线，要要求求任任意意两两个个城城市市均均可可以以互互相相通话，并且电话线的总长度最短。通话，并且电话线的总长度最短。如如果果用用六六个个

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

21、电话线网。图图8.8v6v3v4v2v5v1 定义定义定义定义8.18.18.18.1 一个无圈的连通图叫做一个无圈的连通图叫做树树树树。下面介绍树的一些重要性质：下面介绍树的一些重要性质：下面介绍树的一些重要性质：下面介绍树的一些重要性质：定定定定理理理理8.38.38.38.3 设设图图G=（V，E）是是一一个个树树 P(G)2，那么图那么图G中至少有两个悬挂点。中至少有两个悬挂点。定定理理8.4 8.4 图图G=（V，E）是是一一个个树树的的充充要要条条件件是是G 不含圈，并且有且仅有不含圈，并且有且仅有P-1条边。条边。定定定定理理理理8.58.58.58.5 图图G=（V，E）是是一

22、一个个树树的的充充要要条条件件是是G是连通图，并且有且仅有是连通图，并且有且仅有 p1 条边。条边。定定定定理理理理8.68.68.68.6 图图G是是一一个个树树的的充充分分必必要要条条件件是是任任意意两两个顶点之间有且仅有一条链。个顶点之间有且仅有一条链。从以上定理，不难得出以下从以上定理，不难得出以下结论结论：（1 1）从从一一个个树树中中任任意意去去掉掉一一条条边边，那那么么剩剩下下的的图图不不是是连连通通图图，亦亦即即，在在点点集集合合相相同的图中，树是含边数最少的连通图。同的图中，树是含边数最少的连通图。（2 2）在在树树中中不不相相邻邻的的两两个个点点之之间间加加上上一条边，那么

23、恰好得到一个圈。一条边，那么恰好得到一个圈。二二.支撑树支撑树定义定义8.28.2 设图设图K=(V,EI)是图是图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

24、)-p(G)+1。定理定理8.78.7 一个图一个图G有支撑树的充要条件有支撑树的充要条件是是G 是连通图是连通图。证明：证明：充分性充分性:设图设图G是连通的，若是连通的，若G不不含圈，则按照定义，含圈，则按照定义，G是一个树，从而是一个树，从而G是是自身的一个支撑树。若自身的一个支撑树。若G含圈，则任取含圈，则任取G的的一个圈，从该圈中任意去掉一条边，得到图一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图的一支撑子图G1。若若G1不含圈，则不含圈，则G1是是G的一个支撑树。若的一个支撑树。若G1仍然含圈，则任取仍然含圈，则任取G G1 1的的一个圈，再从圈中任意去掉一条边，得到图一个圈

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

26、的一个支的一个支撑树。撑树。e e4 4e e6 6e e5 5e e3 3e e2 2e 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

27、所示。所示。v2e1e2e5e8v1v3v4v5图图8.128.12三三.最小支撑树问题最小支撑树问题 定义定义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中的权最小，即中的

29、权最小，即S(T*)=minTS(T)，那么称那么称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,v6。任意去掉其中的

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

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

34、（最短 树）树）v1v2v3v4v5v6v7v1v2v3v4v5v6v731245223423122223一一.引言引言 最最短短路路径径问问题题是是图图论论中中十十分分重重要要的的最最优优化化问问题题之之一一，它它作作为为一一个个经经常常被被用用到到的的基基本本工工具具，可可以以解解决决生生产产实实际际中中的的许许多多问问题题，比比如如城城市市中中的的管管道道铺铺设设，线线路路安安排排，工工厂厂布布局局，设设备备更更新新等等等等。也也可可以以用用于于解解决决其其它它的的最优化问题。最优化问题。88.3 3最短路问题最短路问题例例8 86 6 如图如图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算算法法，它它是是在在19591959年年提提

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

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

40、从从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），），d（v1,v4）=1。这是因为从这是因为从v v1 1到达到达v4的任一条路的任一条路P P，假如不是假如不是（v

41、1,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指向其余点的弧。如上所述，从指向其余点的弧。如上所述，从v1出发，出发，分别沿分别沿（v1,v2），（），（v1,v3）到达到达v2，v3，

42、经经过过的路程是的路程是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,v3）=3。这样，又使点这样，又使点v3 3变为具有变为具有P标号的点，标号的点，不断重复以上过程，就可以求出从不断重复以上过程，就可以求出从vs到达任到

43、达任一点一点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)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v963623410231262410

44、1(5,3)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(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)(

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、v1 到到 v8 的最短路的长度为：的最短路的长度为：12从从v1 到到 v8 的最短路线为：的最短路线为：v8v5v2v1步骤：步骤：1、给起点一个永久标号给起点一个永久标号（0，0）。永久标。永久标号用下划线表示；标号中的第一个数表示从号用下划线表示；标号中的第一个数表示从起点到该点的距离；第二个数表示该点的前起点到该点的距离；第二个数表示该点的前面没有点了。面没有点了。2、修改非永久标号点修改非永久标号点 vi 的临时标号为的临时标号为(a,b),其中其中 a 为以为以 vi 为为终点的弧，如果其起终点的弧，如果其起点为永久标号，则求其永久标号的第一个数点为永久标号，则求其永久标号的第一

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

48、v2v3v4v5v6v7v80-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-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56从从

49、v1 到到 v8 的最短路的长度为：的最短路的长度为：6从从v1 到到 v8 的最短路线为：的最短路线为：v8v6v3v18.4 最小费用流问题最小费用流问题一一 引言引言 在在许许多多实实际际的的网网络络系系统统中中都都存存在在着着流流量量和和最最大大流流问问题题。例例如如铁铁路路运运输输系系统统中中的的车车辆辆流流，城城市市给给排排水水系系统统的的水水流流问问题题等等等等。而而网网络络系系统统流流最最大大流流问问题题是是图图与与网网络络流流理理论论中中十十分分重重要要的的最最优优化化问问题题，它它对对于于解解决决生生产产实实际际问题起着十分重要的作用。问题起着十分重要的作用。图图8.198

50、.19是是联联结结某某个个起起始始地地vs和和目目的的地地vt的的交交通通运运输输网网，每每一一条条弧弧vi 旁旁边边的的权权cij表表示示这这段段运运输输线线的的最最大大通通过过能能力力，货货物物经经过过交交通通岗岗从从vs运运送送到到vt.要要求求指指定定一一个个运运输输方方案案，使使得得从从vs到到vt的的货货运运量量最最大大，这这个个问问题题就就是是寻寻求求网网络络系系统统的最大流问题。的最大流问题。问题描述问题描述连通网络连通网络 G(V,A)有有 m 个节点个节点,n条弧条弧,弧弧 eij 上的流量上界为上的流量上界为 cij,求从起始节点求从起始节点 vs 到终点到终点 vt 的