第6章--图与网络分析课件.ppt

《第6章--图与网络分析课件.ppt》由会员分享，可在线阅读，更多相关《第6章--图与网络分析课件.ppt（106页珍藏版）》请在三一办公上搜索。

1、1,图及其分类,图是点与线的集合。一个图由一些点及一些点之间的联线(不带箭头或带箭头)所组成。为了区别起见。把两点之间的不带箭头的连线称为边，带箭头的连线称为弧。用图来描述事物间的联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之间关系的一种工具。,2023/4/4,2,无向图,由点和边组成的图称为无向图。,2023/4/4,3,无向图,2023/4/4,4,环、多重边、简单图、多重图,2023/4/4,5,点的次,2023/4/4,6,链、圈、连通图,2023/4/4,7,子图,2023/4/4,8,子图,v1,2023/4/4,9,

2、有向图,由点和弧组成的图称为有向图。,2023/4/4,10,环、多重弧、简单有向图,2023/4/4,11,点的出次和入次、路,2023/4/4,12,网络的概念,2023/4/4,13,图的矩阵表示：关联矩阵,2023/4/4,14,图的矩阵表示：邻接矩阵,2023/4/4,15,图的矩阵表示：权矩阵,2023/4/4,16,树与最小树问题,2023/4/4,17,树的概念和性质,2023/4/4,18,树的概念和性质,2023/4/4,19,支撑树,2023/4/4,20,用破圈法与避圈法求支撑树,2023/4/4,21,最小树,破圈法：任取一圈，去掉圈中最长边，直到无圈。,2023/4

3、/4,22,最小树,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,【例8.1】用破圈法求下图的最小树。,最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同,2023/4/4,23,避圈法：取图G的n个孤立点v1，v2，vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v1,v2,v3,v4,v5,v6,在上图中，如果添加边v1,v2就形成圈v1,v2,v4，这时就应避开添加边v1,v2，添加下一条最短边v3,v6。破圈法和

4、避圈法得到树的形状可能不一样，但最小树的长度相等,Min C(T)=15,2023/4/4,24,最小树的寻找方法：矩阵法,2023/4/4,25,矩阵法举例,2023/4/4,26,矩阵法,2023/4/4,27,矩阵法举例,2023/4/4,28,矩阵法举例,2023/4/4,29,最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题,求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法 另一种是针对网络中有负权的逐次逼近法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离

5、最短的一条路,最短路问题,2023/4/4,30,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,【例8.3】下图中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。,2023/4/4,31,【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij1，不选择弧(i，j)时xij0，得到最短路问题的网络模型：,2023/4/4,32,Dijkstra标号法原理,2023/4/4,33,Dijkstra标号法原理,2023/4/4,34,Dijkstra算法的具体步骤,2

6、023/4/4,35,Dijkstra算法的具体步骤,2023/4/4,36,6,10,12,3,2,14,6,7,5,8,11,16,5,9,(6,v1),(12,v1),(16,v3),(18,v3),(29,v5),【例8.3】用Dijkstra算法求下图所示v1到v7的最短路及最短路长,v1 到v7的最短路为：p17=v1,v2,v3,v5,v7，最短路长为L17=29,2023/4/4,37,Dijkstra算法举例,2023/4/4,38,Dijkstra算法举例,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,2023/4/4,39,

7、逐次逼近法,2023/4/4,40,逐次逼近法,2023/4/4,41,逐次逼近法举例,2023/4/4,42,逐次逼近法举例,2023/4/4,43,逐次逼近法举例,2023/4/4,44,逐次逼近法举例,2023/4/4,45,最短链问题,2023/4/4,46,最短链问题,2023/4/4,47,最短链问题举例,2023/4/4,48,最短链问题举例,2023/4/4,49,最短链问题举例,2023/4/4,50,最短链问题举例,2023/4/4,51,最短链问题举例,2023/4/4,52,最短链问题举例,2023/4/4,53,网络最大流问题,所谓最大流量问题就是：给一个带收发点的网

8、络（一般收点用vt表示，发点用vs表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大流量。在交通运输、物资供应、通讯系统和财政金融等实际工作中，常会遇到这类最大流问题。,2023/4/4,54,网络最大流问题,2023/4/4,55,最大流有关概念,2023/4/4,56,可行流与最大流,2023/4/4,57,增广链的概念,2023/4/4,58,增广链的概念,2023/4/4,59,截集和截量,2023/4/4,60,截集和截量,2023/4/4,61,截集和截量,2023/4/4,62,满足下例3个条件的流fij 的

9、集合 f=fij 称为可行流,发点vs流出的总流量等于流入收点vt的总流量,概念回顾,2023/4/4,63,链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。,前向弧：与链的方向相同的弧称为前向弧。,后向弧：与链的方向相反的弧称为后向弧。,增广链:设 f 是一个可行流，如果存在一条从vs到vt的链，满足：,1.所有前向弧上fijCij,2.所有后向弧上fij0,则该链称为增广链,容量,流量,2023/4/4,64,寻找网络最大流的Ford-Fulkerson标号法,2023/4/4,65,算法的步骤,2023/4/4,66,算法的步骤,2023/4/

10、4,67,算法举例,2023/4/4,68,算法举例,2023/4/4,69,算法举例,2023/4/4,70,算法举例,2023/4/4,71,算法举例,2023/4/4,72,算法举例,2023/4/4,73,算法举例,2023/4/4,74,(14，10),(8，6),(5，3),(6，6),(3，3),(8，7),(3，0),(6，6),(3，1),(10，3),(4，1),(7，7),【例8.7】求下图发点v1到收点v7的最大流及最大流量,2023/4/4,75,无向图最大流标号算法,无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端vj未标号的边只要满足 Cij

11、fij0 则vj就可标号（Cijfij）,【例8.8】求下图v1到则v7标的最大流,(12,10),(9,6),(20,10),(8,8),(5,2),(8,3),(7,7),(6,6),(14,5),(13,13),(9,0),(16,13),0,v1,2,v4,2,v5,2,v6,2,v2,2,76,(12,12),(9,6),(20,10),(8,8),(5,4),(8,3),(7,7),(6,6),(14,7),(13,13),(9,2),(16,15),0,v1,3,v4,3,v5,3,v6,1,2023/4/4,77,(12,12),(9,7),(20,10),(8,8),(5,4

12、),(8,3),(7,7),(6,6),(14,8),(13,13),(9,3),(16,16),V=29,0,v1,10,v3,5,v4,5,v5,5,v4,1,78,最小费用网络最大流问题,2023/4/4,79,最小费用最大流问题,2023/4/4,80,最小费用增广链,2023/4/4,81,求最小费用流的基本思想,2023/4/4,82,辅助赋权有向网络的构造方法,2023/4/4,83,最小费用最大流算法步骤,2023/4/4,84,最小费用最大流算法应用举例,2023/4/4,85,最小费用最大流算法应用举例,2023/4/4,86,最小费用最大流算法应用举例,2023/4/4,

13、87,最小费用最大流算法应用举例,2023/4/4,88,最小费用最大流算法应用举例,2023/4/4,89,最小费用最大流算法应用举例,2023/4/4,90,最小费用最大流算法应用举例,2023/4/4,91,欧拉图,2023/4/4,92,欧拉链、欧拉圈与欧拉图,欧拉链 给定一个连通多重图G，若存在一条链，经过每边一次且仅一次，称这条链为欧拉链。欧拉圈 若存在一个简单圈，过每边一次，称这个圈为欧拉圈。欧拉图 一个具有欧拉圈的图，称为欧拉图。上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。,2023/4/4,93,定理与推论,定理1 连通多重图G 是欧拉图的充要条件是图中的点全为偶点

14、。定理2 连通多重图G有欧拉链，当且仅当G中恰有两个奇点。上述两个定理可用来识别一个图能否一笔画出。,2023/4/4,94,中国邮递员问题,中国邮递员问题由我国学者管梅谷在1962年首先提出。所谓中国邮递员问题，是指如下问题：某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，他应如何安排投递路线，使所走的总路程最短。中国邮递员问题的图论语言描述：给定一个连通图，在每边上ei上赋予一个非负的权w(ei),要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。,2023/4/4,95,中国邮递员问题求解,考虑两种情形：如果G是欧拉图，则从邮局出发，每

15、边恰好走一次可回到邮局，这时总权必定最小；如果G不是欧拉图，则某些边必然要重复走，我们当然要求重复走过的边的总长最小。我们可以用“奇偶点图上作业法”解决这一问题。,2023/4/4,96,“奇偶点图上作业法”相关定理,2023/4/4,97,奇偶点图上作业法,2023/4/4,98,奇偶点图上作业法举例,2023/4/4,99,奇偶点图上作业法举例,2023/4/4,100,奇偶点图上作业法举例,2023/4/4,101,奇偶点图上作业法举例,2023/4/4,102,奇偶点图上作业法举例,2023/4/4,103,【例】求解下图的中国邮路问题,3,5,v1,v2,v4,v5,v6,v7,4,7,5,2,6,1,8,v3,4,1,奇偶点图上作业法举例,2023/4/4,精品课件！,精品课件！,106,5,v1,v2,v4,v5,v6,v7,4,3,7,5,2,6,1,8,v3,4,1,【解】最优解如下图,上图为最短欧拉回路，重复经过了1，2和6，7两条边,2023/4/4,