第八章--图与网络.ppt
《第八章--图与网络.ppt》由会员分享,可在线阅读,更多相关《第八章--图与网络.ppt(130页珍藏版)》请在三一文库上搜索。
1、第 八 章 图 与 网 络 分 析,教学目的:让学生了解图论的基本知识,掌握用网络表示所研究问题、对象的基本属性及其解决方法。 教学内容:基本概念、树、最短路、最大流、最小费用最大流等。 教学难点:建立网络图的技巧和各种方法产生的思路。 学时安排:810学时。,第一节 图与网络的基本知识,1、18世纪哥尼斯堡城中普雷格尔河中有两个小岛C、D,它们之间与两岸A、B共有七座桥相连。,一、图论形成的历史回顾,A,B,当地人热衷于这样的游戏:一个人怎样才能一次连续走过七桥且每桥只走一次,再回到出发点。,1736年,著名数学家欧拉把此问题简化为图,并发表了论文:“依据几何位置的解题方法”。,能否从某一点
2、开始不重复地一笔画出这个图形,最终回到原点?,2、1847年,物理学家基尔霍夫为解决有关线性方程组而发展了“树”的理论。他将网络中的电感、电容、电阻等抽象为点和线,得到一简单的组合结构。这种结构便于运算,不必指明为何种元素。,3、1857年,凯莱研究饱和烃链CnH2n+2的同分异构体时,又一次引入树状结构,例如, C4H10 。,5、1857年,英国数学家哈密尔顿发明了一个游戏,他用一个实心正12面体象征地球,正12面体的20个顶点分别表示世界上的20个城市,要求寻找一条路径:由某个城市出发每城市仅去一次,最终回到出发点。,1、有向图与无向图:如果顶点之间的连线皆是无方向的(称为边,边的集合记
3、为E),此时图G称为无向图,记为G=(V,E); 如果顶点之间的连线有方向,即有向边(或称为弧,弧的集合记为A) ,此时图G称为有向图,记为 D =(V,A)。用m(D)=E( A)表示图D 中边(弧)的数量;用n(D)=V表示图D中顶点的数量。,一个图是由点集V=vi和V中元素(顶点)之间的连线所组成。,二、图与网络的基本概念,G=(V,E) V=A,B,C,D,N,F,G,H,M E=A,A,A,B,A,C,H,M m(G)=12;n(G)=9,边,端点,端点,D=(V,A) V=M,N,F,G A=M,G,G,F,M,N,N,F,弧,始点,终点,2、如果一条边的两端点相同,此边称为环,两
4、点之间多于一条边的,称为多重边。,3、简单图:无多重边和环的图; 多重图:有多重边,无环的图。,4、链:点、边交替的序列(V1,e1, V2,e2, ,Vi,ei) ; 简单链: 边不重复, A, C, D, B, G,D,N; 初等链: 点、边不重复, A, B, G, F, N; 。,5、 圈:链上首、尾节点是同一节点时,称为圈; 简单圈:圈中没有重复的边;(A,B,G,B,D,C,A) 初等圈:既无重复点,也无重复边;(A,B,D,C,A),路:链上边方向一致时,称为路; 回路:路上首、尾节点是同一节点时,称为回路。,6、顶点的次:以点vi为端点的边数,记为d(vi )。,如图中d(A
5、) =2(用于无向图)。,出次:以点vi为始点的边数,用d+(vi )表示 。 入次:以点vi为终点的边数,用d-(vi )表示。 d+(vi ) +d-(vi )= d(vi )(用于有向图)。,d+(D ) =1 d-(D ) =1 d(D) =2,偶点:d(v) = 偶数; 奇点:d(v)=奇数 悬挂点:d(v)=1; 悬挂边:与悬挂点连接的边; 孤立点:d(v)=0; 空图:E = ,无边图,7、连通图:图G=(V,E)中任意两点间至少有一条链。 子图: G=(V,E),其中 VV ,E E。,支撑(生成)子图:对于子图G=(V,E),当V=V时,且与图G=(V,E)的连通性相同的子图
6、称为支撑子图,或生成子图。,8、完全图:任意两点间皆有边相连的无向简单图。,9、基础图:将有向图中弧去掉其方向所形成的无向图,称为原有向图的基础图。 网络:给图的边或点赋予某些数量指标(我们称之为“权”),这种赋权图又称为网络。,10、图的矩阵表示:邻接矩阵与权矩阵,(1)邻接矩阵:图G=(V,E),V=n,构造一个矩阵邻接矩阵A=(aij)nn,其中,(2)权矩阵:图G=(V,E),V=n,边(vi, vj)有权ij,构造矩阵权矩阵B=(bij)nn,其中,定理1 任何图中,顶点次的总和等于边数的2倍。,三、基本理论,d(G)=2; d(D)=2; d(N)=2;d(F)=2;,次为奇数的点
7、为奇点,次为偶数的点为偶点。奇点的集合可记为V1,偶点的集合记为V2。,定理2 任何图中,次为奇数的顶点必为偶数个。,四、欧拉回路与道路 定义:连通图G中,若存在一条道路,经过每边一次且仅一次,则称这条路为欧拉道路。若存在一条回路,经过每边一次且仅一次,则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图(图)。,定理:无向连通图G是欧拉图,当且仅当G中无奇点。,推论 无向连通图为欧拉图,当且仅当的边集可划分为若干个初等回路。 推论 无向连通图有欧拉道路,当且仅当中恰有两个奇点。 定理:连通有向图是欧拉图,当且仅当它每个顶点的出次等于入次。,五、中国邮路问题(Chinese postman p
8、roblem),一个邮递员如何选择一条道路,是他能从邮局出发,走遍他负责送信的所有街道,最后回到邮局,并且所走的路程为最短。 给定一个连通图,每边有非负权l(e),要求一条回路过每边至少一次,且满足总权最小。 中国邮路问题可用于邮政部门、扫雪车路线、洒水车路线、警车巡逻路线、(计算机绘图)如何节约画笔的空走问题、(计算机制造工业)如何将激光刻制用于集成电路加工的模具等。 定理:已知图G*=G+E1,无奇点,则L(E1)= l(e)最小的充分必要条件为: (1)每条边最多重复一次; (2)对图G中每个初等圈来讲,重复边的长度和不超过圈长的一半。 奇偶点图上作业法。,v5,v6,v9,v8,v7,
9、5,4,3,6,3,4,4,v5,v6,v9,v8,v7,5,4,3,6,3,4,4,第 二 节 树,主要内容: 1.树的概念与性质 2.最小生成树及其算法,1.树连通且不含圈的无向图称为树。树中次为1的点为树叶,次大于1的点称为分枝点。,一、树的概念与性质,2.生成树若图G的生成子图是一棵树,则称该树为G的生成树(或支撑树)。简称为图G的树。图中属于生成树的边叫树枝, 不在生成树的边叫弦。,树枝,树枝,树枝,树枝,树枝,弦,弦,弦,弦,3.最小生成树连通图G=( V,E ),每条边上有非负权L( e )。一棵生成树所有树枝上权的总和称为这棵生成树的权。具有最小权的生成树称为最小生成树(最小支
10、撑树),简称最小树。,定理3 设图G(V,E)是一棵树,n(G)2,则G 中至少有两个悬挂点,(1)T无圈,且m=(n-1)。,定理4 图T=( V,E ),V=n,E=m,若T是一棵树,则下列关于树的说法是等价的。,(2)T连通,且m=(n-1)。 (3)T无圈,但每加一新边即得唯一一个圈。,(4)T连通,但任舍去一边就不连通。 (5 ) T中任意两点,有唯一链相连。,定理5:图G有支撑树的充要条件为G是连通图。,该定理的证明给出了求生成树的方法:每步选出一条边,使它与已经选出的边不形成圈,直至选出(n-1)条边为止。,(1)支撑树的求法:破圈法,(1)避圈法每步从未选的边中选取e,使它与已
11、选边不构成圈,且e是未选边中的最小权边,直到选够(n-1)条边为止。,(2)破圈法每步从未破掉的圈中任选一个圈,将该圈的边中权最大的一条边e去掉,直到图中无圈为止。,例82 一个乡有9个自然村,其间道路及各道路长度如下图所示,各边上的权表示距离,问如何拉电缆线才能使用线总长度最短。,解:这是一个最小生成树问题。具体解法如下:,二、最小生成树的算法,最小树权值为W(T) =5+2+3+2+3+4+6+1=26。,1,2,3,3,4,5,6,2,第 三 节 最 短 路 问 题,一、问题的提出,二、最短路的定义,设D =(V,A)为一个赋权有向图,图中各弧(vi ,vj)有权lij0, vs、vt为
12、图中任意两点,求一条路P0,它是从vs 到 vt的所有路P中总权最小的路。 w(p0) = min w(p),P=(v1 ,v2 , v4 , v5 ),(v1 , v3 , v5 ),P0= (v1 ,v2 , v4 , v5 ),w(p0)=14,三、Dijkstra算法(1959年),用于求解指定两点间的最短路,或从指定点到其余各点的最短路。 Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等,是目前被认为求无负权网络最短路问题的最好方法。 其采用的是贪心法的算法策略。 Dijkstra算法能得出最短路径的最优解,但由于
13、它遍历计算的节点很多,所以效率低。,1、算法思路,(1) 当lij0时,若从vi 出发的弧中权值最小者是(vi ,vk)那么,从vi至 vk的最短路长必然是lik。,(2)若序列v1, v2, vk, , vn 是从v1 至 vn 的一个最短路,则序列v1 , v2 , vk是从v1至 vk的一个最短路程。即,全局最优,一定是局部最优的。,序列v1, v4,v5 是从v1 至 vn 的一个最短路,则序列v1, v4是从v1 至 v4 的一个最短路,从vs出发,给从vs 到 vk 最短路长的点 vk 赋予固定标号P(permanent label)标号,并记下相应的最短路长(真实的长度); 而未
14、得到P标号的点,赋予试探性(临时性标号)标号T(tentative label)标号,表示从vs 到vk 点的最短路长的上界。,(3)标记:,P (v1 ) =0,T(v2 )=3,T(v4 )=8,T(v6 )=14,(1)给vs以P标号,P(vs)=0,其余各点均给T类标号, T(vi)=+ (2)若vi点为刚得到P标号的点,考虑这样的点vj: (vi,vj)E,且vj为T标号,对其T标号进行如下更改: T(vj)=min T(vj ) , P (v i)+lij (3)比较所有具有T标号的点,把最小者vk改为P标号: P(vk)=min T(vk) 若vt得到固定标号则停止,否则用vk
15、代替vi,转回(2)。,2、算法的步骤,P(v1)=0,T(v3)=+,T(v2)=+,T(v4)=+,T(v2)=3,T(v3)=1,P(v3)=1,T(v4)=4,T(v2)=2,P(v2)=2,P(v4)=4,(vi)= vm :表示从v1到vi的最短路上, vi的前一个点是vm,(v2)=,v3,(v4)=,v3,S:已获得固定标号的点的集合,例85 用Dijkstra算法求下图中vs 到 vt点的最短路。,3、举例,P(vs)=0,T(v1)=+,T(v3)=+,T(v5)=+,T(v2)=+,T(v4)=+,T(v6)=+,T(vt)=+,T(v1)=4,T(v2)=6,P(v1)
16、=4,T(v3)=9,T(v4)=8,P(v2)=6,P(v4)=8,T(v5)=13,T(v6)=14,P(v3)=9,P(v5)=13,T(vt)=17,P(v6)=14,P(vt)=15,(vt)= v6,T=+,P=0,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=2,T=8,P=2,T=3,P=3,T=4,P=4,T=10,T=11,T=6,P=6,P=8,T=15,P=10,T=14,P=11,P=14,T=15,P=15,P=15,四、带有负权网络的最短路解法 逐次逼近法,(1)基本思想: 若v1 到 vj 的最短路总是沿着该路 从v1 到某一点vi
17、 ,然后再沿着边( vi ,vj)到 vj 。则从v1 到点vi的这条路,也是从v1 到点vi的最短路。 如果令P1i为从v1 到点vi的最短路长,则下列方程成立: P1j = minP1i +lij i=1, 2, , n 该方程表明: v1到 vj的最短路要依次考察网络中的所有点vi i=1, 2, , n。当改变 vj时,可以求出从v1到其它各个点的最短路。,v4,(2)迭代公式:,P1j(1) =0,3,1, ,P1j(2) =minP1i(1) +lij =minP11(1) +l1j , P12(1) +l2j , P13(1) +l3j , P14(1) +l4j ,P14(2)
18、 =minP1i(1) +li4 =minP11(1) +l14 , P12(1) +l24 , P13(1) +l34 , P14(1) +l44 =min0+ ,3+5,1+3, +0=4,P14(2) =4 , (v4)= v3,P1j(3) =minP1i(2) +lij =minP11(2) +l1j , P12(2) +l2j , P13(2) +l3j , P14(2) +l4j ,P14(3) =minP1i(2) +li4 =minP11(2) +l14 , P12(2) +l24 , P13(2) +l34 , P14(2) +l44 =min0+ ,2+5,1+3, 4+
19、0=4,P14(2) =4 , (v4)= v3,例8-6:求v1到各点的最短路。,第一步:初始条件为: P1j(1) =0,2,5,-3,,第二步:第一次迭代(k=2) P11(2) = minP11(1) , P12(1) , P13(1) ,P14(1) , P15(1) ,P16(1) , P17(1) , P18(1) ,+ l11 + l21 + l31 + l41 + l5 1 + l61 + l71 + l81,= min(0+0, 2+, 5+, -3+, , , , ) = 0,P12(2) = minP11(1) ,P12(1) , P13(1) ,P14(1) , P1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 网络
链接地址:https://www.31doc.com/p-2261329.html