运筹学图与网络优化.ppt

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

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

2、的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。最优匹配问题等。七桥问题七桥问题七桥问题图形七桥问题图形原原 理理 及及 方方 法法 七桥问题是图论中的著名问题。七桥问题是图论中的著名问题。17361736年，年，EulerEuler巧妙巧妙地将此问题化为图的不重复一笔画问题，并证明了地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。接奇数条边。10.1 图的基本概念图的基本概念一个图一个图(Graph)定义为三元有序

3、组定义为三元有序组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是一个图，是一个图，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与边与边e

7、j相关联的次数，相关联的次数，取值可能为取值可能为0、1、2。注注v图的邻接矩阵比它的关联矩阵小的多，因而图图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。常常以其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。关联矩阵和邻接矩阵统称图的矩阵表示。顶点的度顶点的度设设G是一个图，是一个图，G=(V(G),E(G)，定义图定义图G的顶点的顶点v的度为与顶点的度为与顶点v相关联的边数，记作相关联的边数，记作d(v)例例称度为奇数的顶点为奇点；称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。称度为偶数的顶点为偶点。例例2222 2224+3+3+4=1

8、4=27关联矩阵性质关联矩阵性质图图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；则每行元矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于素之和等于相应顶点的度；每列元素之和等于2。因此，因此，图图G的关联矩阵的关联矩阵M所有元素之和既等于所所有元素之和既等于所有顶点的度之和，又等于边数的有顶点的度之和，又等于边数的2倍。倍。定理设定理设G是一个图，则是一个图，则推论推论图中奇点的数目为偶数。图中奇点的数目为偶数。证明证明记记简单图简单图一个图称为一个图称为简单图简单图，如果它既没有环也没有多重边。，如果它既没有环也没有多重边。下图是简单图。下图是简单图。本书只限于讨论有限简单图，本

9、书只限于讨论有限简单图，即顶点集与边集都是有限集的图。即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图；边集是空集的图称为边集是空集的图称为空图空图。同构同构称称G和和H是同构的，记为是同构的，记为，使得使得给定两个图给定两个图如果存在两个一一对应如果存在两个一一对应同构图例同构图例v图图G与图与图H是同构的。是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4完全图Knv完全图是每一对不同顶点都恰有一边的简单图；完全图是每一对不同顶点都恰有一边的简单图；v具有具有n个顶点的完全

10、图记为个顶点的完全图记为Kn.K5二分图二分图v二分图是一个简单图，其顶点集合可分划成两个子集二分图是一个简单图，其顶点集合可分划成两个子集X与与Y，使得每条边的一个端点在，使得每条边的一个端点在X，另一个端点在，另一个端点在Y;(X,Y)也称也称为图的二分划。为图的二分划。x1x2x3y1y2y3完全二分图完全二分图v完全二分图是具有二分划完全二分图是具有二分划(X,Y)的二分图，并且的二分图，并且X的每个顶点与的每个顶点与Y的每个顶点都相连；记为的每个顶点都相连；记为Km,n，v其中其中K3,3特殊图例特殊图例K5K 3,3都是极小的非平面图都是极小的非平面图子图子图称图称图H是图是图G的

11、子图，的子图，图图G及其基本图及其基本图称称H是是G的的支撑子图支撑子图，如果如果称称H是是G的真子图的真子图，若若如果如果表示关联函数表示关联函数记为记为在在H的限制。的限制。顶点导出子图顶点导出子图设设W是图是图G的一个非空顶点子集的一个非空顶点子集,以以W为顶点集，以二端点为顶点集，以二端点均在均在W中的边的全体为边集的子图称为由中的边的全体为边集的子图称为由W导出的导出的G的子的子图，简称导出子图，记为图，简称导出子图，记为GW。导出子图导出子图GV-w记为记为G-W，即，即 它是从它是从G中删除中删除W中顶点以及与这些顶点相关联的边所得中顶点以及与这些顶点相关联的边所得到的子图。到的

12、子图。如果如果W仅含一个顶点仅含一个顶点v，则把，则把 简记为。简记为。边导出子图边导出子图设设F是图是图G的非空边子集，以的非空边子集，以F为边集，以为边集，以F中边的端点全体中边的端点全体为顶点集所构成的子图称为由为顶点集所构成的子图称为由F导出的导出的G的子图，简称的子图，简称G的边的边导出子图。记为导出子图。记为GF。记记G-F表示以表示以E(G)F为边集的为边集的G的支撑子图，它是从的支撑子图，它是从G中删中删除除F中的边所得到的子图。中的边所得到的子图。如如F=e，则记。，则记。子图图例子图图例v1v2v3v4v5e1e3e2Gv1v2v3v4v5G的支撑子图的支撑子图G-e1,e

13、 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的起点，的起点，v顶点顶点vi 叫叫W的内部顶点，的内部顶点，v整数整数k称为称为W的长度。的长度。v在简单图中，径可由顶点序列表示。在简单图中，径可由顶点序列表示。图图G的一个有限的点边交错序列称为从的一个有限的点边交错序列称为从v0到到vk的途径。的途径。其中其中vi与与vi+1是边是边ei的顶点的顶点;路、路、链v如果径如果径W的边

14、不相同，则称的边不相同，则称W为一条链，为一条链，如果如果W顶点互不相同，则称顶点互不相同，则称W是一条路。是一条路。链长是链长是W中边的个数中边的个数k。记路长记路长uvwxyabdefgh|路：路：xcwhyeuav|链：链：wcxdyhwbvgyc圈圈(回路回路)v如果途径如果途径W的起点和终点相同且有正长度，则称它的起点和终点相同且有正长度，则称它是一个闭途径；是一个闭途径；v如果一条闭链的顶点互不相同，则称它是一个圈如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。（或回路）。v称一个圈是偶圈（奇圈），如果它的圈长是偶数称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。（奇数）

15、。圈：uavbwhyeuuvwxyabdefghc定理定理v一个图是二分图当且仅当图中不存在奇圈。一个图是二分图当且仅当图中不存在奇圈。Euler圈圈vEuler圈是指过所有边一次且恰好一次的圈是指过所有边一次且恰好一次的闭途径闭途径。vEuler链是指过所有边一次且恰好一次的链。链是指过所有边一次且恰好一次的链。Euler链链:ydxcwheuavfygvbwuvwxyabdefghc图例图例v下例给出了一个图的径，链和路。下例给出了一个图的径，链和路。v径：径：uavfyfvgyhwbvv链：链：wcxdyhwbvgyv路：路：xcwhyeuavv圈：圈：uavbwhyeuvEuler链链

16、:ydxcwheuavfygvbwuvwxyabdefghcEuler型型定理定理v定理定理2设设G是连通圈，则是连通圈，则G是是Euler型的充要型的充要条件是条件是G没有奇次数的顶点。没有奇次数的顶点。v推论推论1设设G是一个连通图，则是一个连通图，则G有有Euler链当链当且仅当且仅当G最多有两个奇数次数的顶点。最多有两个奇数次数的顶点。连通性连通性v图图G称为连通的，如果在称为连通的，如果在G的任意两个顶点的任意两个顶点u和和v中存在一条中存在一条(u,v)路。路。|不连通图至少有两个连通分支。不连通图至少有两个连通分支。两点顶点两点顶点u和和v等价当且仅当等价当且仅当u和和v中存在一

17、条中存在一条(u,v)路。路。表示表示G的连通分支数。的连通分支数。10.2 树树树（树（tree）是一个不包含圈的简单连通图。）是一个不包含圈的简单连通图。具有具有k个连通分支的不包含圈的图称为个连通分支的不包含圈的图称为k-树，或森林。树，或森林。下图列出了具有六个顶点的不同构的树。从中可以看出，下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有图中的每棵树都只有5条边，并且至少有条边，并且至少有2个顶点的次数是个顶点的次数是1。性质性质1设设G是一棵树，则：是一棵树，则：G中任意两点均有唯一的路连接。中任意两点均有唯一的路连接。2 G的边数等于顶点数减的边数等于顶点数减

18、1，即，即3 若若G不是平凡图，则不是平凡图，则G至少有两个次数为至少有两个次数为1的顶点。的顶点。定理定理1设设G是一个简单图，是一个简单图，则下列六个命题是等价的。，则下列六个命题是等价的。vG是一棵树。是一棵树。v无圈且无圈且m=n-1。vG连通且连通且m=n-1。vG连通并且每条边都是割边。连通并且每条边都是割边。vG中任意两点都有唯一的路相连。中任意两点都有唯一的路相连。vG无圈，但在任意一对不相邻的顶点之间加连一条无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。边，则构成唯一的一个圈。支撑树支撑树v图图G的支撑树是的支撑树是G的支撑子图，并且是一棵树。的支撑子图，

19、并且是一棵树。v每个连通图都有支撑树每个连通图都有支撑树v支撑树也称为连通图的极小连通支撑子图。支撑树也称为连通图的极小连通支撑子图。v很显然，一个连通图只要本身不是一棵树，它的支撑很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。树就不止一个。定理定理v定理定理4设设T1 和和T2 是是G的两个支撑树，令的两个支撑树，令 则则T1 经过经过k次迭代后可得到次迭代后可得到T2。v定理定理2设设G是一个连通图，是一个连通图，T是是G的一棵支撑树，的一棵支撑树，e是是G的的一条不属于一条不属于T的边，则的边，则T+e含有含有G的唯一圈。的唯一圈。v定理定理3设设T是连通图是连通图G的一棵

20、支撑树，的一棵支撑树，e是是T的任意一条边，的任意一条边，则：则：T（1）不包含不包含G的割集的割集（2）包含）包含G的唯一的割集。的唯一的割集。最小树最小树定理定理5设设T是是G的一个支撑树，则的一个支撑树，则T是是G的最小树的充分的最小树的充分必要条件为对任意边必要条件为对任意边设设G是一个赋权图，是一个赋权图，T为为G的一个支撑树。定义的一个支撑树。定义T的权为：的权为：G中权最小的支撑树称为中权最小的支撑树称为G的最小树。的最小树。定理定理6v设设T是是G的支撑树，则的支撑树，则T是是G的最小树的充分必要条件为对任的最小树的充分必要条件为对任意边意边 ，其中其中 为为G的唯一割集。的唯

21、一割集。最小树算法最小树算法-1-贪心算法贪心算法Kruskal在在1965年提出一种求最小树的所谓贪心算法。年提出一种求最小树的所谓贪心算法。算法步骤如下算法步骤如下vStep0 把边按权的大小从小到大排列得：把边按权的大小从小到大排列得：置置Step1 若若 ，则停，此时，则停，此时GS即为所求的最小树；即为所求的最小树；否则，转向否则，转向Step2。Step2 如果如果 GS+e j不构成回路，则令不构成回路，则令转向转向Step1；否则，令；否则，令j=j+1转向转向Step2。算例算例图图7-18展示了利用展示了利用Kruskal算法求最小树的迭代过程。算法求最小树的迭代过程。v1

22、v2v4v5v312244342v1v2v4v5v312244342图图7-18v1v2v4v5v312244342v1v2v4v5v312244342图7-18-1评注评注Kruskal算法的总计算量为算法的总计算量为 ，有效性不太好。，有效性不太好。求求最最小小树树的的一一个个好好的的算算法法是是Dijkstra于于1959年年提提出出的的，算算法法的的实实质质是是在在图图的的 个个独独立立割割集集中中，取取每每个个割割集集的的一一条条极极小小边边来来构成最小树。构成最小树。最小树算法最小树算法-2-Dijkstra算法算法Step0 置置Step1 取取置置Step2 若若 ，则停止；，

23、则停止；否则，置否则，置 ，返回，返回Step1算例算例2图图7-19展示了利用展示了利用Dijkstra算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-19利用利用Dijkstra算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-19-1v破圈法是破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。其是当图的顶点数和边数比较大时，可以在各个局

24、部进行。Step1 若若G不含圈，则停止；否则在不含圈，则停止；否则在G中找一个圈中找一个圈C，取圈，取圈C的的一条边一条边e ，满足，满足最小树算法最小树算法-3-破圈法破圈法Step2：置：置 G=G-e，返回，返回Step1。利用破圈法求图利用破圈法求图7-19的最小树的过程如图的最小树的过程如图7-20所示。所示。算例算例3图图7-20展示了利用破圈法求最小树的迭代过程。展示了利用破圈法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-20v1v2v4v5v312244342v1v2v4v5v312244342图图7-20-1评注评注上

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

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

27、问题最小连接问题作作为为最最小小树树的的应应用用问问题题之之一一是是所所谓谓的的连连接接问问题题：欲欲建建造造一一个个连连接接若若干干城城镇镇（矿矿区区或或工工业业区区）的的铁铁路路网网，给给定定城城镇镇i和和j之之间间直直通通线线路路的的造造价价为为cij，试试设设计计一一个个总总造造价价最最小小的铁路运输图。的铁路运输图。v把每个城镇看作是具有权把每个城镇看作是具有权cij的赋权图的赋权图G的一个顶点。显的一个顶点。显然连接问题可以表述成：在赋权图然连接问题可以表述成：在赋权图G中，求出具有最小权中，求出具有最小权的支撑树。的支撑树。10.3 最短路问题最短路问题vDijkstra算法算法

28、v求任意两点的最短路算法求任意两点的最短路算法-Floyd算法算法v求带负权网络图的最短路的算法求带负权网络图的最短路的算法v用线性规划求最短路用线性规划求最短路赋权图赋权图v给定赋权图的一个子图给定赋权图的一个子图H，定义，定义H的权为的权为H的所有边权的总和。的所有边权的总和。n对图对图G的每条边的每条边e，赋予一实数，赋予一实数(e)，称为边，称为边e的权，可得一的权，可得一赋权图。赋权图。SDBTCEA712244731555v赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。n在一个赋权图在一个赋权图G上，给定两个顶点上，给定两个顶点u和和 v，所谓，所谓u和和 v最短最短 路

29、是指所有连接顶点路是指所有连接顶点u和和 v 的路中路长最短的路；的路中路长最短的路；nu和和v最短路的路长也称为最短路的路长也称为u和和 v的距离。的距离。SDBTCEA712244731555n如何求从如何求从u到到v的的最短路的长？最短路的长？vDijkstra算法的基本思想：算法的基本思想：(1)u0u1P设设S是是V的真子集，的真子集，如果如果 是从是从u0 到的最短路，到的最短路，则则，并且，并且P的的 段是最短的段是最短的 路，所以路，所以算法标号算法标号v令令dij表示连接顶点表示连接顶点vi与顶点与顶点vj边上的权，即边上的权，即(1)公式（公式（1）是）是Dijkstra算

30、法的基础。算法的基础。定义结点定义结点vj 的标号为的标号为始点的标号为始点的标号为0,-,表明这个点前面没有点。表明这个点前面没有点。结点结点vj 的标号分为两种：的标号分为两种：临时性标号和永久性标号临时性标号和永久性标号。如果。如果找到一条更短的路，临时性标号即被修改，如果找不到一找到一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。条更短的路，临时性标号即被改为永久性标号。vStep0 令令始点的标号为始点的标号为0,-.令令i=1 Step i(a)对于由结点对于由结点i可达的还没有永久性标号的结点可达的还没有永久性标号的结点j，计算其计算其临时

31、性标号临时性标号li+dij,i（dij0）.如果如果 j 已经通过另一已经通过另一个结点个结点k标号为标号为 lj,k 且且 li+dijlj,则用则用li+dij,i取代取代 lj,k。(b)如果所有的结点都是永久性标号，停止。否则选择最小如果所有的结点都是永久性标号，停止。否则选择最小的临时性标号的临时性标号 lr,s。令令 i=r，返回返回Step i.计算实例计算实例求连接求连接S、T的最短路的最短路SDBTCEA712244731555SDBTCEA7122447315550SDBTCEA71224473155505，s4，s2，s2，sSDBTCEA71224473155505，

32、s4，s2，s2，s9，A4，A4，sSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，CSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B 7，BSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，ElST=13;S-T最短路为最短路为SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D实例评述实例评述vDijkstra算法不仅找到了所求

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

34、到v2的最短路的权是的最短路的权是1，但实际上，但实际上从从v1到到v2的最短路是（的最短路是（v1，v3，v2），权是），权是-1。下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任一点到任一点vj都有一条弧（如果在都有一条弧（如果在D中，中，（vi，vj）A，则添加弧（，则添加弧（vi，vj）令）令wij=+）。）。显然，从显然，从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi，再沿（，再沿（vi，vj）到）到vj的，由前面的结论可知，从的，由前面的结论可知，从vs到到vi的这

35、条路必定是从的这条路必定是从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-1-1v7-1-305-5-5v8-5066v例一个连接例一个连接11个城镇的交通图以及城市个城镇的交通图以及城市u与与v之间的一之间的一条最短路。（粗线表示）条最短路。（粗线表

36、示）uvuv求任意两点的最短路算法求任意两点的最短路算法-Floyd算法算法这种算法用一个这种算法用一个n阶方阵来表示一个阶方阵来表示一个n-结点网络结点网络.矩阵中的矩阵中的(i,j)-元元 dij 表示从表示从 i 到到 j边上的权边上的权,即即ijkFloyds algorithm 的基本思想：给定结点的基本思想：给定结点 i,j 和和 k，若有如，若有如下三角形，且下三角形，且 ，则从，则从i经过经过 k到到j 比直接到比直接到j所经所经过路线短。过路线短。此时用此时用ikj 代替代替ij最好最好.-三角形运算三角形运算1245335461510 1 2 3 4 5 1 2 3 4 5

37、31035106155644 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 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 5310831

38、35101361585644 1 2 3 4 5 1 2 3 4 5232511451145223512341 2 3 4 5 1 2 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

39、 2 3 4 5 1 2 3 4 53108123115910116108564129104 1 2 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的最短路的最短路2010.4 网络最大流问题网络最大流问题vsv1v3v4v2vt322223111网络流图网络流

40、图设设D=(V,A,W)是一个有向网络。是一个有向网络。vs是网络的源点，是网络的源点，vt是是网络的汇点。网络的汇点。弧上的数字是允许通过的最大流量弧上的数字是允许通过的最大流量。可行流可行流设设f是定义在弧集是定义在弧集A上的一个函数，如果对所有弧上的一个函数，如果对所有弧 a 成立成立并且对所有并且对所有中间顶点中间顶点 v 成立成立其中，其中，f+(v)是流出是流出v 的流量，的流量，f -(v)是流入是流入v的流量。的流量。则称则称 f 是网络是网络D上的一个可行流。上的一个可行流。2,1vsv1v3v4v2vt3,12,12,22,13,21,01,01,1-容量限制容量限制-守恒

41、条件守恒条件流值流值对于源点对于源点vs和汇点和汇点vt，流出源点，流出源点vs的流量等于流入汇的流量等于流入汇点点vt的流量，称之为流的流量，称之为流 f 的值，记为的值，记为val f。即即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1val f=3最大流最大流网络最大流是指给定网络上的流值最大的一个可行流。网络最大流是指给定网络上的流值最大的一个可行流。寻找给定网络的最大流及其有效算法是网络规划的一个寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。重要问题。Ford 与与 Fulkerson 在在1957年提出一个求解网络最大流年提出一个求解网络

42、最大流问题的算法，称为问题的算法，称为Ford Fulkerson 算法。算法。割集割集v设设S是网络的顶点子集，且是网络的顶点子集，且割集的容量定义为割集的容量定义为最小割是指容量最小的割。最小割是指容量最小的割。定义定义D的一个割集，简称割为的一个割集，简称割为vsv1v3v4v2vt322223111定理定理1对于网络的任意流对于网络的任意流 f 和割和割 成立成立证明证明 由定义可知由定义可知推论推论1 对于网络的任意流对于网络的任意流 f 和割和割 ，成立成立vsv1v3v4v2vt322223111注：推论注：推论2的逆命题也成立，即推论中的等式永远成立。的逆命题也成立，即推论中的

43、等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。称为最大流最小割定理，是网络理论的一个重要定理。则则f 是最大流，是最大流，K是最小割。是最小割。如果成立如果成立推论推论2 设设 f 是网络的一个可行流，是网络的一个可行流，是网络的一个割，是网络的一个割，链、正向弧、反向弧链、正向弧、反向弧 v设设P是网络是网络D的一条链，则的一条链，则P中的弧可分为两类：中的弧可分为两类：v正向弧正向弧弧的方向与弧的方向与P的走向一致；记为的走向一致；记为P+。v反向弧反向弧弧的方向与弧的方向与P的走向相反的走向相反;记为记为P-。网络网络D的连接源点的连接源点vs和汇点和汇点vt的路。的路。

44、vsv1v3v4v2vt322223111增广链增广链v设设P是网络是网络D的一条连接源点的一条连接源点vs和汇点和汇点vt的链，的链，f 是网络是网络D上的一个可行流上的一个可行流.n如果如果P的每一正向弧都是的每一正向弧都是不饱和弧不饱和弧，而而P的每一反向弧的流量都为正的每一反向弧的流量都为正；n则称则称P是网络是网络D的关于可行流的关于可行流f 的一条可增广链。简称增广链。的一条可增广链。简称增广链。可增广链上流量可以增加。可增广链上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,21,01,11,0定理定理2v设设f 是网络是网络D上的一个可行流，则上的一个可

45、行流，则 f 是一个最大流当是一个最大流当且仅当网络且仅当网络D不存在不存在f 的增广链。的增广链。证明证明 （必要性）（必要性）设设f 是一个最大流，假如是一个最大流，假如D中存在中存在f 的增广链的增广链P,则可以则可以得到一个流值更大的流得到一个流值更大的流f 1,使得使得v构造过程如下：构造过程如下：其中其中证明证明n充分性充分性设网络设网络D不存在不存在f 的增广链。定义的增广链。定义S如下：如下：从而从而 是是D的割集，进而可得的割集，进而可得 中的弧都是饱和弧，而中的弧都是饱和弧，而 中的弧都是中的弧都是0流弧，流弧，否则将产生网络否则将产生网络D 的一条增广链。因此，的一条增广

46、链。因此，f 的流值等于割的流值等于割集集 的割量的割量，所以，所以，f是一个最大流。是一个最大流。定理定理3在任何网络流图中，最大流的值等于最小割的容量。在任何网络流图中，最大流的值等于最小割的容量。（最大流最小割定理）（最大流最小割定理）Ford Fulkerson 算法算法vFord Fulkerson 算法的基本思想是从任意一个可行流出发，算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。个新可行流，依次进行下去，直到一个最大流为止。定理的证明过程蕴

47、涵着最大流算法定理的证明过程蕴涵着最大流算法算例算例v求下面网络的最大流求下面网络的最大流vsv1v3v4v2vt852879665图图4.23初始初始0流流v先给网络赋一个初始先给网络赋一个初始0流流f 0 图图4.2-1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,)寻找增广链寻找增广链1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,)(+v1,5)(+v3,2)寻

48、找增广链寻找增广链2vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,)(+v1,5)(+v3,2)(+v2,5)寻找增广链寻找增广链3寻找增广链寻找增广链4v找到流找到流f 0 的增广链的增广链P0=vs v1 v2 vt.vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,)(+v1,5)(+v3,2)(+v2,5)|增量增量=5.调整流值调整流值2v调整流值得流值为调整流值得流值为5的新可行流的新可行流f 1，vsv1v3v4v2vt8,55,52,08,

49、07,09,56,06,05,03,0vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,)vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,)(+v3,2)(+v3,2)vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,)(+v3,2)(+v3,2)(+v2,2)|增量增量=2.vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-

50、,)(+v3,2)(+v3,2)(+v2,2)v找到流找到流f 1 的增广链的增广链P0=vs v3 v2 vt，调整流值调整流值3v调整流值得流值为调整流值得流值为7的新可行流的新可行流f 2，vsv1v3v4v2vt8,55,52,28,07,09,76,06,05,23,0vsv1v3v4v2vt8,55,52,28,07,09,76,06,05,23,0(+vs,3)(+v1,3)(-,)(+v3,3)(+v3,3)(+v2,2)|增量增量=2.vsv1v3v4v2vt8,75,52,28,07,09,96,26,05,43,0vsv1v3v4v2vt8,75,52,28,07,09,