运筹学图与网络优化.ppt

《运筹学图与网络优化.ppt》由会员分享，可在线阅读，更多相关《运筹学图与网络优化.ppt（131页珍藏版）》请在三一办公上搜索。

1、第十章 图与网络优化,图论概述,图论(Graph Theory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。,如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。,网络规划概述,网络规划(Network Programming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。,七桥问题,七桥问题图形,原 理 及 方 法,七桥问题是图论中的著名问题。1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有

2、顶点连接奇数条边。,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是一个图，,图的几何实现,一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。,图的几何实现有助与我们直观的了解图的许多性质。,说明,一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关

3、系。我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。,几何实现图例,在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图 中，它共有4个顶点，6条边；而e 3 与e 4 的交点不是这个图的顶点。,平面图,一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。,基本概念,端点重合为一点的边称为环。连接同一对顶点的多条边称为多重边。在右图中，e5 是一个环，e1 与e2 是多重边，v1和e1,e2,e3是关联的，v1与v2,v3是邻接的。,邻接矩阵,设

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

5、,2,2,2,4+3+3+4=14=27,关联矩阵性质,图G的关联矩阵M=(mij)为mn矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于2。,因此，图G的关联矩阵M所有元素之和既等于所有顶点的度之和，又等于边数的2倍。,定理设G是一个图，则,推论,图中奇点的数目为偶数。,证明,记,简单图,一个图称为简单图，如果它既没有环也没有多重边。下图是简单图。本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。,只有一个顶点的图称为平凡图；,边集是空集的图称为空图。,同构,称G和H是同构的，记为，,使得,给定两个图,如果存在两个一一对应,同构图例,图G与图H是同构的。,v1,v2,v3,v4,

6、u1,u2,u3,u4,G,H,e6,e4,e2,e1,e3,e5,f1,f2,f6,f3,f5,f4,完全图Kn,完全图是每一对不同顶点都恰有一边的简单图；具有n个顶点的完全图记为Kn.,K5,二分图,二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y;(X,Y)也称为图的二分划。,x1,x2,x3,y1,y2,y3,完全二分图,完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连；记为Km,n，其中,K3,3,特殊图例,K5,K 3,3,都是极小的非平面图,子图,称图H是图G的子图，,图G及其基本图,称H是G的支撑子图，

7、,如果,称H是G的真子图，,若,如果,表示关联函数,记为,在H的限制。,顶点导出子图,设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为GW。导出子图GV-w记为G-W，即 它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。如果W仅含一个顶点v，则把 简记为。,边导出子图,设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为GF。记G-F表示以E(G)F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。如F=e，则记。,子图图例,v1

8、,v2,v3,v4,v5,e1,e3,e2,G,v1,v2,v3,v4,v5,G的支撑子图G-e1,e 2,e 3,子图图例2,v2,v3,v4,e2,G-v 1,v 5,v1,v2,v5,Gv 1,v 2,v 5,v1,v2,v3,v4,e1,e3,e2,G e1,e 2,e 3,v1,v2,v3,v4,v5,e1,e3,e2,G,途径,顶点vk叫W的终点，顶点v0 称为W的起点，顶点vi 叫W的内部顶点，整数k称为W的长度。在简单图中，径可由顶点序列表示。,图G的一个有限的点边交错序列称为从v0到vk的途径。,其中vi与vi+1是边ei的顶点;,路、链,如果径W的边不相同，则称W为一条链，

9、,如果W顶点互不相同，则称W是一条路。,链长是W中边的个数k。,记路长,u,v,w,x,y,a,b,d,e,f,g,h,路：xcwhyeuav链：wcxdyhwbvgy,c,圈(回路),如果途径W的起点和终点相同且有正长度，则称它是一个闭途径；如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。,圈：uavbwhyeu,u,v,w,x,y,a,b,d,e,f,g,h,c,定理,一个图是二分图当且仅当图中不存在奇圈。,Euler圈,Euler圈是指过所有边一次且恰好一次的闭途径。Euler链是指过所有边一次且恰好一次的链。,Euler链:yd

10、xcwheuavfygvbw,u,v,w,x,y,a,b,d,e,f,g,h,c,图例,下例给出了一个图的径，链和路。径：uavfyfvgyhwbv链：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler链:ydxcwheuavfygvbw,u,v,w,x,y,a,b,d,e,f,g,h,c,Euler型定理,定理2设G是连通圈，则G是Euler型的充要条件是G没有奇次数的顶点。推论1设G是一个连通图，则G有Euler链当且仅当G最多有两个奇数次数的顶点。,连通性,图G称为连通的，如果在G的任意两个顶点u和v中存在一条(u,v)路。,不连通图至少有两个连通分支。,两点顶

11、点u和v等价当且仅当u和v中存在一条(u,v)路。,表示G的连通分支数。,10.2 树,树（tree）是一个不包含圈的简单连通图。具有k个连通分支的不包含圈的图称为k-树，或森林。,下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。,性质,1设G是一棵树，则：G中任意两点均有唯一的路连接。2 G的边数等于顶点数减1，即3 若G不是平凡图，则G至少有两个次数为1的顶点。,定理1,设G是一个简单图，则下列六个命题是等价的。G是一棵树。无圈且m=n-1。G连通且m=n-1。G连通并且每条边都是割边。G中任意两点都有唯一的路相连。G无圈，但在任意

12、一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。,支撑树,图G的支撑树是G的支撑子图，并且是一棵树。每个连通图都有支撑树支撑树也称为连通图的极小连通支撑子图。很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。,定理,定理4设T1 和T2 是G的两个支撑树，令 则T1 经过k次迭代后可得到T2。,定理2设G是一个连通图，T是G的一棵支撑树，e是G的一条不属于T的边，则T+e含有G的唯一圈。,定理3设T是连通图G的一棵支撑树，e是T的任意一条边，则：,（2）包含G的唯一的割集。,最小树,定理5设T是G的一个支撑树，则T是G的最小树的充分必要条件为对任意边,设G是一个赋权图，T为G的一

13、个支撑树。定义T的权为：,G中权最小的支撑树称为G的最小树。,定理6,设T是G的支撑树，则T是G的最小树的充分必要条件为对任意边，,其中 为G的唯一割集。,最小树算法-1-贪心算法,Kruskal在1965年提出一种求最小树的所谓贪心算法。算法步骤如下,Step0 把边按权的大小从小到大排列得：,置,Step1 若，则停，此时GS即为所求的最小树；否则，转向Step2。,Step2 如果 GS+e j不构成回路，则令,转向Step1；否则，令j=j+1转向Step2。,算例,图7-18展示了利用Kruskal算法求最小树的迭代过程。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2

14、,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-18,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-18-1,评注,Kruskal算法的总计算量为，有效性不太好。求最小树的一个好的算法是Dijkstra于1959年提出的，算法的实质是在图的 个独立割集中，取每个割集的一条极小边来构成最小树。,最小树算法-2-Dijkstra算法,Step0 置,Step1 取,置,Step2 若，则停止；,否则，置，返回Step1,算例2,图7-19展示了利用Dijkstra算法求最小树的迭代过程。,v1

15、,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-19,利用Dijkstra算法求最小树的迭代过程。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-19-1,破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。Step1 若G不含圈，则停止；否则在G中找一个圈C，取圈C的一条边e，满足,最小树算法-3-破圈法,Step2：置 G=G-e，返回Step1。利用破圈法求图7-19的

16、最小树的过程如图7-20所示。,算例3,图7-20展示了利用破圈法求最小树的迭代过程。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-20,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-20-1,评注,上述算法都可以在图上进行。为了便于计算机计算，下面介绍Dijkstra的表上算法。给定一个赋权图G，可以相应地定义一个邻接矩阵A=(wij)，其中wij是连接顶点vi和vj的权;若vi vj不是G的边，则令 wij 等于无穷大。,

17、Step0：画掉第一列的所有元素（例如打上），并在第一行的每个元素下面画一横线。Step1：在画横线的元素中找一个最小的w ij，用圆圈起来，把第j列其他元素画掉，并把第j行没有画掉的元素画上横线。Step2：如果还有没有圈起来和没有画掉的元素，则返回Step1；否则，结束。这时圈起来的元素代表最小树的边，所有圈起来的元素之和就是最小树的权。,最小树算法-4-表上作业法,算例,用表上作业法求图7-19的最小树的过程为：最小对的权=1+2+3+2=8。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,最小连接问题,作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿

18、区或工业区）的铁路网，给定城镇i和j之间直通线路的造价为cij，试设计一个总造价最小的铁路运输图。把每个城镇看作是具有权cij的赋权图G的一个顶点。显然连接问题可以表述成：在赋权图G中，求出具有最小权的支撑树。,10.3 最短路问题,Dijkstra算法,求任意两点的最短路算法-Floyd算法,求带负权网络图的最短路的算法,用线性规划求最短路,赋权图,给定赋权图的一个子图H，定义H的权为H的所有边权的总和。,对图G的每条边e，赋予一实数(e)，称为边e的权，可得一赋权图。,赋权图中一条路的权称为路长。,在一个赋权图G上，给定两个顶点u和 v，所谓u和 v最短 路是指所有连接顶点u和 v 的路中

19、路长最短的路；,u和v最短路的路长也称为u和 v的距离。,如何求从u到v的最短路的长？,Dijkstra算法的基本思想：,(1),u0,u1,P,设S是V的真子集，,如果 是从u0 到的最短路，,则，并且P的 段是最短的 路，所以,算法标号,令dij表示连接顶点vi与顶点vj边上的权，即,(1),公式（1）是Dijkstra算法的基础。,定义结点vj 的标号为,始点的标号为0,-,表明这个点前面没有点。,结点vj 的标号分为两种：临时性标号和永久性标号。如果找到一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。,Step0 令始点的标号为0,-.令i=1,

20、Step 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.,计算实例,求连接S、T的最短路,0,0,5，s,4，s,2，s,2，s,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A

21、,8，C,7，B,7，B,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,lST=13;S-T最短路为SABEDT,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,13，D,实例评述,Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,13，D,注

22、:,Dijkstra算法只适用于所有wij0的情形，当赋权有向图中存在负权时，算法失效。如,用Dijkstra算法可以得出从v1到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的这条路必定是从vs到vi的最短路，所以d（vs，vj）必满足如下方程：,6,-1,-3,-2,8,3,-

23、5,2,-1,1,1,-1,2,1,7,-3,-5,例：求v1到各点的最短路。,例一个连接11个城镇的交通图以及城市u与v之间的一条最短路。（粗线表示）,u,v,u,v,求任意两点的最短路算法-Floyd算法,这种算法用一个n阶方阵来表示一个n-结点网络.矩阵中的(i,j)-元 dij 表示从 i 到 j边上的权,即,i,j,k,Floyds algorithm 的基本思想：给定结点 i,j 和 k，若有如下三角形，且，则从i经过 k到j 比直接到j所经过路线短。,此时用ikj 代替ij最好.-三角形运算,1,2,4,5,3,3,5,4,6,15,10,1 2 3 4 5,1 2 3 4 5,

24、1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,1,2,4,5,3,3,5,4,6,15,10,1245,用线性规划求最短路,1,2,4,5,3,100,15,50,10,60,30,求从1到2的最短路,20,10.4 网络最大流问题,vs,v1,v3,v4,v2,vt,3,2,2,2,2,3,1,1,1,网络流图,设D=(V,A,W)是一个有向网络。vs是网络的源点，vt是网络的汇点。,弧上的数字是允许通过的最大流量。,可行流,设f是定义在弧集A上的一个函数，如果对所有弧 a 成立,并且对所有中间顶点 v 成立,其中，f+(v)是流出v 的流量，f-(v)是流

25、入v的流量。,则称 f 是网络D上的一个可行流。,-容量限制,-守恒条件,流值,对于源点vs和汇点vt，流出源点vs的流量等于流入汇点vt的流量，称之为流 f 的值，记为val f。即,val f=3,最大流,网络最大流是指给定网络上的流值最大的一个可行流。,寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。,Ford 与 Fulkerson 在1957年提出一个求解网络最大流问题的算法，称为Ford Fulkerson 算法。,割集,设S是网络的顶点子集，且,割集的容量定义为,最小割是指容量最小的割。,定义D的一个割集，简称割为,vs,v1,v3,v4,v2,vt,3,2,2,2,2

26、,3,1,1,1,定理1,对于网络的任意流 f 和割 成立,证明 由定义可知,推论1 对于网络的任意流 f 和割，成立,vs,v1,v3,v4,v2,vt,3,2,2,2,2,3,1,1,1,注：推论2的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。,则f 是最大流，K是最小割。,如果成立,推论2 设 f 是网络的一个可行流，是网络的一个割，,链、正向弧、反向弧,设P是网络D的一条链，则P中的弧可分为两类：正向弧弧的方向与P的走向一致；记为P+。反向弧弧的方向与P的走向相反;记为P-。,网络D的连接源点vs和汇点vt的路。,vs,v1,v3,v4,v2,

27、vt,3,2,2,2,2,3,1,1,1,增广链,设P是网络D的一条连接源点vs和汇点vt的链，f 是网络D上的一个可行流.,如果P的每一正向弧都是不饱和弧，,而P的每一反向弧的流量都为正；,则称P是网络D的关于可行流f 的一条可增广链。简称增广链。,可增广链上流量可以增加。,定理2,设f 是网络D上的一个可行流，则 f 是一个最大流当且仅当网络D不存在f 的增广链。,证明（必要性）设f 是一个最大流，假如D中存在f 的增广链P,则可以得到一个流值更大的流f 1,使得,构造过程如下：,其中,证明,充分性,设网络D不存在f 的增广链。定义S如下：,从而 是D的割集，进而可得,中的弧都是饱和弧，而

28、 中的弧都是0流弧，否则将产生网络D 的一条增广链。因此，f 的流值等于割集 的割量，所以，f是一个最大流。,定理3,在任何网络流图中，最大流的值等于最小割的容量。,（最大流最小割定理）,Ford Fulkerson 算法,Ford Fulkerson 算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。,定理的证明过程蕴涵着最大流算法,算例,求下面网络的最大流,初始0流,先给网络赋一个初始0流f 0,图4.2-1,(+vs,8),(+vs,2),(-,),寻找增广链1,vs,v1,v3,v4,v2,vt,8,

29、0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,vs,v1,v3,v4,v2,vt,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+vs,8),(+vs,2),(-,),(+v1,5),(+v3,2),寻找增广链2,vs,v1,v3,v4,v2,vt,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+vs,8),(+vs,2),(-,),(+v1,5),(+v3,2),(+v2,5),寻找增广链3,寻找增广链4,找到流f 0 的增广链P0=vs v1 v2 vt.,vs,v1,v3,v4,v2,v

30、t,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+vs,8),(+vs,2),(-,),(+v1,5),(+v3,2),(+v2,5),增量=5.,调整流值2,调整流值得流值为5的新可行流f 1，,vs,v1,v3,v4,v2,vt,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+vs,3),(+vs,2),(-,),vs,v1,v3,v4,v2,vt,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+vs,3),(+vs,2),(-,),(+v3,2),(+v3,2),vs,v1,v3

31、,v4,v2,vt,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+vs,3),(+vs,2),(-,),(+v3,2),(+v3,2),(+v2,2),增量=2.,vs,v1,v3,v4,v2,vt,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+vs,3),(+vs,2),(-,),(+v3,2),(+v3,2),(+v2,2),找到流f 1 的增广链P0=vs v3 v2 vt，,调整流值3,调整流值得流值为7的新可行流f 2，,vs,v1,v3,v4,v2,vt,8,5,5,5,2,2,8,0,7,0,9,7,6,

32、0,6,0,5,2,3,0,(+vs,3),(+v1,3),(-,),(+v3,3),(+v3,3),(+v2,2),增量=2.,vs,v1,v3,v4,v2,vt,8,7,5,5,2,2,8,0,7,0,9,9,6,2,6,0,5,4,3,0,(+vs,1),(+v1,1),(-,),(+v3,1),(+v3,1),(+v4,1),增量=1.,vs,v1,v3,v4,v2,vt,8,8,5,5,2,2,8,1,7,1,9,9,6,3,6,0,5,4,3,0,(-,),寻找增广链,利用标号法得不出流f 3 的增广链，因此，f 3 是给定网络的最大流，流值为10。令S=vs,则 是最小割。,Fo

33、rd Fulkerson 算法,Step0 先给网络赋一个初始0流f 0;给vs标(-,+)Step1 寻找流f 的增广链(1.1)如果所有标号点已经检查且汇点未标号，转Step3；(1.2)找一个已标号但未检查的点vi 做如下检查：对每个弧e=(vi,vk),如果vk 未标号且,则给vk标号(+vi,l(k),其中,Ford Fulkerson 算法,对每个 弧e=(vk,vi),如果vk 未标号且 则给v k标号(-vi,l(k),其中,Step2 增广网络流 从源点vs开始依据标号构造增广链P，并调整流值，标号的正负表示增加或减少相应弧的流值；擦去所 有标号，转Step1.,(1.3)若汇点vt已标号，转Step2;否则转(1.1).,Step3 令S表示所有已标号点，则得最小割，相应流为 最大流，结束。,1,2,3,5,4,6,8,5,2,8,7,9,6,6,5,3,Linear Programming of Maximal Flow Mode,