大学精品课件:第八章 图与网络分析.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《大学精品课件:第八章 图与网络分析.ppt》由用户(罗嗣辉)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学精品课件:第八章 图与网络分析 大学 精品 课件 第八 网络分析
- 资源描述:
-
1、第八章第八章 图与网络分析图与网络分析p图的基本知识图的基本知识p最短路径问题最短路径问题p网络最大流问题网络最大流问题p最小费用最大流问题最小费用最大流问题图论的产生:图论的产生:1736年的年的“哥尼斯堡七桥哥尼斯堡七桥问题问题”十八世纪的东普鲁士哥尼斯堡城十八世纪的东普鲁士哥尼斯堡城哥尼斯堡七桥问题的网络分析哥尼斯堡七桥问题的网络分析1.图的基本知识图的基本知识一、图一、图1、图:由一些点及一些点的连线所组成的图形。、图:由一些点及一些点的连线所组成的图形。若若V=V1,V2,Vn是空间是空间n个点的集合个点的集合 E=e1,e2,em是空间是空间m条线的集合条线的集合满足满足1)V非空
2、非空 2)E中每一条线中每一条线ei是以是以V中两个点中两个点Vs,Vt为端点为端点 3)E中任意两条线之间除端点之外无公共点中任意两条线之间除端点之外无公共点.则由则由V、E构成的二元组合构成的二元组合G=(V,E)就是图。就是图。2、子图:已知图、子图:已知图G1(V1,E1)若)若V1 V,E1 E 则称图则称图G1(V1,E1)是图)是图G=(V,E)的子图的子图3、若在图若在图G中,某个边的两个端点相同,则称中,某个边的两个端点相同,则称e是环。是环。4、多重边:图中某两点之间有多余一条的边,称之为多重、多重边:图中某两点之间有多余一条的边,称之为多重边。边。多重图:含有多重边的图。
3、多重图:含有多重边的图。5、简单图:无环、无多重边的图。、简单图:无环、无多重边的图。二、一笔划问题二、一笔划问题1、次:图中的点、次:图中的点V,以,以V为端点的边的个数,称为为端点的边的个数,称为V的的次,记为次,记为d(V)。2、定理、定理1:图:图G=(V,E)中,所有点的次之和是边数的两中,所有点的次之和是边数的两倍,即设边数为倍,即设边数为q,则,则d(vi)=2q,其中,其中vi V3、奇点:次为奇数的点。否则称为偶点。奇点:次为奇数的点。否则称为偶点。4、任一图中,奇点的个数为偶数。、任一图中,奇点的个数为偶数。5、一笔划:、一笔划:可以一笔划:没有或仅有两个奇次点的图形可以一
4、笔划:没有或仅有两个奇次点的图形 如没有奇次点:任取一点,它既是起点又是终点。如没有奇次点:任取一点,它既是起点又是终点。两个奇次点:分别选为起点和终点。两个奇次点:分别选为起点和终点。三、连通图三、连通图1、链:给定一个图、链:给定一个图G=(V,E),一个点边的交错序列,一个点边的交错序列(vi1,ei1,vi2,ei2,vik-1,eik-1,vik),如果满足,如果满足eit=vit,vit+1(t=1,2,k-1),则称为一条联结,则称为一条联结vi1和和vik的的链链,称点,称点vi2,vi3,vik-1为链的中间点。为链的中间点。2、圈:链、圈:链(vi1,vi2,vik)中,若
5、中,若vi1=vik,,则称之为一,则称之为一个个圈圈。3、简单链:若链、简单链:若链(vi1,vi2,vik)中,点中,点vi1,vi2,vik都都是不同的,则称之为是不同的,则称之为简单链。简单链。4、连通图:图、连通图:图G中,若任何两个点之间,至少有一中,若任何两个点之间,至少有一条链。否则为不连通图。条链。否则为不连通图。四、有向图四、有向图1、无向图:、无向图:G(V,E)点集)点集+边集边集2、弧:点与点之间有方向的边,叫做弧。、弧:点与点之间有方向的边,叫做弧。弧集:弧集:A=a1,a1,am3、有向图:由点及弧所构成的图,记为、有向图:由点及弧所构成的图,记为D=(V,A),
6、V,A分别是分别是D的点集合和弧集合。的点集合和弧集合。4、环:某一条孤起点、环:某一条孤起点=终点,称为环。终点,称为环。5、基础图:给定一个有向图、基础图:给定一个有向图D=(V,A),从,从D中去掉所中去掉所有弧上的箭头,所得到的无向图。记之为有弧上的箭头,所得到的无向图。记之为G(D)。6、链:设、链:设(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中中的一个点弧交错序列,如果这个序列在基的一个点弧交错序列,如果这个序列在基础图础图G(D)中所对应的点边序列是一条链,中所对应的点边序列是一条链,则称这个点弧交错序列是则称这个点弧交错序列是D的一条的一条链链。7
7、、路:如果、路:如果(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中的一条链,并且对中的一条链,并且对t=1,2,k-1,均有,均有ait=(vit,vit+1),称之为从,称之为从vi1到到vik的一条的一条路路。8、回路:若路的第一个点和最后一点相同,、回路:若路的第一个点和最后一点相同,则称之为回路。则称之为回路。五、图的矩阵表示五、图的矩阵表示1、赋权图:给图、赋权图:给图G=(V,E),对,对G中的每一条边中的每一条边vi,vj,相应地有,相应地有一个数一个数wij,则称这样的图,则称这样的图G为赋权图,为赋权图,wij称为边称为边vi,vj上的权。上的权。
8、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,其中:其中:aij=1(vi,vj)E 0 其他其他称矩阵称矩阵A为图为图G的邻接矩阵。如的邻接矩阵。如P239,例,例3 六、树六、树例如:比赛中的相遇情况、组织结构图、家庭树例如:比赛中的相遇情况、组织结构图、家庭树1、定义:一个无圈的连通图称为
9、树。、定义:一个无圈的连通图称为树。2、树的性质:、树的性质:1)图)图G是树的充分必要条件是任意两个顶点之间有是树的充分必要条件是任意两个顶点之间有且只有一条链。且只有一条链。2)在树中去掉任意一条边则构成一个不连通图,)在树中去掉任意一条边则构成一个不连通图,不再是树;在树中不相邻的两点之间添加一条边,不再是树;在树中不相邻的两点之间添加一条边,恰好形成了一个圈,也就不再是树。恰好形成了一个圈,也就不再是树。3)树中顶点的个数为)树中顶点的个数为P,则其边数必为,则其边数必为P-1。3、支撑树:设图、支撑树:设图T=(V,E)是图是图G(V,E)的)的子图,如果图子图,如果图T=(V,E)
10、是一个树,则称是一个树,则称T是是G的一个支撑树。的一个支撑树。4、寻找支撑树的方法、寻找支撑树的方法1)破圈法:在图中任取一个圈,从圈中去掉)破圈法:在图中任取一个圈,从圈中去掉任一边,对余下的图重复上述操作,即可任一边,对余下的图重复上述操作,即可得到一个支撑树。得到一个支撑树。2)避圈法:每一步选取与已选的边构不成圈)避圈法:每一步选取与已选的边构不成圈的边,直到不能继续为止。的边,直到不能继续为止。5、最小支撑树、最小支撑树最小支撑树:如果最小支撑树:如果T=(V,E)是是G的一个支撑树,的一个支撑树,称称E中所有边的权之和为支撑树中所有边的权之和为支撑树T的权,记的权,记为为w(T)
11、,即,即 w(T)=wij (vi,vj)T如果支撑树如果支撑树T*的权的权w(T*)是是G的所有支撑树的的所有支撑树的权中最小者,则称权中最小者,则称T*是是G的最小支撑树的最小支撑树(简简称最小树称最小树)w(T*)=min w(T)T3)求最小树的方法:)求最小树的方法:方法一方法一(避圈法避圈法)开始选一条最小权的边,以后每一步中,开始选一条最小权的边,以后每一步中,总从未被选取的边中选一条权最小的边,并使之与已选取总从未被选取的边中选一条权最小的边,并使之与已选取的边不构成圈。的边不构成圈。方法二方法二(破圈法破圈法)任取一个圈,从圈中去掉一条权最大的边。任取一个圈,从圈中去掉一条权
12、最大的边。在余下的图中,重复这个步骤,一直到一个不含圈的图为在余下的图中,重复这个步骤,一直到一个不含圈的图为止,这时的图便是最小树。止,这时的图便是最小树。例例 用破圈法求下图的最小树用破圈法求下图的最小树12222312222333445第二节 最短路问题一、引例:一、引例:如下图中如下图中V1:油田,:油田,V9:原油加工厂:原油加工厂求使从求使从V1到到V9总铺路设管道最短方案。总铺路设管道最短方案。V1V4V2V3V6V9V8V7V542466234442用图论来解释最短路用图论来解释最短路问题:在一个赋权有问题:在一个赋权有向图向图D(V,A,w)中,其中始点中,其中始点Vs,终,
13、终点点Vt,求从,求从Vs到到Vt的的一条路,使其为一条路,使其为Vs到到Vt的所有路中总权值的所有路中总权值最小的路。最小的路。二、最短路算法二、最短路算法1、情况一:、情况一:wij0(E.W.Eijkstra算法算法)原理:原理:Bellman最优性定理最优性定理方法:图上作业法(标号法)方法:图上作业法(标号法)标号:对于点标号:对于点Vi,若已求出若已求出V1到到Vi的最短值,标号(的最短值,标号(i,i)i:表示:表示V1到到Vi的最短路值的最短路值 i:表示最短路中最后经过的点表示最短路中最后经过的点标号法步骤:标号法步骤:1)给)给V1标号标号(0,Vs)2)把所有顶点分成两部
14、分)把所有顶点分成两部分,X:已标号的点;:已标号的点;X未标号的点未标号的点考虑与已标号点相邻的弧是存在这样的弧(考虑与已标号点相邻的弧是存在这样的弧(Vi,Vj),Vi X,Vj X若不存在,此问题无解,否则转若不存在,此问题无解,否则转3)3)选取未标号中所有入线的起点与未标号的点)选取未标号中所有入线的起点与未标号的点Vj进行计进行计算算:mini+wij=j并对其进行标号并对其进行标号(j,Vi),重复,重复2)2、情况二:、情况二:wij0设从设从V1到到Vj(j=1,2,t)的最短路长为的最短路长为P1jV1到到Vj无任何中间点无任何中间点 P1j(1)=w1jV1到到Vj中间最
15、多经过一个点中间最多经过一个点 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),则原问题无解,存在负回路。,则原问题无解,存在负回路。例:例:求下图所示有向图中从求下图所示有
16、向图中从v1到各点的到各点的最短路。最短路。v1v4v2v3v5v6v7v825-34674-23-1-342V1V2V3V4V5V6V7V8P1j(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年
17、年 第第4年年 第第5年年 购买费购买费 13 14 16 19 24 使用年数使用年数 0-1 1-2 2-3 3-4 4-5 维修费维修费 8 10 13 18 27 解解设以设以vi(i=1,2,3,4,5)表示表示“第第i年初购进一台年初购进一台新设备新设备”这种状态,以这种状态,以v6表示表示“第第5年末年末”这种状态;这种状态;以弧以弧(vi,vj)表示表示“第第i年初购置的一台设备一直使用到年初购置的一台设备一直使用到第第j年初年初”这一方案,以这一方案,以wij表示这一方案所需购置费表示这一方案所需购置费和维护费之和。和维护费之和。v1v2v3v5v6v421443222896
18、2316345244734273732(0,Vs)(21,V1)(31,V1)(44,V1)(62,V1)(78,V3)这样,可建立本例的网络模型。于是,该问题就这样,可建立本例的网络模型。于是,该问题就可归结为从图中找出一条从可归结为从图中找出一条从v1到到v6的最短路问题。的最短路问题。用用Dijkstra标号法,求得最短路为标号法,求得最短路为 v1v3v6 即第一年初购置的设备使用到第三年初予以更新,即第一年初购置的设备使用到第三年初予以更新,然后一直使用到第五年末。这样五年的总费用最然后一直使用到第五年末。这样五年的总费用最少,为少,为78。第三节第三节 最大流问题最大流问题 如下是
展开阅读全文