运筹学七图与网络分析

1、第八章,图与网络分析,A,B,C,D,哥尼斯堡“七桥”难题,1736年，数学家欧拉把该问题归结为下图：,A,B,C,D,主要内容：,第一节 图与网络的基本知识 第二节 树 第三节 最短路问题 第四节 最大流问题 第五节 最小费用流问题,第一节,图与网络的基本知识,一、图与网络的基本概念,1.图及其分类,图：是由点集V=vi和V中元素的无序对的一个集合E=ek所构成的二元组，记为：G=（V,E）。,V中的元素vi叫做顶点，E中的元素ek叫做边。,m（G）=|E|称为G中的边数，简记为m； n（G）=|V|称为G中的顶点个数，简记为n。,完全图：每一对顶点都有边相连的无向简单图称为完全图。,有n个

2、顶点的无向完全图记为Kn。,有向完全图：每一对顶点间有且仅有一条有向边的简单图。,二部图：图G（V,E）的点集V可以分为两个非空子集X,Y，即XY=V，XY=，使得E中每条边的两个端点必有一个属于X，另外一个属于Y，则称G为二部图。,2.顶点的次,顶点的次：以点v为端点的边数叫做点v的次，简记为d(v)。,悬挂点,孤立点,奇点,偶点,定理1：任何图中，顶点次数的总和等于边数的2倍。,定理2：任何图中，次为奇数的顶点必为偶数个。,出次：有向图中，以点vi为始点的边数叫做点vi的出次，简记为d+(vi)。,入次：有向图中，以点vi为终点的边数叫做点vi的入次，简记为d-(vi)。,vi点的出次和入

3、次之和就是该点的次。,有向图中，所有顶点的入次之和等于所有顶点的初次之和。,3.子图,4.网络,子图：图G =（V,E)，若E是E的子集，V是V的子集，且E中的边仅与V中的顶点相关联，则称G=(V,E)是G的一个子图。,生成子图（支撑子图）：若G=(V,E)是G的一个子图，且有V=V，则G是G的一个生成子图。,点或边带有某种数量指标的图称为网络（赋权图）。,二、连通图,链：如v1,e1,v2,e6,v4,e7,v3,e3,v2,e5,v5；,初等链：,圈：,初等圈：,如v1,e1,v2,e6,v4,e10,v6,e9,v5；,如v1,e1,v2,e5,v5,e8,v4,e6,v2,e3,v3，

4、e2，v1；,如v1,e1,v2,e6,v4,e7,v3，e2，v1.,道路：有向图中，链上的边方向相同时，称为道路。,回路：有向图中，圈上的边方向相同时，称为回路。,连通图：一个图中任意两点间至少有一条链相连，则称此图为连通图。,如：v1,e2,v3,e7,v4,e8,v5是一条道路； v1,e1,v2,e5,v5,e8,v4是一条链但不是一条道路。,e1,e2,e3,e4,e5,e6,e7,e8,如：v1,e2,v3,e4,v2,e1,v1是一条回路； v1,e1,v2,e6,v4,e7,v3，e2，v1是圈但不是一条回路。,每一个连通图都可以分为若干个连通子图。,三、图的矩阵表示,有权矩

5、阵：网络（赋权图）G=（V,E），|V|=n，其边(vi,vj)有权wij，构造矩阵A=（aij）nn ，其中：,称矩阵A为网络G的有权矩阵。,邻接矩阵：图G=（V,E），|V|=n，构造矩阵A=（aij）nn ，其中：,称矩阵A为图G的邻接矩阵。,四、欧拉回路与中国邮路问题,1.欧拉回路与道路,欧拉道路：连通图G中，若存在一条道路，经过每边一次且仅一次，则称该道路为欧拉道路。,欧拉回路：连通图G中，若存在一条回路，经过每边一次且仅一次，则称该回路为欧拉回路。,欧拉图：具有欧拉回路的图称为欧拉图。,定理3：无向连通图G是欧拉图，当且仅当G中无奇点。,推论1：无向连通图G是欧拉图，当且仅当G的边

6、集可划分为若干个初等回路。,推论2：无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。,定理4：连通有向图G是欧拉图，当且仅当它的每个顶点的出次等于入次。,2.中国邮路问题,一个邮递员，负责某一地区的信件投递。他每天从邮局出发，走遍该地区所有街道再返回邮局，如何安排送信的路线可以使所走的总路程最短？,G图中若无奇点，则G是一个欧拉图，按欧拉回路走即可。,G图中若有奇点，必然有某些边不止走一次，相当于给G图中某些边增加一些重复边，使得到的新图G无奇点且满足总路程最短。,分析：此问题可归结为：给定一个连通图G，每边有非负权数 ，要求一条回路过每边至少一次，且满足总权最小。,又可以转化为如下问题：在

7、连通图G(V,E)中，求一个边集 ,把G中属于E1的边均变为二重边，得到的新图G=G+E1，且， 最小。,要满足该条件，则有：对G中的初等圈来讲，重复边的长度和不超过圈长的一半。,第二节,树,一、树的概念和性质,树叶,分枝点,连通且不含圈的无向图称为树。,树中次为1的点称为树叶,树中次大于1的点称为分枝点,1、概念,图T=（V,E），|V|=n，|E|=m，则下列关于树的说法是等价的：,（1）T是一个树；,2、关于树的性质的定理,（2）T无圈，且m=n-1；,（3）T连通，且m=n-1；,（4）T无圈，但每加一新边即得唯一一个圈；,（5）T连通，但任舍去一个边就不连通；,（6）T中任意两点之间

8、，有惟一链相连。,二、图的生成树,若图G的生成子图是一棵树，则称该树为G的生成树（支撑树）。简称为图G的树。,1、定义,v1,图G=（V，E）有生成树的充分必要条件是G为连通图。,定理：,2、寻找支撑树的方法,（1）破圈法,（2）避圈法（加边法）,深探法,广探法,破 圈 法 示 例,(1),(2),(3),(4),v5,v6,v2,v3,v4,v1,破 圈 法 示 例,(5),避圈法示例见课本P255.,三、图的最小生成树,连通图G=（V，E），每条边上有非负权L（e）。一棵生成树所有树枝上的权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树（最小支撑数），简称最小树。,1、定义,

9、2、寻找最小生成树的方法,（1）Kruskal法（避圈法）,每步从未选的边中选取边e，使它与已选的边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。,（2）破圈法,在图中任取一圈，去掉最大权边，重复此操作，直到无圈。,4,3,6,2,1,Kruskal法 示 例,V1,V2,V3,V4,V5,V6,8,5,4,3,6,7,8,3,2,1,破 圈 法 示 例,第三节,最 短 路 问 题,一、最短路问题,最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。,最短路径问题的一般

10、提法如下： 设G=（V，E）为连通图，图中各边都有权，vs,vt为图中两个顶点，求一条道路，使它是从vs到vt所有道路中总权最小的道路。,最短路径问题的求解方法： Dijkstra算法求解图中指定点vs到其它任意点的最短路，图中所有边的权为非负数。 逐次逼近算法求解图中指定点vs到其它任意点的最短距离，图中的边可以为负数。 Floyd算法求解图中任意两点之间的最短距离。,二、Dijkstra算法,步骤： （1）给初始点vs以P标号，P(vs)=0，其余点为T标号，T（vi）=+。 （2）若vi为刚得到P标号的点，考虑这样的点vj: (vi,vj)属于E，且vj为T标号。对vj的T标号进行如下修

11、改： T(vj)=minT(vj)，P(vi)+lij （3）比较所有具有T标号的点，把最小者该为P标号。返回步骤（2），直到vt为P标号为止。,求指定点vs到其他任意点vt的最短路。,（1）给v1以P标号，P（v1）=0， 给其余点以T标号，T（vi）=+ （i=2，7）,（2）考察点v1，由于（v1，v2），（v1，v3），（v1，v4）属于E，且v2，v3，v4为T标号，因此修改这三个点的标号:,（3）比较所有T标号，T（v2）最小，因此令P（v2）=6，并记录路径（v1，v2）。,（4）考察点v2，由于（v2，v3），（v2，v5）属于E，且v3，v5为T标号，因此修改这两个点的标号:

12、,（5）比较所有T标号，T（v3）最小，因此令P（v3）=9，并记录路径（v2，v3）。,（6）考察点v3，由于(v3，v4)，(v3，v5)，(v3，v6)属于E，且v4，v5，v6为T标号，因此修改这三个点的标号：,（7）比较所有T标号，T（v4）最小，因此令P（v4）=12，且记录路径（v1，v4）。,（9）比较所有T标号，T（v6）最小，因此令P（v6）=16，记录路径（v3，v6）。,（8）考察点v4，由于（v4，v6）属于E，且v6为T标号，因此修改这一个点的标号：,（10）考察点v6，由于（v6，v5），（v6，v7）属于E，且v5，v7为T标号，因此修改这两个点的标号：,（11

13、）比较所有T标号，T（v5）最小，因此令P（v5）=18，记录路径（v3，v5）。,（12）考察点v5，由于（v5，v7）属于E，且v7为T标号，因此修改这个点的标号：,（13）因为只有一个T标号，所以令P（v7）=29，记录路径（v5,v7）。,所以，最短路为v1v2 v3 v5 v7，距离为29。,三、逐次逼近法,求指定点v1到其他任意点vt的最短路（边的权可以为负） 步骤： （1）令 （2） （3）当进行到第t步时，若出现 则停止， 即为v1到各点的最短路长。,求下图中v1到其他所有点的最短路：,（1）当k=1时，,（2）当k=2时，,（0）,（2）,（5）,（-3）,（+）,（+）,（

14、+）,（+）,（3）当k=3时，,（0）,（2）,（0）,（-3）,（6）,（+）,（+）,（11）,（4）当k=4时，,（0）,（2）,（0）,（-3）,（6）,（15）,（+）,（6）,（5）当k=5时，,（0）,（2）,（0）,（-3）,（3）,（10）,（14）,（6）,（6）当k=6时，,（0）,（2）,（0）,（-3）,（10）,（9）,（6）,（3）,逆推法推出v1到vt的最短路，如考察v1到v7的最短路，依次找到点v8,v6,v3,v2,v1。,四、Floyd算法,求网络上任意两点间的最短路。,令网络的权矩阵为：,算法的基本步骤为：,（1）输入权矩阵,（2）计算,其中,（3）

15、中元素 就是 到 的最短路长。,求下图中任意两点间的最短路：,五、最短路问题的应用举例,1.设备更新问题,某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个5年计划，使总支出最少。,转化为下图所示的求v1到v6的最短路问题：,V1,V2,V3,V4,V5,V6,12,13,14,15,15,19,28,40,59,20,29,41,21,30,22,12+（5+6+8）-2=29,14+（5+6）-3=22,可以用Dijkstra法求解。,2.选址问题,已知某地区的交通网络如下图所示，其中点代表居民小区，边表示公路， 为小区间公

16、路的距离，问区中心医院应建在哪个小区，可使离医院最远的小区就诊时所走的路程最近？,V1,V3,V2,V4,V6,V7,30,15,25,20,60,18,15,V5,30,这是求任意两点间最短路的问题，可以用Floyd法求解。,93,63,50,63,93,48,63,所以应该把医院设在v6处，此时v5距离医院最远，距离为48。,第四节,最 大 流 问 题,1.容量网络,一、最大流相关概念,给定一个有向图G(V,E)，其中仅有一个点的入次为零称为发点（源），记为vs，仅有一个点的出次为零称为收点（汇），记为vt，其余点称为中间点。,对于G中的每一个弧(vi,vj)，相应地给一个数cij（cij0），称为弧(vi,vj)的容量。我们把这样的G称为容量网络，记为G(V,E,C)。,一、最大流相关概念,2.流,所谓网络上的流，是指定义在弧集E上的函数ff(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。,标示方式：每条边上标示两个数字，第一个是容量，第二是流量,一、最大流相关概念,3. 可行流,可行流是指满足如下条件的流：,（1）容量限制条件：对G中