运筹学 图与网络优化精选文档.ppt

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

1、运筹学 图与网络优化本讲稿第一页，共一百三十一页图论概述图论概述v图论图论(Graph Theory)是运筹学中的一个重要分支，主要是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产工艺如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。流程以及军事后勤保障系统等的问题常用图论模型来描述。本讲稿第二页，共一百三十一页网络规划概述网络规划概述v网络规划网络规划(Network Programming)是图论与线性是图论与线性规

2、划的交叉学科，具有广泛的应用背景，比如，最短规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。路问题、最小树问题、最大流问题、最优匹配问题等。本讲稿第三页，共一百三十一页七桥问题七桥问题七桥问题图形七桥问题图形本讲稿第四页，共一百三十一页原原 理理 及及 方方 法法 七桥问题是图论中的著名问题。七桥问题是图论中的著名问题。17361736年，年，EulerEuler巧妙巧妙地将此问题化为图的不重复一笔画问题，并证明了地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连该问题不存在肯定回答。原因在于该图形有顶点连接奇

3、数条边。接奇数条边。本讲稿第五页，共一百三十一页10.1 图的基本概念图的基本概念一个图一个图(Graph)定义为三元有序组定义为三元有序组V(G)是图的顶点集合是图的顶点集合E(G)是是图图的边集合的边集合记记 是关联函数是关联函数本讲稿第六页，共一百三十一页图的端点图的端点设设G是一个图是一个图(Graph)G=(V(G),E(G)，则称则称e连接连接u和和v，称，称u和和v是是e的端点。的端点。若若称端点称端点u，v与边与边e是是关联的关联的，称两个顶点称两个顶点u，v是是邻接邻接的。的。本讲稿第七页，共一百三十一页设设G是一个图，是一个图，图10G的几何实现的几何实现本讲稿第八页，共一

4、百三十一页图的几何实现图的几何实现 一个图可用一个几何图形表示一个图可用一个几何图形表示,称为图的几称为图的几何实现，其中何实现，其中每个顶点用点表示，每个顶点用点表示，每条边用连接端点的线表示。每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质。图的几何实现有助与我们直观的了解图的许多性质。本讲稿第九页，共一百三十一页说明说明一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系边与顶点之间保持的相互关系。我们常常把一

5、个图的图形当作这个抽象图自身我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点，图形的线为边。并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。边、多重边、环、路、圈、树等。本讲稿第十页，共一百三十一页几何实现图例几何实现图例在一个图的几何实现中，两条边的交点可能不是图的顶点。例在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图如下图 中，它共有中，它共有4个顶点，个顶点，6条边；而条边；而e 3 与与e 4 的交点不是这个的交点不是这个图的顶点。图的顶

6、点。本讲稿第十一页，共一百三十一页平面图平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。顶点相交。下图就是一个平面图。本讲稿第十二页，共一百三十一页基本概念基本概念端点重合为一点的边称为端点重合为一点的边称为环环。连接同一对顶点的多条边称为连接同一对顶点的多条边称为多重边多重边。在右图中，在右图中，e5 是一个环，是一个环，e1 与与e2 是多重边，是多重边，v1和和e1,e2,e3是关联的，是关联的，v1与与v2,v3是邻接的。是邻接的。本讲稿第十三页，共一百三十一页邻接矩阵邻接矩阵设设G是一个图，是

7、一个图，G=(V(G),E(G)，定义图，定义图G的邻接矩阵的邻接矩阵A(G)=(aij)为为mm矩阵矩阵,aij是顶点是顶点vi与边与边vj相邻接的边数。相邻接的边数。其中其中本讲稿第十四页，共一百三十一页关联矩阵关联矩阵设设G是一个图，是一个图，G=(V(G),E(G)定义图定义图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；矩阵；其中其中mij是顶点是顶点vi与边与边ej相关联的次数，相关联的次数，取值可能为取值可能为0、1、2。本讲稿第十五页，共一百三十一页注注v图的邻接矩阵比它的关联矩阵小的多，因而图常常以图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机

8、中。其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。关联矩阵和邻接矩阵统称图的矩阵表示。本讲稿第十六页，共一百三十一页顶点的度顶点的度设设G是一个图，是一个图，G=(V(G),E(G)，定义图定义图G的顶点的顶点v的度的度为与顶点为与顶点v相关联的边数，记作相关联的边数，记作d(v)例例称度为奇数的顶点为奇点；称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。称度为偶数的顶点为偶点。本讲稿第十七页，共一百三十一页例例22222224+3+3+4=14=27本讲稿第十八页，共一百三十一页关联矩阵性质关联矩阵性质图图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；则每行元矩阵；

9、则每行元素之和等于相应顶点的度；每列元素之和等于素之和等于相应顶点的度；每列元素之和等于2。因此，因此，图图G的关联矩阵的关联矩阵M所有元素之和既等于所有顶所有元素之和既等于所有顶点的度之和，又等于边数的点的度之和，又等于边数的2倍。倍。定理设定理设G是一个图，则是一个图，则本讲稿第十九页，共一百三十一页推论推论图中奇点的数目为偶数。图中奇点的数目为偶数。证明证明记记本讲稿第二十页，共一百三十一页简单图简单图一个图称为一个图称为简单图简单图，如果它既没有环也没有多重边。，如果它既没有环也没有多重边。下图是简单图。下图是简单图。本书只限于讨论有限简单图，本书只限于讨论有限简单图，即顶点集与边集都

10、是有限集的图。即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图；边集是空集的图称为边集是空集的图称为空图空图。本讲稿第二十一页，共一百三十一页同构同构称称G和和H是同构的，记为是同构的，记为，使得使得给定两个图给定两个图如果存在两个一一对应如果存在两个一一对应本讲稿第二十二页，共一百三十一页同构图例同构图例v图图G与图与图H是同构的。是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4本讲稿第二十三页，共一百三十一页完全图Knv完全图是每一对不同顶点都恰有一边的简单图；完全图是每

11、一对不同顶点都恰有一边的简单图；v具有具有n个顶点的完全图记为个顶点的完全图记为Kn.K5本讲稿第二十四页，共一百三十一页二分图二分图v二分图是一个简单图，其顶点集合可分划成两个子集二分图是一个简单图，其顶点集合可分划成两个子集X与与Y，使得每条边的一个端点在使得每条边的一个端点在X，另一个端点在，另一个端点在Y;(X,Y)也称为图的二分也称为图的二分划。划。x1x2x3y1y2y3本讲稿第二十五页，共一百三十一页完全二分图完全二分图v完全二分图是具有二分划完全二分图是具有二分划(X,Y)的二分图，并且的二分图，并且X的每个的每个顶点与顶点与Y的每个顶点都相连；记为的每个顶点都相连；记为Km,

12、n，v其中其中K3,3本讲稿第二十六页，共一百三十一页特殊图例特殊图例K5K 3,3都是极小的非平面图都是极小的非平面图本讲稿第二十七页，共一百三十一页子图子图称图称图H是图是图G的子图，的子图，图图G及其基本图及其基本图称称H是是G的的支撑子图支撑子图，如果如果称称H是是G的真子图的真子图，若若如果如果表示关联函数表示关联函数记为记为在在H的限制。的限制。本讲稿第二十八页，共一百三十一页顶点导出子图顶点导出子图设设W是图是图G的一个非空顶点子集的一个非空顶点子集,以以W为顶点集，以二端点为顶点集，以二端点均在均在W中的边的全体为边集的子图称为由中的边的全体为边集的子图称为由W导出的导出的G的

13、子的子图，简称导出子图，记为图，简称导出子图，记为GW。导出子图导出子图GV-w记为记为G-W，即，即 它是从它是从G中删除中删除W中顶点以及与这些顶点相关联的边所得中顶点以及与这些顶点相关联的边所得到的子图。到的子图。如果如果W仅含一个顶点仅含一个顶点v，则把，则把 简记为。简记为。本讲稿第二十九页，共一百三十一页边导出子图边导出子图设设F是图是图G的非空边子集，以的非空边子集，以F为边集，以为边集，以F中边的端点全体为顶点中边的端点全体为顶点集所构成的子图称为由集所构成的子图称为由F导出的导出的G的子图，简称的子图，简称G的边导出子图。的边导出子图。记为记为GF。记记G-F表示以表示以E(

14、G)F为边集的为边集的G的支撑子图，它是从的支撑子图，它是从G中删除中删除F中中的边所得到的子图。的边所得到的子图。如如F=e，则记。，则记。本讲稿第三十页，共一百三十一页子图图例子图图例v1v2v3v4v5e1e3e2Gv1v2v3v4v5G的支撑子图的支撑子图G-e1,e 2,e 3本讲稿第三十一页，共一百三十一页子图图例子图图例2v2v3v4e2G-v 1,v 5 v1v2v5Gv 1,v 2,v 5 v1v2v3v4e1e3e2G e1,e 2,e 3v1v2v3v4v5e1e3e2G本讲稿第三十二页，共一百三十一页途径途径v顶点顶点vk叫叫W的终点，的终点，v顶点顶点v0 称为称为W

15、的起点，的起点，v顶点顶点vi 叫叫W的内部顶点，的内部顶点，v整数整数k称为称为W的长度。的长度。v在简单图中，径可由顶点序列表示。在简单图中，径可由顶点序列表示。图图G的一个有限的点边交错序列称为从的一个有限的点边交错序列称为从v0到到vk的途径。的途径。其中其中vi与与vi+1是边是边ei的顶点的顶点;本讲稿第三十三页，共一百三十一页路、路、链v如果径如果径W的边不相同，则称的边不相同，则称W为一条链，为一条链，如果如果W顶点互不相同，则称顶点互不相同，则称W是一条路。是一条路。链长是链长是W中边的个数中边的个数k。记路长记路长uvwxyabdefghv路：路：xcwhyeuavv链：链

16、：wcxdyhwbvgyc本讲稿第三十四页，共一百三十一页圈圈(回路回路)v如果途径如果途径W的起点和终点相同且有正长度，则称它是一个的起点和终点相同且有正长度，则称它是一个闭途径；闭途径；v如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。v称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。圈：uavbwhyeuuvwxyabdefghc本讲稿第三十五页，共一百三十一页定理定理v一个图是二分图当且仅当图中不存在奇圈。一个图是二分图当且仅当图中不存在奇圈。本讲稿第三十六页，共一百三十

17、一页Euler圈圈vEuler圈是指过所有边一次且恰好一次的圈是指过所有边一次且恰好一次的闭途径闭途径。vEuler链是指过所有边一次且恰好一次的链。链是指过所有边一次且恰好一次的链。Euler链链:ydxcwheuavfygvbwuvwxyabdefghc本讲稿第三十七页，共一百三十一页图例图例v下例给出了一个图的径，链和路。下例给出了一个图的径，链和路。v径：径：uavfyfvgyhwbvv链：链：wcxdyhwbvgyv路：路：xcwhyeuavv圈：圈：uavbwhyeuvEuler链链:ydxcwheuavfygvbwuvwxyabdefghc本讲稿第三十八页，共一百三十一页Eule

18、r型型定理定理v定理定理2设设G是连通圈，则是连通圈，则G是是Euler型的充要条件型的充要条件是是G没有奇次数的顶点。没有奇次数的顶点。v推论推论1设设G是一个连通图，则是一个连通图，则G有有Euler链当且仅链当且仅当当G最多有两个奇数次数的顶点。最多有两个奇数次数的顶点。本讲稿第三十九页，共一百三十一页连通性连通性v图图G称为连通的，如果在称为连通的，如果在G的任意两个顶点的任意两个顶点u和和v中中存在一条存在一条(u,v)路。路。v不连通图至少有两个连通分支。不连通图至少有两个连通分支。两点顶点两点顶点u和和v等价当且仅当等价当且仅当u和和v中存在一条中存在一条(u,v)路。路。表示表

19、示G的连通分支数。的连通分支数。本讲稿第四十页，共一百三十一页10.2 树树树（树（tree）是一个不包含圈的简单连通图。）是一个不包含圈的简单连通图。具有具有k个连通分支的不包含圈的图称为个连通分支的不包含圈的图称为k-树，或森林。树，或森林。本讲稿第四十一页，共一百三十一页v下图列出了具有六个顶点的不同构的树。从中可以看出，下图列出了具有六个顶点的不同构的树。从中可以看出，v图中的每棵树都只有图中的每棵树都只有5条边，并且至少有条边，并且至少有2个顶点的次数是个顶点的次数是1。本讲稿第四十二页，共一百三十一页性质性质1设设G是一棵树，则：是一棵树，则：G中任意两点均有唯一的路连接。中任意两

20、点均有唯一的路连接。2 G的边数等于顶点数减的边数等于顶点数减1，即，即3 若若G不是平凡图，则不是平凡图，则G至少有两个次数为至少有两个次数为1的顶点。的顶点。本讲稿第四十三页，共一百三十一页定理定理1设设G是一个简单图，是一个简单图，则下列六个命题是等价的。，则下列六个命题是等价的。vG是一棵树。是一棵树。v无圈且无圈且m=n-1。vG连通且连通且m=n-1。vG连通并且每条边都是割边。连通并且每条边都是割边。vG中任意两点都有唯一的路相连。中任意两点都有唯一的路相连。vG无圈，但在任意一对不相邻的顶点之间加连一条边，无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。则构成

21、唯一的一个圈。本讲稿第四十四页，共一百三十一页支撑树支撑树v图图G的支撑树是的支撑树是G的支撑子图，并且是一棵树。的支撑子图，并且是一棵树。v每个连通图都有支撑树每个连通图都有支撑树v支撑树也称为连通图的极小连通支撑子图。支撑树也称为连通图的极小连通支撑子图。v很显然，一个连通图只要本身不是一棵树，它的支撑树就不止很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。一个。本讲稿第四十五页，共一百三十一页定理定理v定理定理4设设T1 和和T2 是是G的两个支撑树，令的两个支撑树，令 则则T1 经过经过k次迭代后可得到次迭代后可得到T2。v定理定理2设设G是一个连通图，是一个连通图，T是是

22、G的一棵支撑树，的一棵支撑树，e是是G的一条不的一条不属于属于T的边，则的边，则T+e含有含有G的唯一圈。的唯一圈。v定理定理3设设T是连通图是连通图G的一棵支撑树，的一棵支撑树，e是是T的任意一条边，则：的任意一条边，则：T（1）不包含不包含G的割集的割集（2）包含）包含G的唯一的割集。的唯一的割集。本讲稿第四十六页，共一百三十一页最小树最小树定理定理5设设T是是G的一个支撑树，则的一个支撑树，则T是是G的最小树的充分的最小树的充分必要条件为对任意边必要条件为对任意边设设G是一个赋权图，是一个赋权图，T为为G的一个支撑树。定义的一个支撑树。定义T的权为：的权为：G中权最小的支撑树称为中权最小

23、的支撑树称为G的最小树。的最小树。本讲稿第四十七页，共一百三十一页定理定理6v设设T是是G的支撑树，则的支撑树，则T是是G的最小树的充分必要条件为对任意边的最小树的充分必要条件为对任意边 ，其中其中 为为G的唯一割集。的唯一割集。本讲稿第四十八页，共一百三十一页最小树算法最小树算法-1-贪心算法贪心算法Kruskal在在1965年提出一种求最小树的所谓贪心算法。年提出一种求最小树的所谓贪心算法。算法步骤如下算法步骤如下vStep0 把边按权的大小从小到大排列得：把边按权的大小从小到大排列得：置置Step1 若若 ，则停，此时，则停，此时GS即为所求的最小树；即为所求的最小树；否则，转向否则，转

24、向Step2。Step2 如果如果 GS+e j不构成回路，则令不构成回路，则令转向转向Step1；否则，令；否则，令j=j+1转向转向Step2。本讲稿第四十九页，共一百三十一页算例算例图图7-18展示了利用展示了利用Kruskal算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-18本讲稿第五十页，共一百三十一页v1v2v4v5v312244342v1v2v4v5v312244342图7-18-1本讲稿第五十一页，共一百三十一页评注评注Kruskal算法的总计算量为算法的总计算量为 ，有效性不太好。，有效性不太好

25、。求求最最小小树树的的一一个个好好的的算算法法是是Dijkstra于于1959年年提提出出的的，算算法法的的实实质质是是在图的在图的 个独立割集中，取每个割集的一条极小边来构成最小树。个独立割集中，取每个割集的一条极小边来构成最小树。本讲稿第五十二页，共一百三十一页最小树算法最小树算法-2-Dijkstra算法算法Step0 置置Step1 取取置置Step2 若若 ，则停止；，则停止；否则，置否则，置 ，返回，返回Step1本讲稿第五十三页，共一百三十一页算例算例2图图7-19展示了利用展示了利用Dijkstra算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v3122443

26、42v1v2v4v5v312244342图图7-19本讲稿第五十四页，共一百三十一页利用利用Dijkstra算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-19-1本讲稿第五十五页，共一百三十一页v破圈法是破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。顶点数和边数比较大时，可以在各个局部进行。Step1 若若G不含圈，则停止；否则在不含圈，则停止；否则在G中找一个圈中找一个圈C，取圈，取圈C的一条边的一条

27、边e ，满足，满足最小树算法最小树算法-3-破圈法破圈法Step2：置：置 G=G-e，返回，返回Step1。利用破圈法求图利用破圈法求图7-19的最小树的过程如图的最小树的过程如图7-20所示。所示。本讲稿第五十六页，共一百三十一页算例算例3图图7-20展示了利用破圈法求最小树的迭代过程。展示了利用破圈法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-20本讲稿第五十七页，共一百三十一页v1v2v4v5v312244342v1v2v4v5v312244342图图7-20-1本讲稿第五十八页，共一百三十一页评注评注上上述述算算法法都都可可以以

28、在在图图上上进进行行。为为了了便便于于计计算算机机计计算算，下下面面介介绍绍Dijkstra的表上算法。的表上算法。给给定定一一个个赋赋权权图图G，可可以以相相应应地地定定义义一一个个邻邻接接矩矩阵阵A=(wij)，其其中中wij是连接顶点是连接顶点vi和和vj的权的权;若若vi vj不是不是G的边，则令的边，则令 wij 等于无穷大。等于无穷大。本讲稿第五十九页，共一百三十一页Step0：画画掉掉第第一一列列的的所所有有元元素素（例例如如打打上上 ），并并在在第第一一行行的的每每个元素下面画一横线。个元素下面画一横线。Step1：在在画画横横线线的的元元素素中中找找一一个个最最小小的的w i

29、j，用用圆圆圈圈起起来来，把把第第j列列其其他元素画掉，并把第他元素画掉，并把第j行没有画掉的元素画上横线。行没有画掉的元素画上横线。Step2：如如果果还还有有没没有有圈圈起起来来和和没没有有画画掉掉的的元元素素，则则返返回回Step1；否否则则，结结束束。这这时时圈圈起起来来的的元元素素代代表表最最小小树树的的边边，所所有有圈圈起起来来的元素之和就是最小树的权。的元素之和就是最小树的权。最小树算法最小树算法-4-表上作业法表上作业法本讲稿第六十页，共一百三十一页算例算例用表上作业法求图用表上作业法求图7-19的最小树的过程为：的最小树的过程为：最小对的权最小对的权=1+2+3+2=8。v1

30、v2v4v5v312244342本讲稿第六十一页，共一百三十一页本讲稿第六十二页，共一百三十一页最小连接问题最小连接问题作作为为最最小小树树的的应应用用问问题题之之一一是是所所谓谓的的连连接接问问题题：欲欲建建造造一一个个连连接接若若干干城城镇镇（矿矿区区或或工工业业区区）的的铁铁路路网网，给给定定城城镇镇i和和j之之间间直直通通线线路的造价为路的造价为cij，试设计一个总造价最小的铁路运输图。，试设计一个总造价最小的铁路运输图。v把每个城镇看作是具有权把每个城镇看作是具有权cij的赋权图的赋权图G的一个顶点。显然连接问的一个顶点。显然连接问题可以表述成：在赋权图题可以表述成：在赋权图G中，求

31、出具有最小权的支撑树。中，求出具有最小权的支撑树。本讲稿第六十三页，共一百三十一页10.3 最短路问题最短路问题vDijkstra算法算法v求任意两点的最短路算法求任意两点的最短路算法-Floyd算法算法v求带负权网络图的最短路的算法求带负权网络图的最短路的算法v用线性规划求最短路用线性规划求最短路本讲稿第六十四页，共一百三十一页赋权图赋权图v给定赋权图的一个子图给定赋权图的一个子图H，定义，定义H的权为的权为H的所有边权的总和。的所有边权的总和。v对图对图G的每条边的每条边e，赋予一实数，赋予一实数(e)，称为边，称为边e的权，可得一的权，可得一赋权图。赋权图。SDBTCEA71224473

32、1555本讲稿第六十五页，共一百三十一页v赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。v在一个赋权图在一个赋权图G上，给定两个顶点上，给定两个顶点u和和 v，所谓，所谓u和和 v最短最短 路是指所有连接顶点路是指所有连接顶点u和和 v 的路中路长最短的路；的路中路长最短的路；vu和和v最短路的路长也称为最短路的路长也称为u和和 v的距离。的距离。SDBTCEA712244731555v如何求从如何求从u到到v的的最短路的长？最短路的长？本讲稿第六十六页，共一百三十一页vDijkstra算法的基本思想：算法的基本思想：(1)u0u1P设设S是是V的真子集，的真子集，如果如果 是从是从

33、u0 到的最短路，到的最短路，则则，并且，并且P的的 段是最短的段是最短的 路，所以路，所以本讲稿第六十七页，共一百三十一页算法标号算法标号v令令dij表示连接顶点表示连接顶点vi与顶点与顶点vj边上的权，即边上的权，即(1)公式（公式（1）是）是Dijkstra算法的基础。算法的基础。本讲稿第六十八页，共一百三十一页定义结点定义结点vj 的标号为的标号为始点的标号为始点的标号为0,-,表明这个点前面没有点。表明这个点前面没有点。结点结点vj 的标号分为两种：的标号分为两种：临时性标号和永久性标号临时性标号和永久性标号。如果找到。如果找到一条更短的路，临时性标号即被修改，如果找不到一条更短的路

34、，一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。临时性标号即被改为永久性标号。本讲稿第六十九页，共一百三十一页vStep0 令令始点的标号为始点的标号为0,-.令令i=1 vStep i(a)对于由结点对于由结点i可达的还没有永久性标号的结点可达的还没有永久性标号的结点j，计算，计算其其临时性标号临时性标号li+dij,i（dij0）.如果如果 j 已经通过另一个结点已经通过另一个结点k标号标号为为 lj,k 且且 li+dijlj,则用则用li+dij,i取代取代 lj,k。(b)如果所有的结点都是永久性标号，停止。否则选择最小的临时性如果所有的结点

35、都是永久性标号，停止。否则选择最小的临时性标号标号 lr,s。令令 i=r，返回返回Step i.本讲稿第七十页，共一百三十一页计算实例计算实例求连接求连接S、T的最短路的最短路SDBTCEA712244731555本讲稿第七十一页，共一百三十一页SDBTCEA7122447315550本讲稿第七十二页，共一百三十一页SDBTCEA71224473155505，s4，s2，s2，s本讲稿第七十三页，共一百三十一页SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s本讲稿第七十四页，共一百三十一页SDBTCEA71224473155505，s4，s2，s2，s9，A

36、4，A4，s4，A8，C本讲稿第七十五页，共一百三十一页SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B 7，B本讲稿第七十六页，共一百三十一页SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E本讲稿第七十七页，共一百三十一页lST=13;S-T最短路为最短路为SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D本讲稿第七十八页，共一百三十一页实例评述实例评述vDijkstr

37、a算法不仅找到了所求最短路，而且找到了从算法不仅找到了所求最短路，而且找到了从S点到其点到其他所有顶点的最短路；这些最短路构成了图的一个连通无他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。圈的支撑子图，即图的一个支撑树。SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D本讲稿第七十九页，共一百三十一页注注:Dijkstra算法只适用于所有算法只适用于所有wij0的情形，当赋权有向图中存在负权时，的情形，当赋权有向图中存在负权时，算法失效。如算法失效。如v1v2v3 12-3用

38、用Dijkstra算法可以得出从算法可以得出从v1到到v2的最短路的权是的最短路的权是1，但实际上从，但实际上从v1到到v2的最短路是（的最短路是（v1，v3，v2），权是），权是-1。本讲稿第八十页，共一百三十一页下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任一点到任一点vj都有一条弧（如果在都有一条弧（如果在D中，（中，（vi，vj）A，则添加弧（，则添加弧（vi，vj）令）令wij=+）。）。显然，从显然，从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi，再，再沿（沿（v

39、i，vj）到）到vj的，由前面的结论可知，从的，由前面的结论可知，从vs到到vi的这条路必的这条路必定是从定是从vs到到vi的最短路，所以的最短路，所以d（vs，vj）必满足如下方程：）必满足如下方程：本讲稿第八十一页，共一百三十一页本讲稿第八十二页，共一百三十一页6-1-3-283-52-111-1217-3-5例：求例：求v1到各点的最短路。到各点的最短路。本讲稿第八十三页，共一百三十一页wijv1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v610-17-1

40、-1-1v7-1-305-5-5v8-5066本讲稿第八十四页，共一百三十一页v例一个连接例一个连接11个城镇的交通图以及城市个城镇的交通图以及城市u与与v之间的一条最短之间的一条最短路。（粗线表示）路。（粗线表示）uv本讲稿第八十五页，共一百三十一页uv本讲稿第八十六页，共一百三十一页求任意两点的最短路算法求任意两点的最短路算法-Floyd算法算法这种算法用一个这种算法用一个n阶方阵来表示一个阶方阵来表示一个n-结点网络结点网络.矩阵中的矩阵中的(i,j)-元元 dij 表示从表示从 i 到到 j边上的权边上的权,即即本讲稿第八十七页，共一百三十一页ijkFloyds algorithm 的

41、基本思想：给定结点的基本思想：给定结点 i,j 和和 k，若有如，若有如下三角形，且下三角形，且 ，则从，则从i经过经过 k到到j 比直接到比直接到j所所经过路线短。经过路线短。此时用此时用ikj 代替代替ij最好最好.-三角形运算三角形运算本讲稿第八十八页，共一百三十一页本讲稿第八十九页，共一百三十一页1245335461510 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5 1 2 3 4 523451345124512351234本讲稿第九十页，共一百三十一页 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5

42、1 2 3 4 523451345124512351234 1 2 3 4 5 1 2 3 4 5310313510136155644 1 2 3 4 5 1 2 3 4 523451145114512351234本讲稿第九十一页，共一百三十一页 1 2 3 4 5 1 2 3 4 5310313510136155644 1 2 3 4 5 1 2 3 4 523451145114512351234 1 2 3 4 531083135101361585644 1 2 3 4 5 1 2 3 4 5232511451145223512341 2 3 4 5本讲稿第九十二页，共一百三十一页 1 2

43、 3 4 531083135101361585644 1 2 3 4 5 1 2 3 4 523251145114522351234 1 2 3 4 5310825313528101361585644 1 2 3 4 5 1 2 3 4 5232311431145223512341 2 3 4 51 2 3 4 5本讲稿第九十三页，共一百三十一页 1 2 3 4 5310825313528101361585644 1 2 3 4 5 1 2 3 4 5232311431145223512341 2 3 4 5 1 2 3 4 53108123115910116108564129104 1 2

44、3 4 5 1 2 3 4 5232414441444223544441 2 3 4 5本讲稿第九十四页，共一百三十一页 1 2 3 4 53108123115910116108564129104 1 2 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 512453354615101245本讲稿第九十五页，共一百三十一页用线性规划求最短路用线性规划求最短路124531001550106030求从求从1到到2的最短路的最短路20本讲稿第九十六页，共一百三十一页10.4 网络最大流问题网络最大流问题本讲稿第九十七页，共一百三十一页vsv1v3v4v2vt322

45、223111网络流图网络流图设设D=(V,A,W)是一个有向网络。是一个有向网络。vs是网络的源点，是网络的源点，vt是网络的是网络的汇点。汇点。弧上的数字是允许通过的最大流量弧上的数字是允许通过的最大流量。本讲稿第九十八页，共一百三十一页可行流可行流设设f是定义在弧集是定义在弧集A上的一个函数，如果对所有弧上的一个函数，如果对所有弧 a 成立成立并且对所有并且对所有中间顶点中间顶点 v 成立成立其中，其中，f+(v)是流出是流出v 的流量，的流量，f -(v)是流入是流入v的流量。的流量。则称则称 f 是网络是网络D上的一个可行流。上的一个可行流。2,1vsv1v3v4v2vt3,12,12

46、,22,13,21,01,01,1-容量限制容量限制-守恒条件守恒条件本讲稿第九十九页，共一百三十一页流值流值对于源点对于源点vs和汇点和汇点vt，流出源点，流出源点vs的流量等于流入汇点的流量等于流入汇点vt的流的流量，称之为流量，称之为流 f 的值，记为的值，记为val f。即即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1val f=3本讲稿第一百页，共一百三十一页最大流最大流网络最大流是指给定网络上的流值最大的一个可行流。网络最大流是指给定网络上的流值最大的一个可行流。寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。寻找给定网络的最大流及其有效

47、算法是网络规划的一个重要问题。Ford 与与 Fulkerson 在在1957年提出一个求解网络最大流问年提出一个求解网络最大流问题的算法，称为题的算法，称为Ford Fulkerson 算法。算法。本讲稿第一百零一页，共一百三十一页割集割集v设设S是网络的顶点子集，且是网络的顶点子集，且割集的容量定义为割集的容量定义为最小割是指容量最小的割。最小割是指容量最小的割。定义定义D的一个割集，简称割为的一个割集，简称割为vsv1v3v4v2vt322223111本讲稿第一百零二页，共一百三十一页定理定理1对于网络的任意流对于网络的任意流 f 和割和割 成立成立证明证明 由定义可知由定义可知本讲稿第

48、一百零三页，共一百三十一页推论推论1 对于网络的任意流对于网络的任意流 f 和割和割 ，成立成立vsv1v3v4v2vt322223111本讲稿第一百零四页，共一百三十一页注：推论注：推论2的逆命题也成立，即推论中的等式永远成立。称为最的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。大流最小割定理，是网络理论的一个重要定理。则则f 是最大流，是最大流，K是最小割。是最小割。如果成立如果成立推论推论2 设设 f 是网络的一个可行流，是网络的一个可行流，是网络的一个割，是网络的一个割，本讲稿第一百零五页，共一百三十一页链、正向弧、反向弧链、正向弧、反向弧 v

49、设设P是网络是网络D的一条链，则的一条链，则P中的弧可分为两类：中的弧可分为两类：v正向弧正向弧弧的方向与弧的方向与P的走向一致；记为的走向一致；记为P+。v反向弧反向弧弧的方向与弧的方向与P的走向相反的走向相反;记为记为P-。网络网络D的连接源点的连接源点vs和汇点和汇点vt的路。的路。vsv1v3v4v2vt322223111本讲稿第一百零六页，共一百三十一页增广链增广链v设设P是网络是网络D的一条连接源点的一条连接源点vs和汇点和汇点vt的链，的链，f 是网络是网络D上的一个可行流上的一个可行流.v如果如果P的每一正向弧都是的每一正向弧都是不饱和弧不饱和弧，而而P的每一反向弧的流量都为正

50、的每一反向弧的流量都为正；v则称则称P是网络是网络D的关于可行流的关于可行流f 的一条可增广链。简称增广链。的一条可增广链。简称增广链。可增广链上流量可以增加。可增广链上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,21,01,11,0本讲稿第一百零七页，共一百三十一页定理定理2v设设f 是网络是网络D上的一个可行流，则上的一个可行流，则 f 是一个最大流当且仅当是一个最大流当且仅当网络网络D不存在不存在f 的增广链。的增广链。证明证明 （必要性）（必要性）设设f 是一个最大流，假如是一个最大流，假如D中存在中存在f 的增广链的增广链P,则可以得到一则可以得到一个流值