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

运筹学 图与网络优化第1页，此课件共131页哦图论概述图论概述v图论图论(Graph Theory)是运筹学中的一个重要分支，主是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。要研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。型来描述。第2页，此课件共131页哦网络规划概述网络规划概述v网络规划网络规划(Network Programming)是图论与线是图论与线性规划的交叉学科，具有广泛的应用背景，比如，性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹最短路问题、最小树问题、最大流问题、最优匹配问题等。配问题等。第3页，此课件共131页哦七桥问题七桥问题七桥问题图形七桥问题图形第4页，此课件共131页哦原原 理理 及及 方方 法法 七桥问题是图论中的著名问题。七桥问题是图论中的著名问题。17361736年，年，EulerEuler巧妙巧妙地将此问题化为图的不重复一笔画问题，并证明了地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。接奇数条边。第5页，此课件共131页哦10.1 图的基本概念图的基本概念一个图一个图(Graph)定义为三元有序组定义为三元有序组V(G)是图的顶点集合是图的顶点集合E(G)是是图图的边集合的边集合记记 是关联函数是关联函数第6页，此课件共131页哦图的端点图的端点设设G是一个图是一个图(Graph)G=(V(G),E(G)，则称则称e连接连接u和和v，称，称u和和v是是e的端点。的端点。若若称端点称端点u，v与边与边e是是关联的关联的，称两个顶点称两个顶点u，v是是邻接邻接的。的。第7页，此课件共131页哦设设G是一个图，是一个图，图10G的几何实现的几何实现第8页，此课件共131页哦图的几何实现图的几何实现 一个图可用一个几何图形表示一个图可用一个几何图形表示,称为图的几称为图的几何实现，其中何实现，其中每个顶点用点表示，每个顶点用点表示，每条边用连接端点的线表示。每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质。图的几何实现有助与我们直观的了解图的许多性质。第9页，此课件共131页哦说明说明一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点，图形的线为边。并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。重边、环、路、圈、树等。第10页，此课件共131页哦几何实现图例几何实现图例在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图图 中，它共有中，它共有4个顶点，个顶点，6条边；而条边；而e 3 与与e 4 的交点不是这个图的的交点不是这个图的顶点。顶点。第11页，此课件共131页哦平面图平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。顶点相交。下图就是一个平面图。第12页，此课件共131页哦基本概念基本概念端点重合为一点的边称为端点重合为一点的边称为环环。连接同一对顶点的多条边称为连接同一对顶点的多条边称为多重边多重边。在右图中，在右图中，e5 是一个环，是一个环，e1 与与e2 是多重边，是多重边，v1和和e1,e2,e3是关联的，是关联的，v1与与v2,v3是邻接的。是邻接的。第13页，此课件共131页哦邻接矩阵邻接矩阵设设G是一个图，是一个图，G=(V(G),E(G)，定义图，定义图G的邻接矩的邻接矩阵阵A(G)=(aij)为为mm矩阵矩阵,aij是顶点是顶点vi与边与边vj相邻接的边数。相邻接的边数。其中其中第14页，此课件共131页哦关联矩阵关联矩阵设设G是一个图，是一个图，G=(V(G),E(G)定义图定义图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；矩阵；其中其中mij是顶点是顶点vi与边与边ej相关联的次数，相关联的次数，取值可能为取值可能为0、1、2。第15页，此课件共131页哦注注v图的邻接矩阵比它的关联矩阵小的多，因而图常常图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。以其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。关联矩阵和邻接矩阵统称图的矩阵表示。第16页，此课件共131页哦顶点的度顶点的度设设G是一个图，是一个图，G=(V(G),E(G)，定义图定义图G的顶点的顶点v的度的度为与顶点为与顶点v相关联的边数，记作相关联的边数，记作d(v)例例称度为奇数的顶点为奇点；称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。称度为偶数的顶点为偶点。第17页，此课件共131页哦例例22222224+3+3+4=14=27第18页，此课件共131页哦关联矩阵性质关联矩阵性质图图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；则每行元矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于素之和等于相应顶点的度；每列元素之和等于2。因此，因此，图图G的关联矩阵的关联矩阵M所有元素之和既等于所有顶点所有元素之和既等于所有顶点的度之和，又等于边数的的度之和，又等于边数的2倍。倍。定理设定理设G是一个图，则是一个图，则第19页，此课件共131页哦推论推论图中奇点的数目为偶数。图中奇点的数目为偶数。证明证明记记第20页，此课件共131页哦简单图简单图一个图称为一个图称为简单图简单图，如果它既没有环也没有多重边。，如果它既没有环也没有多重边。下图是简单图。下图是简单图。本书只限于讨论有限简单图，本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图；边集是空集的图称为边集是空集的图称为空图空图。第21页，此课件共131页哦同构同构称称G和和H是同构的，记为是同构的，记为，使得使得给定两个图给定两个图如果存在两个一一对应如果存在两个一一对应第22页，此课件共131页哦同构图例同构图例v图图G与图与图H是同构的。是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4第23页，此课件共131页哦完全图Knv完全图是每一对不同顶点都恰有一边的简单图；完全图是每一对不同顶点都恰有一边的简单图；v具有具有n个顶点的完全图记为个顶点的完全图记为Kn.K5第24页，此课件共131页哦二分图二分图v二分图是一个简单图，其顶点集合可分划成两个子集二分图是一个简单图，其顶点集合可分划成两个子集X与与Y，使得，使得每条边的一个端点在每条边的一个端点在X，另一个端点在，另一个端点在Y;(X,Y)也称为图的二分也称为图的二分划。划。x1x2x3y1y2y3第25页，此课件共131页哦完全二分图完全二分图v完全二分图是具有二分划完全二分图是具有二分划(X,Y)的二分图，并且的二分图，并且X的每个的每个顶点与顶点与Y的每个顶点都相连；记为的每个顶点都相连；记为Km,n，v其中其中K3,3第26页，此课件共131页哦特殊图例特殊图例K5K 3,3都是极小的非平面图都是极小的非平面图第27页，此课件共131页哦子图子图称图称图H是图是图G的子图，的子图，图图G及其基本图及其基本图称称H是是G的的支撑子图支撑子图，如果如果称称H是是G的真子图的真子图，若若如果如果表示关联函数表示关联函数记为记为在在H的限制。的限制。第28页，此课件共131页哦顶点导出子图顶点导出子图设设W是图是图G的一个非空顶点子集的一个非空顶点子集,以以W为顶点集，以二端点为顶点集，以二端点均在均在W中的边的全体为边集的子图称为由中的边的全体为边集的子图称为由W导出的导出的G的子的子图，简称导出子图，记为图，简称导出子图，记为GW。导出子图导出子图GV-w记为记为G-W，即，即 它是从它是从G中删除中删除W中顶点以及与这些顶点相关联的边所得中顶点以及与这些顶点相关联的边所得到的子图。到的子图。如果如果W仅含一个顶点仅含一个顶点v，则把，则把 简记为。简记为。第29页，此课件共131页哦边导出子图边导出子图设设F是图是图G的非空边子集，以的非空边子集，以F为边集，以为边集，以F中边的端点全体为顶点中边的端点全体为顶点集所构成的子图称为由集所构成的子图称为由F导出的导出的G的子图，简称的子图，简称G的边导出子图。记的边导出子图。记为为GF。记记G-F表示以表示以E(G)F为边集的为边集的G的支撑子图，它是从的支撑子图，它是从G中删除中删除F中的中的边所得到的子图。边所得到的子图。如如F=e，则记。，则记。第30页，此课件共131页哦子图图例子图图例v1v2v3v4v5e1e3e2Gv1v2v3v4v5G的支撑子图的支撑子图G-e1,e 2,e 3第31页，此课件共131页哦子图图例子图图例2v2v3v4e2G-v 1,v 5 v1v2v5Gv 1,v 2,v 5 v1v2v3v4e1e3e2G e1,e 2,e 3v1v2v3v4v5e1e3e2G第32页，此课件共131页哦途径途径v顶点顶点vk叫叫W的终点，的终点，v顶点顶点v0 称为称为W的起点，的起点，v顶点顶点vi 叫叫W的内部顶点，的内部顶点，v整数整数k称为称为W的长度。的长度。v在简单图中，径可由顶点序列表示。在简单图中，径可由顶点序列表示。图图G的一个有限的点边交错序列称为从的一个有限的点边交错序列称为从v0到到vk的途径。的途径。其中其中vi与与vi+1是边是边ei的顶点的顶点;第33页，此课件共131页哦路、路、链v如果径如果径W的边不相同，则称的边不相同，则称W为一条链，为一条链，如果如果W顶点互不相同，则称顶点互不相同，则称W是一条路。是一条路。链长是链长是W中边的个数中边的个数k。记路长记路长uvwxyabdefghv路：路：xcwhyeuavv链：链：wcxdyhwbvgyc第34页，此课件共131页哦圈圈(回路回路)v如果途径如果途径W的起点和终点相同且有正长度，则称它是一个的起点和终点相同且有正长度，则称它是一个闭途径；闭途径；v如果一条闭链的顶点互不相同，则称它是一个圈（或如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。回路）。v称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。数）。圈：uavbwhyeuuvwxyabdefghc第35页，此课件共131页哦定理定理v一个图是二分图当且仅当图中不存在奇圈。一个图是二分图当且仅当图中不存在奇圈。第36页，此课件共131页哦Euler圈圈vEuler圈是指过所有边一次且恰好一次的圈是指过所有边一次且恰好一次的闭途径闭途径。vEuler链是指过所有边一次且恰好一次的链。链是指过所有边一次且恰好一次的链。Euler链链:ydxcwheuavfygvbwuvwxyabdefghc第37页，此课件共131页哦图例图例v下例给出了一个图的径，链和路。下例给出了一个图的径，链和路。v径：径：uavfyfvgyhwbvv链：链：wcxdyhwbvgyv路：路：xcwhyeuavv圈：圈：uavbwhyeuvEuler链链:ydxcwheuavfygvbwuvwxyabdefghc第38页，此课件共131页哦Euler型型定理定理v定理定理2设设G是连通圈，则是连通圈，则G是是Euler型的充要条件是型的充要条件是G没有奇次数的顶点。没有奇次数的顶点。v推论推论1设设G是一个连通图，则是一个连通图，则G有有Euler链当且仅链当且仅当当G最多有两个奇数次数的顶点。最多有两个奇数次数的顶点。第39页，此课件共131页哦连通性连通性v图图G称为连通的，如果在称为连通的，如果在G的任意两个顶点的任意两个顶点u和和v中存在一条中存在一条(u,v)路。路。v不连通图至少有两个连通分支。不连通图至少有两个连通分支。两点顶点两点顶点u和和v等价当且仅当等价当且仅当u和和v中存在一条中存在一条(u,v)路。路。表示表示G的连通分支数。的连通分支数。第40页，此课件共131页哦10.2 树树树（树（tree）是一个不包含圈的简单连通图。）是一个不包含圈的简单连通图。具有具有k个连通分支的不包含圈的图称为个连通分支的不包含圈的图称为k-树，或森林。树，或森林。第41页，此课件共131页哦v下图列出了具有六个顶点的不同构的树。从中可以看出，下图列出了具有六个顶点的不同构的树。从中可以看出，v图中的每棵树都只有图中的每棵树都只有5条边，并且至少有条边，并且至少有2个顶点的次数是个顶点的次数是1。第42页，此课件共131页哦性质性质1设设G是一棵树，则：是一棵树，则：G中任意两点均有唯一的路连接。中任意两点均有唯一的路连接。2 G的边数等于顶点数减的边数等于顶点数减1，即，即3 若若G不是平凡图，则不是平凡图，则G至少有两个次数为至少有两个次数为1的顶点。的顶点。第43页，此课件共131页哦定理定理1设设G是一个简单图，是一个简单图，则下列六个命题是等价的。，则下列六个命题是等价的。vG是一棵树。是一棵树。v无圈且无圈且m=n-1。vG连通且连通且m=n-1。vG连通并且每条边都是割边。连通并且每条边都是割边。vG中任意两点都有唯一的路相连。中任意两点都有唯一的路相连。vG无圈，但在任意一对不相邻的顶点之间加连一条边，则无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。构成唯一的一个圈。第44页，此课件共131页哦支撑树支撑树v图图G的支撑树是的支撑树是G的支撑子图，并且是一棵树。的支撑子图，并且是一棵树。v每个连通图都有支撑树每个连通图都有支撑树v支撑树也称为连通图的极小连通支撑子图。支撑树也称为连通图的极小连通支撑子图。v很显然，一个连通图只要本身不是一棵树，它的支撑树很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。就不止一个。第45页，此课件共131页哦定理定理v定理定理4设设T1 和和T2 是是G的两个支撑树，令的两个支撑树，令 则则T1 经过经过k次迭代后可得到次迭代后可得到T2。v定理定理2设设G是一个连通图，是一个连通图，T是是G的一棵支撑树，的一棵支撑树，e是是G的一条不的一条不属于属于T的边，则的边，则T+e含有含有G的唯一圈。的唯一圈。v定理定理3设设T是连通图是连通图G的一棵支撑树，的一棵支撑树，e是是T的任意一条边，则：的任意一条边，则：T（1）不包含不包含G的割集的割集（2）包含）包含G的唯一的割集。的唯一的割集。第46页，此课件共131页哦最小树最小树定理定理5设设T是是G的一个支撑树，则的一个支撑树，则T是是G的最小树的充分的最小树的充分必要条件为对任意边必要条件为对任意边设设G是一个赋权图，是一个赋权图，T为为G的一个支撑树。定义的一个支撑树。定义T的权为：的权为：G中权最小的支撑树称为中权最小的支撑树称为G的最小树。的最小树。第47页，此课件共131页哦定理定理6v设设T是是G的支撑树，则的支撑树，则T是是G的最小树的充分必要条件为对任意边的最小树的充分必要条件为对任意边 ，其中其中 为为G的唯一割集。的唯一割集。第48页，此课件共131页哦最小树算法最小树算法-1-贪心算法贪心算法Kruskal在在1965年提出一种求最小树的所谓贪心算法。年提出一种求最小树的所谓贪心算法。算法步骤如下算法步骤如下vStep0 把边按权的大小从小到大排列得：把边按权的大小从小到大排列得：置置Step1 若若 ，则停，此时，则停，此时GS即为所求的最小树；即为所求的最小树；否则，转向否则，转向Step2。Step2 如果如果 GS+e j不构成回路，则令不构成回路，则令转向转向Step1；否则，令；否则，令j=j+1转向转向Step2。第49页，此课件共131页哦算例算例图图7-18展示了利用展示了利用Kruskal算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-18第50页，此课件共131页哦v1v2v4v5v312244342v1v2v4v5v312244342图7-18-1第51页，此课件共131页哦评注评注Kruskal算法的总计算量为算法的总计算量为 ，有效性不太好。，有效性不太好。求求最最小小树树的的一一个个好好的的算算法法是是Dijkstra于于1959年年提提出出的的，算算法法的的实实质质是是在图的在图的 个独立割集中，取每个割集的一条极小边来构成最小树。个独立割集中，取每个割集的一条极小边来构成最小树。第52页，此课件共131页哦最小树算法最小树算法-2-Dijkstra算法算法Step0 置置Step1 取取置置Step2 若若 ，则停止；，则停止；否则，置否则，置 ，返回，返回Step1第53页，此课件共131页哦算例算例2图图7-19展示了利用展示了利用Dijkstra算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-19第54页，此课件共131页哦利用利用Dijkstra算法求最小树的迭代过程。算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-19-1第55页，此课件共131页哦v破圈法是破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。的顶点数和边数比较大时，可以在各个局部进行。Step1 若若G不含圈，则停止；否则在不含圈，则停止；否则在G中找一个圈中找一个圈C，取圈，取圈C的一条边的一条边e ，满足，满足最小树算法最小树算法-3-破圈法破圈法Step2：置：置 G=G-e，返回，返回Step1。利用破圈法求图利用破圈法求图7-19的最小树的过程如图的最小树的过程如图7-20所示。所示。第56页，此课件共131页哦算例算例3图图7-20展示了利用破圈法求最小树的迭代过程。展示了利用破圈法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-20第57页，此课件共131页哦v1v2v4v5v312244342v1v2v4v5v312244342图图7-20-1第58页，此课件共131页哦评注评注上上述述算算法法都都可可以以在在图图上上进进行行。为为了了便便于于计计算算机机计计算算，下下面面介介绍绍Dijkstra的表上算法。的表上算法。给给定定一一个个赋赋权权图图G，可可以以相相应应地地定定义义一一个个邻邻接接矩矩阵阵A=(wij)，其其中中wij是是连接顶点连接顶点vi和和vj的权的权;若若vi vj不是不是G的边，则令的边，则令 wij 等于无穷大。等于无穷大。第59页，此课件共131页哦Step0：画画掉掉第第一一列列的的所所有有元元素素（例例如如打打上上 ），并并在在第第一一行行的每个元素下面画一横线。的每个元素下面画一横线。Step1：在在画画横横线线的的元元素素中中找找一一个个最最小小的的w ij，用用圆圆圈圈起起来来，把把第第j列列其其他元素画掉，并把第他元素画掉，并把第j行没有画掉的元素画上横线。行没有画掉的元素画上横线。Step2：如如果果还还有有没没有有圈圈起起来来和和没没有有画画掉掉的的元元素素，则则返返回回Step1；否否则则，结结束束。这这时时圈圈起起来来的的元元素素代代表表最最小小树树的的边边，所所有有圈圈起起来来的的元素之和就是最小树的权。元素之和就是最小树的权。最小树算法最小树算法-4-表上作业法表上作业法第60页，此课件共131页哦算例算例用表上作业法求图用表上作业法求图7-19的最小树的过程为：的最小树的过程为：最小对的权最小对的权=1+2+3+2=8。v1v2v4v5v312244342第61页，此课件共131页哦第62页，此课件共131页哦最小连接问题最小连接问题作作为为最最小小树树的的应应用用问问题题之之一一是是所所谓谓的的连连接接问问题题：欲欲建建造造一一个个连连接接若若干干城城镇镇（矿矿区区或或工工业业区区）的的铁铁路路网网，给给定定城城镇镇i和和j之之间间直直通通线线路路的的造价为造价为cij，试设计一个总造价最小的铁路运输图。，试设计一个总造价最小的铁路运输图。v把每个城镇看作是具有权把每个城镇看作是具有权cij的赋权图的赋权图G的一个顶点。显然连接的一个顶点。显然连接问题可以表述成：在赋权图问题可以表述成：在赋权图G中，求出具有最小权的支撑树。中，求出具有最小权的支撑树。第63页，此课件共131页哦10.3 最短路问题最短路问题vDijkstra算法算法v求任意两点的最短路算法求任意两点的最短路算法-Floyd算法算法v求带负权网络图的最短路的算法求带负权网络图的最短路的算法v用线性规划求最短路用线性规划求最短路第64页，此课件共131页哦赋权图赋权图v给定赋权图的一个子图给定赋权图的一个子图H，定义，定义H的权为的权为H的所有边权的总和。的所有边权的总和。v对图对图G的每条边的每条边e，赋予一实数，赋予一实数(e)，称为边，称为边e的权，可得一的权，可得一赋权图。赋权图。SDBTCEA712244731555第65页，此课件共131页哦v赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。v在一个赋权图在一个赋权图G上，给定两个顶点上，给定两个顶点u和和 v，所谓，所谓u和和 v最短最短 路是指所有连接顶点路是指所有连接顶点u和和 v 的路中路长最短的路；的路中路长最短的路；vu和和v最短路的路长也称为最短路的路长也称为u和和 v的距离。的距离。SDBTCEA712244731555v如何求从如何求从u到到v的的最短路的长？最短路的长？第66页，此课件共131页哦vDijkstra算法的基本思想：算法的基本思想：(1)u0u1P设设S是是V的真子集，的真子集，如果如果 是从是从u0 到的最短路，到的最短路，则则，并且，并且P的的 段是最短的段是最短的 路，所以路，所以第67页，此课件共131页哦算法标号算法标号v令令dij表示连接顶点表示连接顶点vi与顶点与顶点vj边上的权，即边上的权，即(1)公式（公式（1）是）是Dijkstra算法的基础。算法的基础。第68页，此课件共131页哦定义结点定义结点vj 的标号为的标号为始点的标号为始点的标号为0,-,表明这个点前面没有点。表明这个点前面没有点。结点结点vj 的标号分为两种：的标号分为两种：临时性标号和永久性标号临时性标号和永久性标号。如果找到。如果找到一条更短的路，临时性标号即被修改，如果找不到一条更短一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。的路，临时性标号即被改为永久性标号。第69页，此课件共131页哦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)如果所有的结点都是永久性标号，停止。否则选择最小的临如果所有的结点都是永久性标号，停止。否则选择最小的临时性标号时性标号 lr,s。令令 i=r，返回返回Step i.第70页，此课件共131页哦计算实例计算实例求连接求连接S、T的最短路的最短路SDBTCEA712244731555第71页，此课件共131页哦SDBTCEA7122447315550第72页，此课件共131页哦SDBTCEA71224473155505，s4，s2，s2，s第73页，此课件共131页哦SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s第74页，此课件共131页哦SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C第75页，此课件共131页哦SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B 7，B第76页，此课件共131页哦SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E第77页，此课件共131页哦lST=13;S-T最短路为最短路为SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第78页，此课件共131页哦实例评述实例评述vDijkstra算法不仅找到了所求最短路，而且找到了从算法不仅找到了所求最短路，而且找到了从S点点到其他所有顶点的最短路；这些最短路构成了图的一个连到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。通无圈的支撑子图，即图的一个支撑树。SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第79页，此课件共131页哦注注:Dijkstra算法只适用于所有算法只适用于所有wij0的情形，当赋权有向图中存在负权的情形，当赋权有向图中存在负权时，算法失效。如时，算法失效。如v1v2v3 12-3用用Dijkstra算法可以得出从算法可以得出从v1到到v2的最短路的权是的最短路的权是1，但实际上从，但实际上从v1到到v2的最短路是（的最短路是（v1，v3，v2），权是），权是-1。第80页，此课件共131页哦下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任一点到任一点vj都有一条弧（如果在都有一条弧（如果在D中，（中，（vi，vj）A，则添加弧（，则添加弧（vi，vj）令）令wij=+）。）。显然，从显然，从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi，再，再沿（沿（vi，vj）到）到vj的，由前面的结论可知，从的，由前面的结论可知，从vs到到vi的这条路的这条路必定是从必定是从vs到到vi的最短路，所以的最短路，所以d（vs，vj）必满足如下方程：）必满足如下方程：第81页，此课件共131页哦第82页，此课件共131页哦6-1-3-283-52-111-1217-3-5例：求例：求v1到各点的最短路。到各点的最短路。第83页，此课件共131页哦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-5066第84页，此课件共131页哦v例一个连接例一个连接11个城镇的交通图以及城市个城镇的交通图以及城市u与与v之间的一条最短之间的一条最短路。（粗线表示）路。（粗线表示）uv第85页，此课件共131页哦uv第86页，此课件共131页哦求任意两点的最短路算法求任意两点的最短路算法-Floyd算法算法这种算法用一个这种算法用一个n阶方阵来表示一个阶方阵来表示一个n-结点网络结点网络.矩阵中的矩阵中的(i,j)-元元 dij 表示从表示从 i 到到 j边上的权边上的权,即即第87页，此课件共131页哦ijkFloyds algorithm 的基本思想：给定结点的基本思想：给定结点 i,j 和和 k，若有如，若有如下三角形，且下三角形，且 ，则从，则从i经过经过 k到到j 比直接到比直接到j所经所经过路线短。过路线短。此时用此时用ikj 代替代替ij最好最好.-三角形运算三角形运算第88页，此课件共131页哦第89页，此课件共131页哦1245335461510 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5 1 2 3 4 523451345124512351234第90页，此课件共131页哦 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第91页，此课件共131页哦 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第92页，此课件共131页哦 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第93页，此课件共131页哦 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 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 5第94页，此课件共131页哦 1 2 3 4 53108123115910116108564129104 1 2 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 512453354615101245第95页，此课件共131页哦用线性规划求最短路用线性规划求最短路124531001550106030求从求从1到到2的最短路的最短路20第96页，此课件共131页哦10.4 网络最大流问题网络最大流问题第97页，此课件共131页哦vsv1v3v4v2vt322223111网络流图网络流图设设D=(V,A,W)是一个有向网络。是一个有向网络。vs是网络的源点，是网络的源点，vt是网络的是网络的汇点。汇点。弧上的数字是允许通过的最大流量弧上的数字是允许通过的最大流量。第98页，此课件共131页哦可行流可行流设设f是定义在弧集是定义在弧集A上的一个函数，如果对所有弧上的一个函数，如果对所有弧 a 成立成立并且对所有并且对所有中间顶点中间顶点 v 成立成立其中，其中，f+(v)是流出是流出v 的流量，的流量，f -(v)是流入是流入v的流量。的流量。则称则称 f 是网络是网络D上的一个可行流。上的一个可行流。2,1vsv1v3v4v2vt3,12,12,22,13,21,01,01,1-容量限制容量限制-守恒条件守恒条件第99页，此课件共131页哦流值流值对于源点对于源点vs和汇点和汇点vt，流出源点，流出源点vs的流量等于流入汇点的流量等于流入汇点vt的的流量，称之为流流量，称之为流 f 的值，记为的值，记为val f。即即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1val f=3第100页，此课件共131页哦最大流最大流网络最大流是指给定网络上的流值最大的一个可行流。网络最大流是指给定网络上的流值最大的一个可行流。寻找给定网络的最大流及其有效算法是网络规划的一个重要问寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。题。Ford 与与 Fulkerson 在在1957年提出一个求解网络最大流问题年提出一个求解网络最大流问题的算法，称为的算法，称为Ford Fulkerson 算法。算法。第101页，此课件共131页哦割集割集v设设S是网络的顶点子集，且是网络的顶点子集，且割集的容量定义为割集的容量定义为最小割是指容量最小的割。最小割是指容量最小的割。定义定义D的一个割集，简称割为的一个割集，简称割为vsv1v3v4v2vt322223111第102页，此课件共131页哦定理定理1对于网络的任意流对于网络的任意流 f 和割和割 成立成立证明证明 由定义可知由定义可知第103页，此课件共131页哦推论推论1 对于网络的任意流对于网络的任意流 f 和割和割 ，成立成立vsv1v3v4v2vt322223111第104页，此课件共131页哦注：推论注：推论2的逆命题也成立，即推论中的等式永远成立。称为的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。最大流最小割定理，是网络理论的一个重要定理。则则f 是最大流，是最大流，K是最小割。是最小割。如果成立如果成立推论推论2 设设 f 是网络的一个可行流，是网络的一个可行流，是网络的一个割，是网络的一个割，第105页，此课件共131页哦链、正向弧、反向弧链、正向弧、反向弧 v设设P是网络是网络D的一条链，则的一条链，则P中的弧可分为两类：中的弧可分为两类：v正向弧正向弧弧的方向与弧的方向与P的走向一致；记为的走向一致；记为P+。v反向弧反向弧弧的方向与弧的方向与P的走向相反的走向相反;记为记为P-。网络网络D的连接源点的连接源点vs和汇点和汇点vt的路。的路。vsv1v3v4v2vt322223111第106页，此课件共131页哦增广链增广链v设设P是网络是网络D的一条连接源点的一条连接源点vs和汇点和汇点vt的链，的链，f 是网络是网络D上的一个可行流上的一个可行流.v如果如果P的每一正向弧都是的每一正向弧都是不饱和弧不饱和弧，而而P的每一反向弧的流量都为正的每一反向弧的流量都为正；v则称则称P是网络是网络D的关于可行流的关于可行流f 的一条可增广链。简称增广链。的一条可增广链。简称增广链。可增广链上流量可以增加。可增广链上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,21,01,11,0第107页，此课件共131页哦定理定理2v设设f 是网络是网络D上的一个可行流，则上的一个可行流，则 f 是一个最大流当且仅当是一个最大流当且仅当网络网络D不存在不存在f 的增广链。的增广链。证明证明 （必要性）（必要性）设设f 是一个最大流，假如是一个最大流，假如D中存在中存在f 的增广链的增广链P,则可以得到一则可以得到一个流值更大的流个流值更大的流f 1,使得使得v构造过程如下：构造过程如下：其中其中第108页，此课件共131页哦证明证明v充分性充分性设网络设网络D不存在不存在f 的增广链。定义的增广链。定义S如下：如下：从而从而 是是D的割集，进而可得的割集，进而可得 中的弧都是饱和弧，而中的弧都是饱和弧，而 中的弧都是中的弧都是0流弧，流弧，否则将产生网络否则将产生网络D 的一条增