第8章图与网络优化

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外图与网络优化图与网络优化第第 8 8 章章Graph Theory and Network Optimization本章内容本章内容8.1 8.1 图的基本概念图的基本概念8.2 8.2 树树8.3 8.3 最短路问题最短路问题8.4 8.4 网络最大流问题网络最大流问题图论是应用十分广泛的运筹学分支，它已经图论是应用十分广泛的运筹学分支，它已经广泛地应用在物理学、化学、控制论、信息广泛地应用在物理学、化学、控制论、信息论、经营管理、电子计算机等各个领域。论、经营管理、电子计算机等各个领域。绪绪 言言BACD哥尼斯堡七桥问题哥

2、尼斯堡七桥问题18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。河中的小岛有七座桥。河中的小岛C与河岸与河岸A、对岸、对岸B各有两座桥相各有两座桥相连接，而小岛连接，而小岛D与与A、B、C各有一座桥相连接。各有一座桥相连接。当时哥尼斯堡的居民中流传着一道难题：一个人怎样才当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图寻找答案，但是谁也解决不了这个问题。点？大家都试图寻找答案，但是谁也解决不了这个问题。这就是著名的七桥问题。这就是

3、著名的七桥问题。 绪绪 言言1736年，欧拉将这个问题抽象成一笔画问题，即能否从年，欧拉将这个问题抽象成一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的。因为这个图形欧拉在他的论文中证明了这是不可能的。因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。出，这就是古典图论中的第一个著名问题。ABCD一笔画问题一笔画问题绪绪 言言人们为反映一些对象之间关系人们为反映一些对象之间关系时，常会用示意图。

4、时，常会用示意图。例例1 1如右图是我国北京、上海等如右图是我国北京、上海等十个城市间的铁路交通图，反十个城市间的铁路交通图，反映了这十个城市间的铁路分布映了这十个城市间的铁路分布情况。这里用点代表城市，用情况。这里用点代表城市，用点和点之间的连线代表这两个点和点之间的连线代表这两个城市之间的铁路线。城市之间的铁路线。其他示意图的例子其他示意图的例子电话线分布图、煤气管道图、电话线分布图、煤气管道图、航空线图等。航空线图等。铁路交通图铁路交通图8.1 8.1 图的基本概念图的基本概念例例2 有甲、乙、丙、丁、戊五个球队，它们之有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。间比赛

5、的情况用图表示出来。比赛情况图比赛情况图8.1 8.1 图的基本概念图的基本概念l甲队和其他各队都比赛过一次；甲队和其他各队都比赛过一次；l乙队和甲、丙队比赛过；乙队和甲、丙队比赛过；l丙队和甲、乙、丁队比赛过；丙队和甲、乙、丁队比赛过；l队和甲、丙、戊队比赛过；队和甲、丙、戊队比赛过；l戊队和甲、丁队比赛过。戊队和甲、丁队比赛过。l为了反映这个情况，可以用点分为了反映这个情况，可以用点分别代表这五个队，某两个队之间比别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点，间联一条线，这条线不过其他的点，如图所示。如图所示。例例

6、3 某单位储存八种化学药品，其中某些药品是不能某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。用点存放在同一个库房里的。用点 分别分别代表这八种药品，若药品代表这八种药品，若药品vi和药品和药品vj是不能存放在是不能存放在同一个库房的，则在同一个库房的，则在vi和和vj之间联一条线。之间联一条线。678,12345v ,v ,v ,v ,v v ,v ,v768 ,12435vv ,v ,vv ,vv ,v药品存放图药品存放图从图中可以看到至少要有四个库房，从图中可以看到至少要有四个库房，各存放在一个库房里。各存放在一个库房里。8.1 8.1 图的基本概念图的基本概念图：由点及

7、点与点的连线构成，反映了实际生活中某图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系。些对象之间的某些特定关系。点：代表研究的对象；点：代表研究的对象；连线：表示两个对象之间特定的关系。连线：表示两个对象之间特定的关系。图：是反映对象之间关系的一种抽象。图：是反映对象之间关系的一种抽象。一般情况下，图中点的相对位置如何，点与点之间连一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要。线的长短曲直，对反映对象之间的关系并不重要。如例如例2也可以用下图所示的图去反映五个球队的比赛也可以用下图所示的图去反映五个球队的比赛情况，与原图没有本质

8、区别。情况，与原图没有本质区别。 比赛情况图比赛情况图8.1 8.1 图的基本概念图的基本概念关系的对称性和非对称性：关系的对称性和非对称性：几个例子中涉及到的对象之间的几个例子中涉及到的对象之间的“关系关系”具有具有“对称性对称性”，就是说，如果甲与乙有这种关，就是说，如果甲与乙有这种关系，那么同时乙与甲也有这种关系。系，那么同时乙与甲也有这种关系。实际生活中，有许多关系不具有这种对称性。实际生活中，有许多关系不具有这种对称性。 比赛胜负图比赛胜负图8.1 8.1 图的基本概念图的基本概念如例如例2，如果人们关心的是五个，如果人们关心的是五个球队比赛的胜负情况，那么从原球队比赛的胜负情况，那

9、么从原图中就看不出来了。为了反映这图中就看不出来了。为了反映这一类关系，可以用一条带箭头的一类关系，可以用一条带箭头的连线表示。例如，如果球队连线表示。例如，如果球队v1胜胜了球队了球队v2，可以从，可以从v1引一条带箭引一条带箭头的连线到头的连线到v2。图的概念图的概念图是由一些点及点之间的连线图是由一些点及点之间的连线(不带箭头或带箭头不带箭头或带箭头)组成的图形。组成的图形。两点间不带箭头的连线称为边两点间不带箭头的连线称为边, 带箭头的连线称带箭头的连线称为弧。为弧。如果一个图如果一个图G由点及边所构成，则称之为无向图由点及边所构成，则称之为无向图，记为，记为 ，式中，式中V，E分别是

10、分别是G的点集合的点集合和边集合。一条连结点和边集合。一条连结点 的边记为的边记为 (或或 )。如果一个图如果一个图D由点及弧所构成，则称为有向图，由点及弧所构成，则称为有向图，记为记为D=(V,A)，式中，式中V，A分别表示分别表示D的点集合的点集合和弧集合。一条方向是从和弧集合。一条方向是从vi指向指向vj的弧，记为的弧，记为( )。G=(V,E)ijv ,vjiv ,vijv ,vijv ,vV8.1 8.1 图的基本概念图的基本概念无向图的例子无向图的例子 其中其中V1234= v ,v ,v ,vE1234567e ,e ,e ,e ,e ,e ,e11221232343451461

11、3744e = v ,v,e = v ,v,e = v ,v,e = v ,v,e = v ,v , ,e = v ,v,ev ,v无向图无向图8.1 8.1 图的基本概念图的基本概念有向图的例子有向图的例子5671234511V,A1234v ,v ,v ,v ,v ,v ,va ,a ,a ,a ,a ,a其中其中12333434524657468539510561167,121244a = v ,v ,a = v ,v ,a = v ,v ,a = v ,v ,a = v ,v ,a = v ,v ,a = v ,v ,a = v ,v ,av ,va = v ,v ,a = v ,v有

12、向图有向图8.1 8.1 图的基本概念图的基本概念n图图G或或D中的点数记为中的点数记为p(G)或或p(D)，边，边(弧弧)数记为数记为q(G)(q(D)，分别简记为，分别简记为p，q。n无向图无向图G=(V，E)常用的一些名词和记号：常用的一些名词和记号：8.1 8.1 图的基本概念图的基本概念l若边若边e =u，vE，则称，则称u，v是是e的端点，也称的端点，也称u，v是相邻的。称是相邻的。称e是点是点u(及点及点v)的关连边。的关连边。l若图若图G中，某个边中，某个边e的两个端点相同，的两个端点相同，则称则称e是环是环(如图中的如图中的e7)。l若两个点之间有多于一条的边，称这若两个点之

13、间有多于一条的边，称这些边为多重边些边为多重边(如图中的如图中的e1,e2)。n一个无环，无多重边的图称为简单图；一个无环，但一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。允许有多重边的图称为多重图。n以点以点v为端点的边的个数称为为端点的边的个数称为v的次，记为的次，记为dG(v)或或d(v)。n称次为称次为1的点为悬挂点，悬挂点的关连边的点为悬挂点，悬挂点的关连边n称为悬挂边，次为零的点称为孤立点。称为悬挂边，次为零的点称为孤立点。8.1 8.1 图的基本概念图的基本概念如右图中，如右图中，d(v1)=4，d(v2)=3，d(v3)=3，d(v4)=4(环环e7

14、在计算在计算d(v4)时算作两次时算作两次)。定理定理1 图图G=(V，E)中，所有点的次之和是边数中，所有点的次之和是边数的两倍，即的两倍，即vV2vqd()次为奇数的点，称为奇点，否则称为偶点。次为奇数的点，称为奇点，否则称为偶点。定理定理2 任一个图中，奇点的个数为偶数。任一个图中，奇点的个数为偶数。8.1 8.1 图的基本概念图的基本概念 称为一条联结称为一条联结 的链，记为的链，记为 称点称点 为链的中间点。为链的中间点。 给定一个图给定一个图G=(V,E)和一个点、边交错序列和一个点、边交错序列, ，如果满足，如果满足112k 1k 1k()iiiiiiv ,e ,v ,v,e,v

15、ttt 1iiiev ,v (t=1，2，k-1)12k 1k()iiiiv ,v ,v,v2k13iiiv,v,v1kiivv和8.1 8.1 图的基本概念图的基本概念n链链 中中, 若若 , 则称之为一个圈则称之为一个圈,记为记为 。n若链若链 中，点中，点 都是都是不同的，则称之为初等链；不同的，则称之为初等链；n若圈若圈 中，中， 都是不同的都是不同的,则称之为初等圈。则称之为初等圈。n若链若链(圈圈)中含的边均不相同，称为简单链中含的边均不相同，称为简单链(圈圈)。n除非特别交代除非特别交代, 以后说到链以后说到链(圈圈)均指初等链均指初等链(圈圈)。12k 1k()iiiiv ,v

16、 ,v,v1kiivv12k 11()iiiiv ,v ,v,v12k 1k()iiiiv ,v ,v,v12k 1kiiiiv ,v ,v,v12k 11()iiiiv ,v ,v,v12k 1iiiv ,v ,v8.1 8.1 图的基本概念图的基本概念例子例子下图中，下图中， 是一条简单链，但不是是一条简单链，但不是初等链，初等链， 是一条初等链。图中不存在是一条初等链。图中不存在联结联结v1和和v9的链。的链。 是一个初等圈，是一个初等圈， 是是简单圈，但不是初等圈。简单圈，但不是初等圈。67,123453v ,v ,v ,v ,v v ,v ,v67123v ,v ,v ,v ,v11

17、234v ,v ,v ,v ,v763,412354v ,v,v ,v ,v ,v v ,v ,v8.1 8.1 图的基本概念图的基本概念连通图连通图图图G中，若任何两点之间至少有一条链，则称中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。是连通图，否则称为不连通图。若若G是不连通图，它的每个连通的部分称为是不连通图，它的每个连通的部分称为G的一个连通分图的一个连通分图(也简称分图也简称分图)。例如下图是一个不连通图，它有两个连通分图例如下图是一个不连通图，它有两个连通分图。8.1 8.1 图的基本概念图的基本概念支撑子图支撑子图给了一个图给了一个图G=(V，E)，如果，如果

18、G=(V，E)，使，使V=V及及EE ，则称，则称G是是G的一个支撑子图。的一个支撑子图。设设vV(G)，用，用Gv表示从图表示从图G中去掉点中去掉点v及及v的关联边的关联边后得到的一个图。后得到的一个图。例如图例如图G为下图为下图 (a)所示，则所示，则G v3表示为图表示为图 (b)，图，图 (c)是图是图G的一个支撑子图。的一个支撑子图。8.1 8.1 图的基本概念图的基本概念和有向图有关的概念和术语和有向图有关的概念和术语设给定一个有向图，设给定一个有向图，D=(V，A)，从，从D中去掉所中去掉所有弧上的箭头，就得到一个无向图，称之为有弧上的箭头，就得到一个无向图，称之为D的基础图，记

19、之为的基础图，记之为G(D)。给定给定D中的一条弧中的一条弧a=(u，v)，称，称u为为a的始点，的始点，v为为a的终点，称弧的终点，称弧a是从是从u指向指向v的。的。8.1 8.1 图的基本概念图的基本概念和有向图有关的概念和术语和有向图有关的概念和术语设设 是是D中的一个点弧中的一个点弧交错序列，如果这个序列在基础图交错序列，如果这个序列在基础图G(D)中所中所对应的点边序列是一条链，则称这个点弧交对应的点边序列是一条链，则称这个点弧交错序列是错序列是D的一条链。类似定义圈和初等链的一条链。类似定义圈和初等链(圈圈)。如果如果 是是D中的一条中的一条链，并且对链，并且对t=1，2，k-1，

20、均有，均有 ，称之为从，称之为从 的一条路。若路的第一个的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定点和最后一点相同，则称之为回路。类似定义初等路义初等路(回路回路)。1122k 1k 1ki()iiiiiiv ,a ,v ,a,v,a,v1122k 1k 1ki()iiiiiiv ,a ,v ,a,v,a,vttt+1i(,)iiavv1tiivv到8.1 8.1 图的基本概念图的基本概念有向图的例子有向图的例子 是一个回路；是一个回路； 是从是从v1到到v6的路；的路； 是一条链，但不是路。是一条链，但不是路。3568(, , , , , , )32453va vavava

21、v2476(, , , )134v , av , av av28106(, , , )135v , a ,va vav对无向图，链与路对无向图，链与路(圈与回路圈与回路)两个概念是一致的。两个概念是一致的。8.1 8.1 图的基本概念图的基本概念树：一类极其简单然而却很有用的图。树：一类极其简单然而却很有用的图。例例4 已知有五个城市，要在它们之间架设电话线已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话，要求任何两个城市都可以互相通话(允许通允许通过其他城市过其他城市)，并且电话线的根数最少。，并且电话线的根数最少。 8.2 8.2 树树树及其性质树及其性质分析：用五个

22、点分析：用五个点v1，v2，v3，v4，v5代表五个城市，代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个如果在某两个城市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话线网就可以用一个图点之间连一条边，这样一个电话线网就可以用一个图来表示。来表示。分析：为了使任何两个城市都可以通话，这样的图必分析：为了使任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定电话线

23、。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。是不含圈的连通图。8.2 8.2 树树树及其性质树及其性质下图代表了满足要求的一个电话线网。下图代表了满足要求的一个电话线网。定义定义1 1（树的定义）（树的定义） 一个无圈的连通图称为树。一个无圈的连通图称为树。例例5 5 某工厂的组织机构如下所示某工厂的组织机构如下所示工厂组织机构图工厂组织机构图8.2 8.2 树树树及其性质树及其性质如果用图表示，该工厂的组织机构图就是一个树。如果用图表示，该工厂的组织机构图就是一个树。8.2 8.2 树树树及其性质树及其性质定理定理3 设图设图G=(V，E)是一个树，是一个树，p(G)2，则，则

24、G中至中至少有两个悬挂点。少有两个悬挂点。定理定理4 图图G=(V，E)是一个树的充分必要条件是是一个树的充分必要条件是G不不含圈，且恰有含圈，且恰有p1条边。条边。定理定理5 图图G=(V，E)是一个树的充分必要条件是是一个树的充分必要条件是G是是连通图，并且连通图，并且q(G)=p(G) 1定理定理6 图图G是树的充分必要条件是任意两个顶点之是树的充分必要条件是任意两个顶点之间恰有一条链。间恰有一条链。8.2 8.2 树树树及其性质树及其性质由定理由定理6，很容易推出如下结论：，很容易推出如下结论：(1) 从一个树中去掉任意一条边，则余下的图是不连通从一个树中去掉任意一条边，则余下的图是不

25、连通的。由此可知，在点集合相同的所有图中，树是含边的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。例数最少的连通图。例4中所要求的电话线网就是以这中所要求的电话线网就是以这五个城市为点的一个树。五个城市为点的一个树。(2) 在树中不相邻的两个点间添上一条边，则恰好得到在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步地说，如果再从这个圈上任意去掉一一个圈。进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树。条边，可以得到一个树。21v , v5112(v ,v ,v ,v )15v , v8.2 8.2 树树树及其性质树及其性质如例如例4图中，添加图中，添加 ，就

26、得到一个圈就得到一个圈 ，如果从这个圈中去掉一条如果从这个圈中去掉一条边边 ，就得到如右图所，就得到如右图所示的树。示的树。定义定义2 设图设图T=(V，E)是图是图G=(V，E)的支撑子图，如果的支撑子图，如果图图T=(V，E)是一个树，则称是一个树，则称T是是G的一个支撑树。的一个支撑树。例如下图例如下图 (b)是图是图 (a)所示图的一个支撑树。所示图的一个支撑树。8.2 8.2 树树图的支撑树图的支撑树定理定理7 图图G有支撑树的充分必要条件是图有支撑树的充分必要条件是图G是连通的。是连通的。 寻求连通图的支撑树的方法：寻求连通图的支撑树的方法：破圈法破圈法任取一个圈，从圈中去掉一边，

27、对余下的图重复这个步任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支撑树。骤，直到不含圈时为止，即得到一个支撑树。避圈法避圈法在图中任取一条边在图中任取一条边e1，找一条与，找一条与e1不构成圈的边不构成圈的边e2，再，再找一条与找一条与 不构成圈的边不构成圈的边e3，一般，设已有，一般，设已有 ，找一条与找一条与 中的任何一些边不构成圈的边中的任何一些边不构成圈的边ek+1。重复。重复这个过程，直到不能进行为止。这时，由所有取出的这个过程，直到不能进行为止。这时，由所有取出的边所构成的图是一个支撑树。边所构成的图是一个支撑树。12e ,e12ke ,e ,e

28、12ke ,e ,e8.2 8.2 树树图的支撑树图的支撑树例例6 在下图中，用破圈法求出图的一个支撑树。在下图中，用破圈法求出图的一个支撑树。解：取一个圈解：取一个圈 ，从这个圈中去掉边，从这个圈中去掉边 ；在余下的图中，再取一个圈在余下的图中，再取一个圈 ，去掉边，去掉边 ； 在余下的图中，从圈在余下的图中，从圈 中去掉边中去掉边 ； 再从圈再从圈 中去掉边中去掉边 。这时，剩余的图中不含圈，于是得到一个支撑树，如下图中粗这时，剩余的图中不含圈，于是得到一个支撑树，如下图中粗线所示。线所示。1()123v ,v ,v ,v323=ev , v31(,)124v ,v ,v ,v v424=

29、ev , v3(,)345v ,v ,v v653=ev , v531(,)124v ,v ,v ,v ,v v825=ev , v8.2 8.2 树树图的支撑树图的支撑树例例7 在下图中，用避圈法求出一个支撑树。在下图中，用避圈法求出一个支撑树。解解 ：首先任取边：首先任取边e1，因，因e2与与e1不构成圈，所以可以取不构成圈，所以可以取e2，因为，因为e5与与 不构成圈，故可以取不构成圈，故可以取e5(因因e3与与 构成一个构成一个圈圈 ，所以不能取，所以不能取e3)；因；因e6与与 不构成圈，不构成圈，故可取故可取e6；因；因e8与与 不构成圈，故可取不构成圈，故可取e8(注意，因注意，

30、因e7与与 中的中的e5，e6构成圈构成圈 ，故不能取，故不能取e7)。这时由这时由 所构成的图就是一个支撑树所构成的图就是一个支撑树, 如下图所示如下图所示12e e , 12e e , 512e ,e ,e5612e ,e ,e ,e5612e ,e ,e ,e2542()v ,v ,v ,v56812e ,e ,e ,e ,e8.2 8.2 树树图的支撑树图的支撑树定义定义3 给图给图G=(V，E)，对，对G中的每一条边中的每一条边 ，相，相应地有一个数应地有一个数wij，则称这样的图，则称这样的图G为赋权图，为赋权图，wij称称为边为边 上的权。上的权。这里所说的这里所说的“权权”，是

31、指与边有关的数量指标。根据，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示距实际问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等。离、时间、费用等。赋权图在图的理论及其应用方面有重要的地位。赋权赋权图在图的理论及其应用方面有重要的地位。赋权图不仅指出了各点之间的邻接关系，而且同时也表示图不仅指出了各点之间的邻接关系，而且同时也表示了各点之间的数量关系。所以，赋权图被广泛应用于了各点之间的数量关系。所以，赋权图被广泛应用于工程技术及科学生产管理等领域的最优化问题。最小工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。支撑树问

32、题就是赋权图上的最优化问题之一。 ,ijv v ,ijv v8.2 8.2 树树最小支撑树问题最小支撑树问题设有一个连通图设有一个连通图G=(V，E)，每一边，每一边e= ，有一，有一个非负权个非负权 w(e)=wij (wij 0)定义定义4 如果如果T=(V，E)是是G的一个支撑树，称的一个支撑树，称E中所中所有边的权之和为支撑树有边的权之和为支撑树T的权，记为的权，记为w(T)。如果支撑树如果支撑树T* 的权的权w(T*)是是G的所有支撑树的权中最的所有支撑树的权中最小者，则称小者，则称T*是是G的最小支撑树的最小支撑树(简称最小树简称最小树)。最小支撑树问题就是要求给定连通赋权图最小支

33、撑树问题就是要求给定连通赋权图G的最小支的最小支撑树。撑树。 ,ijv v8.2 8.2 树树最小支撑树问题最小支撑树问题1. 1. 避圈法避圈法开始选一条最小权的边，以后每一步中，总从开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选一条与已选边不构成圈的那些未选边中，选一条权最小的。权最小的。算法的具体步骤如下：算法的具体步骤如下：第第1 1步：令步：令i=1i=1， 。第第2 2步：选一条边步：选一条边 ，使，使eiei是使是使 不含圈的不含圈的所有边所有边e( )e( )中权最小的边中权最小的边。令令 ，如果这样的边不，如果这样的边不存在，则存在，则T=(VT=

34、(V，Ei-1)Ei-1)是最小树。是最小树。第第3 3步：把步：把i i换成换成i+1i+1，转入第，转入第2 2步。步。0E( 表表示示空空集集）ii-1eEE( )i-1V,Eei-1eE Eii= i-1EEe8.2 8.2 树树最小支撑树问题最小支撑树问题例例8 8 某工厂内联结六个车间的道路网如下图某工厂内联结六个车间的道路网如下图(a)(a)所示所示。已知每条道路的长，要求沿道路架设联结六个车。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。间的电话线网，使电话线的总长最小。8.2 8.2 树树最小支撑树问题最小支撑树问题2. 破圈法破圈法任取一个圈，

35、从圈中去掉一条权最大的边。在余任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，直至得到一个不含下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。圈的图为止，这时的图便是最小树。例例9 用破圈法求例用破圈法求例8图图(a)所示赋权图的最小支撑树。所示赋权图的最小支撑树。8.2 8.2 树树最小支撑树问题最小支撑树问题练习练习(8.5)已知世界六大城市之间的航线距离已知世界六大城市之间的航线距离(以百英里为单位以百英里为单位)表，表，试在此表确定的交通网络图中找出一个最小树。试在此表确定的交通网络图中找出一个最小树。北京Pe东京T巴黎Pa 墨西哥M 纽约N

36、伦敦L北京/1351776850东京13/60706759巴黎5160/57362墨西哥777057/2055纽约68673620/34伦敦595925534/8.2 8.2 树树最小支撑树问题最小支撑树问题例例10 10 已知如图所示的单行线交通网，每弧旁的数字已知如图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从表示通过这条单行线所需要的费用。现在某人要从v1v1出发，通过这个交通网到出发，通过这个交通网到v8v8去，求使总费用最小的旅去，求使总费用最小的旅行路线。行路线。8.3 8.3 最短路问题最短路问题-问题描述问题描述问题分析：问题分析：从从v1到到v

37、8的旅行路线有很多的旅行路线有很多例如可以从例如可以从v1出发，依次经过出发，依次经过v2，v5，然后到然后到v8；也可以从；也可以从v1出发，依次经出发，依次经过过v3，v4，v6，v7，然后到，然后到v8等。等。不同的路线所需总费用是不同的。不同的路线所需总费用是不同的。用图的语言来描述，从用图的语言来描述，从v1到到v8的一条旅的一条旅行路线就是图中从行路线就是图中从v1到到v8的一条路；的一条路；一条旅行路线的总费用就是相应的从一条旅行路线的总费用就是相应的从v1到到v8的路中所有弧旁数字之和。的路中所有弧旁数字之和。8.3 8.3 最短路问题最短路问题-问题描述问题描述最短路问题描述

38、最短路问题描述给定一个赋权有向图，即给了一个有向图给定一个赋权有向图，即给了一个有向图D=(V，A)，对每一个弧，对每一个弧a=(vi，vj)，相应地赋予了权，相应地赋予了权数。数。又给定又给定D中的两个顶点中的两个顶点vs，vt。设。设P是是D中从中从vs到到vt的一条路，定义路的一条路，定义路P的权是的权是P中所有弧的权之中所有弧的权之和，记为和，记为w(P)。最短路问题就是要在所有从。最短路问题就是要在所有从vs到到vt的路中，求一条权最小的路，即求一条从的路中，求一条权最小的路，即求一条从vs到到vt的路的路P0，使，使式中对式中对D中所有从中所有从vs到到vt的路的路P取最小，称取最

39、小，称P0是从是从vs到到vt的最短路。路的最短路。路P0的权称为从的权称为从vs到到vt的距的距离，记为离，记为d(vs，vt)。显然，。显然，d(vs，vt)与与d(vt，vs)不一定相等。不一定相等。0P(P )min(P)8.3 8.3 最短路问题最短路问题-问题描述问题描述最短路算法最短路算法(wij0)目前公认最好的方法是由目前公认最好的方法是由Dijkstra1959年提出的年提出的，Dijkstra方法的基本思想是从方法的基本思想是从vs出发，逐步出发，逐步向外探寻最短路，不断给新确定的最短路的结向外探寻最短路，不断给新确定的最短路的结点点vj标号标号P(vj)，vi，其中，其

40、中P(vj)为起点为起点vs到到vj的最短距离，的最短距离，vi为该最短路上的前一节点。为该最短路上的前一节点。具体步骤是：具体步骤是：8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)(1) 给起点给起点v1标号标号0, v1(3) 考虑所有这样的弧（考虑所有这样的弧（vi , vj），其中），其中vi Si ， vj Si ，挑选，挑选其中与起点其中与起点vs距离最短（距离最短（minP(vi) +wij）的）的vj，对，对vj进行标号。进行标号。(2) 把顶点集把顶点集V分成已具有分成已具有P标号的点集（标号的点集（Si）和未标号点集）和未标号点集以例以例1

41、0为例说明该方法的基本思想为例说明该方法的基本思想:求从求从v1到到v8的最短的最短路路8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)1, v10, v110v2v1v3v4v5v6v7v9v816322226613310441, v10, v110v2v1v3v4v5v6v7v9v816322226613310443, v18.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)0, v11, v13, v15, v310v2v1v3v4v5v6v7v9v816322226613310448.3 8.3 最短路问题最短路问题最短路算法

42、最短路算法(wij0)(wij0)0, v11, v13, v15, v36, v210v2v1v3v4v5v6v7v9v816322226613310448.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)0, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v9v816322226613310448.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)0, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v9v816322226613310448.3

43、8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)0, v11, v1算法终止算法终止,v8已标号已标号12, v5，则，则12即为即为v1 v8的的最短距离，反向追踪可求出最短路！最短距离，反向追踪可求出最短路！3, v15, v36, v29, v510, v512, v510v2v1v3v4v5v6v7v9v816322226613310448.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)0, v11, v13, v15, v36, v29, v510, v512, v5v1到到v8的最短路为：的最短路为：v1 v3 v2 v5 v8

44、，最短距离，最短距离为为1210v2v1v3v4v5v6v7v9v81632222661331044反向追踪反向追踪8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)练习练习(8.7):求从求从v1到到v9的最短路的最短路0, v14, v13, v15, v26, v29, v77, v4/ v68.5, v66, v2v2v1v5v4v3v6v8v7v943232.5335234218.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)赋权无向图的最短路问题赋权无向图的最短路问题对于赋权无向图对于赋权无向图G=(V，E)，边，边vi，

45、vj既可以既可以从从vi到达到达vj，也可以沿，也可以沿vj到达到达vi，所以边，所以边vi，vj 可以看作是两条弧可以看作是两条弧(vi，vj)及及(vj，vi)，它们具，它们具有相同的权。有相同的权。这样对赋权无向图的最短路问题，只要把这样对赋权无向图的最短路问题，只要把Dijkstra方法中的方法中的“考查每个使考查每个使(vk，vj)A且且vj Si的点的点vj”改为改为“考查每个使考查每个使vk，vj E且且vj Si的点的点vj”，同样地可以求出从，同样地可以求出从vs到各点的最短路。到各点的最短路。8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)例

46、例11 用用Dijkstra方法求赋权无向图的最短路问题方法求赋权无向图的最短路问题求从求从v1到到v8的最短路。的最短路。8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)10v2v1v3v4v5v6v7v9v816322226613344从从v1到到v8的最短链为的最短链为(v1，v3，v2，v5，v9，v8), 总权为总权为118.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)0, v11, v13, v15, v36, v29, v510, v511, v910v2v1v3v4v5v6v7v9v8163222266133448

47、, v5解：解：v1v2v3v4v5v6v7225355715713练习：对下列无向图求最短路（从练习：对下列无向图求最短路（从v1v1到到v7 v7 ）8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wij0)(wij0)当权可以为负时，例如求下图从当权可以为负时，例如求下图从v1到到v2的最短路。的最短路。12-3v1v2v3Dijkstra算法失效了！最短路算法最短路算法(wijN)8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wijN)(wijN)当赋权有向图中存在具负权弧时，求最短路的方法。当赋权有向图中存在具负权弧时，求最短路的方法。设从任一点设从任一点vi到

48、任一个点到任一个点vj都有一条弧。如果在都有一条弧。如果在D中中， ，则添加弧，则添加弧(vi，vj)，令，令wij=+。显然，从显然，从vs到到vj的最短路总是从的最短路总是从vs出发，沿着一条路出发，沿着一条路到某个点到某个点vi，再沿，再沿(vi，vj)到到vj的的(这里这里vi可以是可以是vs本本身身)，而从，而从vs到到vi的这条路必定是从的这条路必定是从vs到到vi的最短路的最短路，所以，所以d(vs，vj)必满足如下方程：必满足如下方程： ij( ,)Av v id( ,)mind()sjsii jv vv ,v8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wijN)

49、(wijN)最短路算法最短路算法(wijN)为了求得这个方程的解，可用如下递推公式：为了求得这个方程的解，可用如下递推公式：开始时，令开始时，令 , (j=1，2，p)对对t=2,3, 若进行到某一步第若进行到某一步第k步时，有步时，有则则 即为即为vs到各点的最短路的权到各点的最短路的权(1)d ()sjs jv ,v(t)(t 1)id()mind()sjsiijv ,vv ,v(k)(k 1)d()d()sjsjv ,vv ,v(k )d()sjj=1,2,pv ,v8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wijN)(wijN)例例12 求下图所示赋权有向图中从求下图所

50、示赋权有向图中从v1到各点的最短路到各点的最短路。v1v2v3v4v5v6v7v86-1-283-3-5-1212-111-3-578.3 8.3 最短路问题最短路问题最短路算法最短路算法(wijN)(wijN)(表中未写数字的空格内是表中未写数字的空格内是+)660-5-3v8-5-550-1v7-1-1-17101v6-3-310-1v5-7-7-73208v4-2-2-2-21-50-3v3-5-5-5-1206v200003-2-10v1t=4t=3t=2t=1v8v7v6v5v4v3v2v1wij 1,sjijdv vw 1,min,1,2,.,ttsjsiijidvvdvvwjp

51、1,tjdv v8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wijN)(wijN)v1v2v3v4v5v6v7v86-1-283-3-5-1212-111-3-570-5-2-7-5-1-368.3 8.3 最短路问题最短路问题最短路算法最短路算法(wijN)(wijN)练习：求下面赋权有向图中从练习：求下面赋权有向图中从v1到各点的最短路到各点的最短路8.3 8.3 最短路问题最短路问题最短路算法最短路算法(wijN)(wijN)流流(Flow)就是将目标由一个地点运送到另一个地点。就是将目标由一个地点运送到另一个地点。公路系统中的交通流公路系统中的交通流控制系统中的信息流控制

52、系统中的信息流金融系统中的现金流金融系统中的现金流它们的共同问题是：希望经过输送系统，将目标从一它们的共同问题是：希望经过输送系统，将目标从一个地点运送到另一个地点的运输量最大。个地点运送到另一个地点的运输量最大。8.4 8.4 网络最大流问题网络最大流问题网络中存在流量限制时，求解一条线路使得从起点与网络中存在流量限制时，求解一条线路使得从起点与终点之间可通过的流量最大。终点之间可通过的流量最大。例如上图为例如上图为V1到到V6的一交通网，权表示相应运输线的的一交通网，权表示相应运输线的最大通过能力，制定方案使从最大通过能力，制定方案使从V1运到运到V6的产品数量最的产品数量最多。多。v2v

53、2v1v1v3v3v4v4v5v5v6v68 810104 417175 55 53 311116 63 38.4 8.4 网络最大流问题网络最大流问题-问题的提出问题的提出设有网络设有网络D=(V, A, C), 其中其中C=cij, cij为弧为弧(vi,vj)上的容上的容量。量。现在现在D上要通过一个流上要通过一个流f=fij， fij为弧为弧(vi,vj)上的流量。上的流量。问题：如何安排问题：如何安排fij，可使网络，可使网络D上的总流量最大？上的总流量最大？v2v2v1v1v3v3v4v4v5v5v6v68 810104 417175 55 53 311116 63 35 53 3

54、1 12 22 21 13 33 36 62 28.4 8.4 网络最大流问题网络最大流问题-问题的提出问题的提出求网络最大流，即求可行流求网络最大流，即求可行流v(f)的最大值的最大值 v2v2VsVsv3v3v4v4v5v5VtVt8 810104 417175 55 53 311116 63 35 53 31 12 22 21 13 33 36 62 2可行流可行流-在网络上满足下列三个条件的一组流：在网络上满足下列三个条件的一组流：容量限制条件容量限制条件: 对所有的弧有对所有的弧有(2) 中间点平衡条件中间点平衡条件(流出量等于流入量流出量等于流入量): 即对每个即对每个i (is,

55、t)有有(3) 以以v(f)表示网络中从表示网络中从Vs到到Vt的流量的流量);,(),(0jijivvcvvf( ,)(,)ijjif v vf v vtsitifvsifvvvfvvfijji,0)()(),(),(8.4 8.4 网络最大流问题网络最大流问题基本概念和定理基本概念和定理1. 弧按流量分为弧按流量分为饱和弧饱和弧 fij=cij非饱和弧非饱和弧 fijcij零流弧零流弧 fij=0非零流弧非零流弧 fij0v2vsv3v4v5vt810417553116353122133628.4 8.4 网络最大流问题网络最大流问题基本概念和定理基本概念和定理2. 增广链增广链v2vsv

56、3v4v5vt81041755311635312213362如果在网络的起点和终点间能找出一条链如果在网络的起点和终点间能找出一条链,在这条链上：在这条链上：所有指向为所有指向为st的弧的弧(称为前向弧称为前向弧,记为记为 )都是非饱和弧都是非饱和弧(即即f0)这样的链称为增广链这样的链称为增广链.8.4 8.4 网络最大流问题网络最大流问题基本概念和定理基本概念和定理练习：练习：判断增广链判断增广链v2v1v3v4v5v681041755311635312213361v2v1v3v4v5v6810417553116353320153628.4 8.4 网络最大流问题网络最大流问题基本概念和定

57、理基本概念和定理把把V分成两部分分成两部分VA和和VB，且，且vs VA、 vt VB，使，使vs到到vt的流中断的一个弧集合称为截集。的流中断的一个弧集合称为截集。截集上的容量和称为截量，记为截集上的容量和称为截量，记为C(VA,VB) 。截集为：截集为：(vs,v2), (v1,v2), (v1,v3), (v1,v4)；截量为：截量为： C(VA,VB) =8+4+5+3=20例例 若若VA=vs,v13. 截集与截量截集与截量v1vsv2v3v4vt810417553116353122133628.4 8.4 网络最大流问题网络最大流问题基本概念和定理基本概念和定理在一网络在一网络D中，从中，从 到到 的最大流的流量的最大流的流量等于分离等于分离 和和 的最小截集的容量。的最小截集的容量。svtvsvtv4.最大流量最小截集定理最大流量最小截集定理8.4 8.4 网络最大流问题网络最大流问题基本概念和定理基本概念和定理例例. 如图所示的网络中，弧旁数字为容量如图所示的网络中，弧旁数字为容量cij （1）确定所有的截集；）确定所有的截集；（2）根据最大流量最小截集定理求网络最大流；）根据最大流量最小截集定理求网络最大流；v1vsv2v3vt24313528.4 8.4 网络最大流问题网络最大流问题基本概念和定理基本概念和定理v