运筹学-八章-图与网络分析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《运筹学-八章-图与网络分析课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 网络分析 课件
- 资源描述:
-
1、图论的产生:图论的产生:1736年的年的“哥尼斯堡七桥哥尼斯堡七桥问题问题”十八世纪的东普鲁士哥尼斯堡城十八世纪的东普鲁士哥尼斯堡城哥尼斯堡七桥问题的网络分析哥尼斯堡七桥问题的网络分析一、图与网络的基本概念一、图与网络的基本概念由一些点及一些点的连线所组成的图形。若由一些点及一些点的连线所组成的图形。若V=V1,V2, Vn是空间是空间n个点个点的集合的集合; E= e1,e2, em是空间是空间m个边的集合个边的集合,满足满足: 1)V非空非空 2)E中每一条线中每一条线ei是以是以V中两个点中两个点Vs,Vt为端点为端点 3)E中任意两条线之间除端点之外无公共点中任意两条线之间除端点之外无
2、公共点.则由则由V、E构成的二元组合构成的二元组合G=(V, E)就是图。就是图。已知图已知图G1(V1,E1)若)若V1 V, E1 E ; 则称图则称图G1(V1,E1)是)是图图G=(V, E)的子图的子图若在图若在图G中,某个边的两个端点相同,则称中,某个边的两个端点相同,则称e是是。图中某两点之间有多余一条的边,称之为多重边。图中某两点之间有多余一条的边,称之为多重边。含有多重边的图。含有多重边的图。无环、无多重边的图。无环、无多重边的图。 无向图:无向图:G(V,E)点集)点集+边集边集 弧:弧:点与点之间有方向的边,叫做弧。弧集:点与点之间有方向的边,叫做弧。弧集:A=a1,a1
3、,am 有向图:有向图:由点及弧所构成的图,记为由点及弧所构成的图,记为D=(V,A),V,A分别是分别是D的点集合和弧集合。的点集合和弧集合。 环:环:某一条孤起点某一条孤起点=终点,称为环。终点,称为环。 基础图:基础图:给定一个有向图给定一个有向图D=(V,A) ,从,从D中去掉所有弧上的箭头,所得到的无中去掉所有弧上的箭头,所得到的无向图。记之为向图。记之为G(D)。 链:链:设设(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中的一个点弧交错序列,如果这个序中的一个点弧交错序列,如果这个序列在基础图列在基础图G(D)中所对应的点边序列是一条链,则称这个点弧交错
4、序列是中所对应的点边序列是一条链,则称这个点弧交错序列是D的的一条一条链链。 路:路:如果如果(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中的一条链,并且对中的一条链,并且对t=1,2,k-1,均有均有ait=(vit,vit+1),称之为从,称之为从vi1到到vik的一条的一条路路。 回路:回路:若路的第一个点和最后一点相同,则称之为回路。若路的第一个点和最后一点相同,则称之为回路。 次:次:图中的点图中的点V,以,以V为端点的边的个数,称为为端点的边的个数,称为V的次,的次,记为记为d(V)。 定理定理1:图:图G=(V,E)中,所有点的次之和是边数的两倍,中,
5、所有点的次之和是边数的两倍,即设边数为即设边数为q ,则,则d(vi)=2q ,其中,其中vi V 奇点:奇点:次为奇数的点。否则称为偶点。次为奇数的点。否则称为偶点。 任一图中,奇点的个数为偶数。任一图中,奇点的个数为偶数。 一笔划:一笔划:可以一笔划:没有或仅有两个奇次点的图形可以一笔划:没有或仅有两个奇次点的图形 如没有奇次点:任取一点,它既是起点又是终点。如没有奇次点:任取一点,它既是起点又是终点。 两个奇次点:分别选为起点和终点。两个奇次点:分别选为起点和终点。1、链:链:给定一个图给定一个图G=(V,E),一个点边的交错序列,一个点边的交错序列(vi1, ei1, vi2, ei2
6、,vik-1,eik-1,vik),如果满足,如果满足eit=vit,vit+1 (t=1,2,k-1),则称为一条联结,则称为一条联结vi1和和vik的的链链,称点,称点vi2, vi3,vik-1为链的中间点。为链的中间点。2、圈:圈:链链(vi1,vi2,vik)中,若中,若vi1=vik,,则称之为一个,则称之为一个圈圈。3、简单链:简单链:若链若链(vi1,vi2,vik)中,点中,点vi1,vi2,vik都是不同都是不同的,则称之为的,则称之为简单链。简单链。4、连通图:连通图:图图G中,若任何两个点之间,至少有一条链。否中,若任何两个点之间,至少有一条链。否则为不连通图。则为不连
7、通图。 1、赋权图:赋权图:给图给图G=(V,E) ,对,对G中的每一条边中的每一条边vi,vj,相应地有一个数,相应地有一个数wij,则称这样的图则称这样的图G为赋权图,为赋权图,wij称为边称为边vi,vj上的权。上的权。2、网络(赋权图)、网络(赋权图)G=(V,E),其边(),其边(vi,vj)有权)有权wij, 构造矩阵构造矩阵A=(aij)nn,其中:其中: aij= wij(vi,vj)E 0 其他其他称矩阵称矩阵A为网络为网络G的的权矩阵权矩阵。如。如P239,例,例23、对于图、对于图G=(V,E),), V =n,构造一个矩阵构造一个矩阵A=(aij)nn,其中:其中: a
8、ij= 1(vi,vj)E 0 其他其他称矩阵称矩阵A为图为图G的的邻接矩阵邻接矩阵。如。如P239,例,例31、欧拉回路与道路:欧拉回路与道路:连通图连通图G中,若存在一条道路,经过每边一次中,若存在一条道路,经过每边一次且仅一次,则称这条路为且仅一次,则称这条路为欧拉道路欧拉道路。若存在一条回路,经过每边。若存在一条回路,经过每边一次且仅一次,则称这条回路为一次且仅一次,则称这条回路为欧拉回路,具有欧拉回路的图也欧拉回路,具有欧拉回路的图也称欧拉图称欧拉图。仅当无向连通图仅当无向连通图G中无奇点时是欧拉图,仅当恰有两个奇点时为欧拉中无奇点时是欧拉图,仅当恰有两个奇点时为欧拉道路;道路;仅当
9、有向连通图仅当有向连通图G中每个顶点的出次等于入次时是欧拉图,仅当两个中每个顶点的出次等于入次时是欧拉图,仅当两个顶点外,其余每一个顶点的出次等于入次,且这两个顶点中,一顶点外,其余每一个顶点的出次等于入次,且这两个顶点中,一个顶点出次多个顶点出次多1,另一个顶点入次多,另一个顶点入次多1时为欧拉道路;时为欧拉道路;2、中国邮路问题:中国邮路问题:给定一个连通图给定一个连通图G,每边有非负权,每边有非负权l(e),要求一,要求一条回路过每边至少一次,且满足总权最小。条回路过每边至少一次,且满足总权最小。例如:比赛中的相遇情况、组织结构图、家庭树例如:比赛中的相遇情况、组织结构图、家庭树1、定义
10、、定义:一个无圈的连通图称为树。:一个无圈的连通图称为树。2、树的性质、树的性质:1)图)图G是树的充分必要条件是任意两是树的充分必要条件是任意两个顶点之间有且只有一条链。个顶点之间有且只有一条链。2)在树中去掉任意一条边则构成一个)在树中去掉任意一条边则构成一个不连通图,不再是树;在树中不相邻的不连通图,不再是树;在树中不相邻的两点之间添加一条边,恰好形成了一个两点之间添加一条边,恰好形成了一个圈,也就不再是树。圈,也就不再是树。3)树中顶点的个数为)树中顶点的个数为P,则其边数必,则其边数必为为P-1。3、生成树、生成树:设图:设图T=(V,E) 是图是图G(V,E)的子图,如果图)的子图
11、,如果图T=(V, E) 是一个树,则称是一个树,则称T是是G的一个支撑树。的一个支撑树。4、寻找生成树、寻找生成树的方法的方法1)破圈法:在图中任取一个圈,从圈中去掉任一边,对余下的图重复)破圈法:在图中任取一个圈,从圈中去掉任一边,对余下的图重复上述操作,即可得到一个支撑树。上述操作,即可得到一个支撑树。2)避圈法:每一步选取与已选的边构不成圈的边,直到不能继续为止。)避圈法:每一步选取与已选的边构不成圈的边,直到不能继续为止。(深探法广探法(深探法广探法阅读内容阅读内容)5、最小生成树、最小生成树1)最小支撑树:如果)最小支撑树:如果T=(V,E) 是是G的一个支撑树,称的一个支撑树,称
12、E中所有边的权中所有边的权之和为支撑树之和为支撑树T的权,记为的权,记为w(T),即,即 w(T)=wij (vi,vj)T如果支撑树如果支撑树T*的权的权w(T*)是是G的所有支撑树的权中最小者,则称的所有支撑树的权中最小者,则称T*是是G的的最小生成树(最小支撑树,简称最小树)最小生成树(最小支撑树,简称最小树) w(T*)=min w(T)2)求最小树求最小树的方法:的方法:方法一方法一(避圈法避圈法) 开始选一条最小权的边,以后每一步中,总从未被开始选一条最小权的边,以后每一步中,总从未被选取的边中选一条权最小的边,并使之与已选取的边不构成圈。选取的边中选一条权最小的边,并使之与已选取
13、的边不构成圈。方法二方法二(破圈法破圈法) 任取一个圈,从圈中去掉一条权最大的边。在余下任取一个圈,从圈中去掉一条权最大的边。在余下的图中,重复这个步骤,一直到一个不含圈的图为止,这时的图便是的图中,重复这个步骤,一直到一个不含圈的图为止,这时的图便是最小树。最小树。 例例 用破圈法求下图的最小树用破圈法求下图的最小树122223122223334456、根树及其应用、根树及其应用定义定义17:若一个有向图在不考虑边的方向时是一棵树,则称这个有向图:若一个有向图在不考虑边的方向时是一棵树,则称这个有向图为有向树。为有向树。定义定义18:有向树:有向树T,恰有一个结点入次为,恰有一个结点入次为0
14、,其余各点入次均为,其余各点入次均为1,称树,称树T为根树(又称外向树)。为根树(又称外向树)。定义定义19:在根树中,若每个顶点的出次小于或等于:在根树中,若每个顶点的出次小于或等于m,称这颗树为,称这颗树为m叉叉树,若每个顶点的出次恰好等于树,若每个顶点的出次恰好等于m或或0,则称这颗树为完全,则称这颗树为完全m叉树。当叉树。当m=2时,称为二叉树、完全二叉树。满足总权最小的二叉树称为最优时,称为二叉树、完全二叉树。满足总权最小的二叉树称为最优二叉树(又称霍夫曼树)。二叉树(又称霍夫曼树)。最优二叉树求解步骤:最优二叉树求解步骤:(1)将)将s个叶子按权由小到大排序,不失一般性,设个叶子按
15、权由小到大排序,不失一般性,设p1p2ps(2)将两个具有最小权的叶子合并成一个分枝点,其权为)将两个具有最小权的叶子合并成一个分枝点,其权为p1+p2,将新,将新的分枝点作为一个叶子,令的分枝点作为一个叶子,令s=s-1,若,若s=1停止,否则转(停止,否则转(1)习题: P8.7 P8.8 P8.98.3 最短路问题最短路问题如下图中如下图中V1:油田,:油田,V9:原油加工厂:原油加工厂求使从求使从V1到到V9总铺路设管道最短方案。总铺路设管道最短方案。 V1V4V2V3V6V9V8V7V542466234442用图论来解释最短路问用图论来解释最短路问题:在一个赋权有向图题:在一个赋权有
16、向图D(V,A,w)中,其)中,其中始点中始点V1,终点,终点Vt,求,求从从V1到到Vt的一条路,使的一条路,使其为其为V1到到Vt的所有路中的所有路中总权值最小的路。总权值最小的路。1、情况一:、情况一: wij0(Dijkstra算法算法)原理:原理:Bellman最优性定理最优性定理方法:图上作业法(标号法);双标号法(表的形式)方法:图上作业法(标号法);双标号法(表的形式)标号:对于点标号:对于点V,若已求出若已求出V1到到Vi的最短值,标号(的最短值,标号(i,i) i :表示:表示V1到到Vi的最短路值的最短路值 i:表示最短路中最后经过的点表示最短路中最后经过的点标号法步骤:
17、标号法步骤:1)给)给V1标号标号(0, Vs)2)把所有顶点分成两部分,)把所有顶点分成两部分,X:已标号的点;:已标号的点;X未标号的点未标号的点考虑与已标号点相邻的弧是存在这样的弧(考虑与已标号点相邻的弧是存在这样的弧( Vi ,Vj ), Vi X, Vj X若不存在,此问题无解,否则转若不存在,此问题无解,否则转3)3)选取未标号中所有入线的起点与未标号的点)选取未标号中所有入线的起点与未标号的点Vj进行计算进行计算:mini + wij= j并对其进行标号并对其进行标号(j, Vi),重复,重复2)例9:(图831)步骤 v1v2v3v4v5v6v7v8最短路前向结点1002345
18、678*464v1*6986v1*988v2*913149v2*131413v5*141714v5*1515v7最短路长为15,路径可以逆向追踪,v8-v7-v5-v2-v1例2s5t6341074918815220230 0 8151012151131132s5t6341074918815220230 Dijkstra最短路算法的最短路算法的特点特点和和适应范围适应范围 一种隐阶段的动态规划方法一种隐阶段的动态规划方法 每次迭代只有一个节点获得永久标记,若有两个或两个以上节点的每次迭代只有一个节点获得永久标记,若有两个或两个以上节点的临时标记同时最小,可任选一个永久标记;总是从一个新的永久标
19、临时标记同时最小,可任选一个永久标记;总是从一个新的永久标记开始新一轮的临时标记,是一种记开始新一轮的临时标记,是一种深探法深探法 被框住的永久标记被框住的永久标记 Tj 表示表示 vs 到到 vj 的最短路,因此的最短路,因此 要求要求 dij 0,第,第 k 次迭代得到的永久标记,其最短路中最多有次迭代得到的永久标记,其最短路中最多有 k 条边,因此最多有条边,因此最多有n 1 次迭代次迭代 可以应用于可以应用于简单简单有向图和混合图,在临时标记时,所谓相邻必须是有向图和混合图,在临时标记时,所谓相邻必须是箭头指向的节点;若第箭头指向的节点;若第 n 1 次迭代后仍有节点的标记为次迭代后仍
20、有节点的标记为 ,则表明,则表明 vs 到该节点无有向路径到该节点无有向路径 如果只求如果只求 vs 到到 vt 的最短路,则当的最短路,则当 vt 得到永久标记算法就结束了;得到永久标记算法就结束了;但算法复杂度是一样的但算法复杂度是一样的 应用应用 Dijkstra 算法算法 n 1 次次 ,可以求所有点间的最短路,可以求所有点间的最短路 vs 到所有点的最短路也是一棵生成树,但不是最小生成树到所有点的最短路也是一棵生成树,但不是最小生成树设从设从V1到到Vj(j=1,2,t)的最短路长为的最短路长为P1jV1到到Vj无任何中间点无任何中间点 P1j(1)= wijV1到到Vj中间最多经过
21、一个点中间最多经过一个点 P1j(2)= min P1i(1)+wijV1到到Vj中间最多经过两个点中间最多经过两个点 P1j(3)= min P1i(2)+wij.V1到到Vj中间最多经过中间最多经过t-2个点个点 P1j(t-1)= min P1i(t-2)+wij终止原则:终止原则:1)当)当P1j(k)= P1j(k+1)可停止,最短路可停止,最短路P1j*= P1j(k)2)当)当P1j(t-1)P1j(t-2)时,再多迭代一次时,再多迭代一次P1j(t) ,若,若P1j(t) = P1j(t-1) ,则,则原问题无解,存在负回路。原问题无解,存在负回路。V1V2V3V4V5V6V7
22、V8P1j(1)P1j(2)P1j(3)P1j(4)P1j(5)P1j(6)V1V2V3V4V5V6V7V80v1v4v2v3v5v6v7v825-34674-23-1-34225-30-2406400-3047203-10025-3020-3611020-36615020-3361410020-336910020-336910例:例:例例 设备更新问题设备更新问题制订一设备更新问题,使得总费用最小制订一设备更新问题,使得总费用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 购买费购买费 13 14 16 19 24 使用年数使用年数 0-1 1-2 2-3 3-4 4-5
展开阅读全文