图与网络分析.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《图与网络分析.pptx》由会员分享,可在线阅读,更多相关《图与网络分析.pptx(160页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、例1、有甲、乙、丙、丁、戊五个球队,它们之间比赛的情况也可以用图表示出来。V1V2V3V4V5e5e4e1e2e3e6e7一、图基本概念第1页/共160页例2 某单位储存八种化学药品,其中某些药品是不能存放在同一个库房里的。为了反映这个情况可以用点V1,V2,V8分别代表这八种药品,若药品Vi和药品Vj是不能存放在同一个库房的,则在Vi和Vj之间连一条线。V1V2 V3 V4 V5 V8 V7 V6第2页/共160页图的表示方法:一般地,当用图论研究一个实际问题时,常以顶点(Vertex)表示要研究的对象,以它们之间的连线,表示某种关系,这种连线称为边(Edge),目的是为了解决某个极值问题。
2、图中的点用v表示,边用e表示。对每条边可用它所连接的点表示,记作:e1=v1,v1;e2=v1,v2;第3页/共160页运筹学中研究的图具有下列特征:强调点与点之间的关联关系,不讲究图的比例大小与形状;每条边上赋有一个权;建立网络模型,求最大值或最小值。第4页/共160页下图可以提出很多极值问题142653876 63162 7 433716第5页/共160页v3e7e4e8e5e6e1e2e3v1v2v4v5 端点,关联边,相邻若有边e可表示为e=vi,vj,称vi和vj是边e的端点,反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联,称点vi和vj相邻;若边ei和ej具有公共的
3、端点,称边ei和ej相邻。二、关于图的另外一些名称和术语:第6页/共160页 环,多重边,简单图如果边e的两个端点相重,称该边为环。如右图中边e1为环。如果两个点之间多于一条,称为多重边,如右图中的e4和e5,对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5第7页/共160页 次,奇点,偶点,孤立点与某一个点vi相关联的边的数目称为点vi的次(也叫做度),记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点,次为偶数的点称作偶点,次为1的点称为悬挂点,次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5
4、图的次:一个图的次等于各点的次之和。第8页/共160页定理1 任何图中,顶点次数之和等于所有边数的2倍。定理2 任何图中,次为奇数的顶点必为偶数个。证明:由于每条边必与两个顶点关联,在计算点的次时,每条边均被计算了两次,所以顶点次数的总和等于边数的2倍。证明:设V1和V2分别为图G中奇点与偶点的集合。由定理1可得:2m为偶数,且偶点的次之和 也为偶数,所以 必为偶数,即奇数点的个数必为偶数。第9页/共160页 链,圈,连通图图中某些点和边的交替序列,若其中各边互不相同,且对任意vi,t-1和vit均相邻称为链。用表示:v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈
5、。如果每一对顶点之间至少存在一条链,称这样的图为连通图,否则称图不连通。第10页/共160页 子图,部分图(支撑子图)图G1=V1、E1和图G2=V2,E2如果有 称G1是G2的一个子图。若有 ,则称G1是G2的一个部分图(支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)(G图)第11页/共160页 网络(赋权图)赋权图):权可以代表距离、费用、通过能力(容量)等等。无向网络:端点无序的赋权图称为.有向网络:端点有序的赋权图称为。910201571419256第12页/共160页 图的矩阵描
6、述:邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵对于图G=(V,E),|V|=n,|E|=m,有nn阶方矩阵A=(aij)nn,其中第13页/共160页图的基本概念与模型v5v1v2v3v4v64332256437例6.2 下图所表示的图可以构造邻接矩阵A如下第14页/共160页对于赋权图G=(V,E),其中边 有权 ,构造矩阵B=(bij)nn 其中:2.2.权矩阵权矩阵第15页/共160页v5v1v2v3v4v64332256437例6.4 下图所表示的图可以构造权矩阵B如下:第16页/共160页G=(V,E)矩阵表示矩阵表示A A 邻接矩阵B B 关联矩阵边e=u,v 关联边 端点 重重合
7、合环多重边 平行边平行边简单图不含不含多重图含含点的次点的次 0 1 奇数 偶数 子图子图生成子图孤立点悬挂点奇点偶点顶点数p边数q点边关系各种链的概念第17页/共160页欧拉图与中国邮路问题欧拉图哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡(现名加里宁格勒)是欧洲一个城市,哥尼斯堡(现名加里宁格勒)是欧洲一个城市,PregeiPregei河把该城分成两河把该城分成两部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时人们提出这样的问题:有没有办法从某处(如人们提出这样的问题:有没有办法从某处(如A A)出发,经过各桥
8、一次且仅)出发,经过各桥一次且仅一次最后回到原地呢?一次最后回到原地呢?第18页/共160页Cab图 4-10 ad哥尼斯堡七桥问题第19页/共160页acbd(b)第20页/共160页 定理2 连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。定义1.在连通无向图G中,若存在经过每条边恰好一次的一个圈或一条链,就称此圈或链 为欧拉圈或欧拉链。若图G含一条欧拉圈,则称为欧拉图。定理1 连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。(G中无奇次顶点)第21页/共160页欧拉链欧拉图第22页/共160页中国邮路问题第23页/共160页定理3 使图G成为总权最小的欧拉图的充要条件是:(
9、1)在有奇次顶点的图G中,通过加重复边的方法使图不再包含奇次顶点,但原图的每条边最多只能加一条重复边。(2)在图G的每个回路上,重复边之总权不超过该回路非重复边之总权。(或回路总长的一半)第24页/共160页 例1 试为图4-13(a)构成总权最小的欧拉图。图中线旁的数字为相应边的权。124332124(a)图4-13第25页/共160页例2 试为图4-14(a)所示的街道规划最优投递路线。解:可按以上所述步骤进行,最终结果示于图4-14(b),总权等于52,重复边的长度等于10。1334333333222图4-14(a)2第26页/共160页413 333333 322 图4-14(b)22
10、第27页/共160页第二节 树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例6.2 乒乓求单打比赛抽签后,可用图来表示相遇情况,如下图所示。ABCDEFGH运动员第28页/共160页例6.3 某企业的组织机构图也可用树图表示。第29页/共160页 树:无圈的连通图即为树性质1:任何树中必存在次为1的点。性质2:n 个顶点的树必有n-1 条边。性质3:树中任意两个顶点之间,恰有且仅有一条链。性质4:树连通,但去掉任一条边,必变为不连通。性质5:树无回圈,但不相邻的两个点之间加一条边,恰得到一个圈。v1v2v3v4v5v6第30页/共160页 图的最小部分树(支撑树)如果G
11、2是G1的部分图,又是树图,则称G2是G1的部分树(或支撑树)。树图的各条边称为树枝,一般图G1含有多个部分树,其中树枝总长最小的部分树,称为该图的最小部分树(或最小支撑树)。v1v2v3v4v5v1v2v3v4v5G1G2第31页/共160页 例如,图4-18(a)是一个有四个顶点(n=4)的连通图,它共有 nn-2=42=16个生成树。V1V2V3V4图4-18(a)第32页/共160页第33页/共160页第34页/共160页a ab bc cf fe ed dh hg gb bf fe ed d第35页/共160页a ab bc cf fe ed dh hg gb bf fd dg g第
12、36页/共160页b bc ce ed da ab bc cf fe ed dh hg g第37页/共160页a ab bc ch ha ab bc cf fe ed dh hg g第38页/共160页a af fd dg ga ab bc cf fe ed dh hg g第39页/共160页 赋权图中求最小树的方法:破圈法和避圈法赋权图中求最小树的方法:破圈法和避圈法破圈法:任取一圈,去掉圈中最长边,直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数n-1=5第40页/共160页v1v2v3v4v5v643521得到最小树:Min C(T)=15第4
13、1页/共160页避圈法:去掉G中所有边,得到n个孤立点;然后加边。加边的原则为:从最短边开始添加,加边的过程中不能形成圈,直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618第42页/共160页v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15第43页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习:练习:应用破圈法求最小树应用破圈法求最小树第44页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v
14、6v6202015159 9161625253 3282817174 41 123233636第45页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第46页/共160页树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第47页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第48页/共160页v1v1v7
15、v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第49页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323第50页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323第51页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323第52页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6
16、v69 925253 3282817174 41 12323第53页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第54页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第55页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57第56页/共160页练习:练习:应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015
17、159 9161625253 3282817174 41 123233636第57页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第58页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第59页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第60页/共160页v1v1v7
18、v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第61页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第62页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57第63页/共160页课堂练习:课堂练习:3749346321
19、Min C(T)=12Min C(T)=15254173314475答案:第64页/共160页34122323242Min C(T)=12213638534567454321Min C(T)=18第65页/共160页 一某一点到另一点的最短路的Dijkstra法二所有点对间的最短路 返回第三节 最短路问题第66页/共160页就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题,如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题,也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。第67页/共160页 里特城(Littletown)是一个乡
20、村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路,从消防站到任何一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素,所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。例子:里特城 的消防队问题第68页/共160页第69页/共160页最短路:O A B E F T 19 英里第70页/共160页一、求最短路的Dijkstra算法 1、算法的基本思想第71页/共160页2、步骤:(1)、给vs以P标号,P(vs)=0,其余各点均给T标号,T(vi)=+。(2)、若vi点为刚得到P标号的点,考虑这样的点vj:(vi,vj)属于E,且vj
21、为T标号。对vj的T标号进行如下的更改:T(vj)=minT(vj),P(vi)+lij(3)、比较所有具有T标号的点,把最小者改为P标号,若全部点均为P标号则停止,否则转(2)。第72页/共160页v1v8v7v6v5v4v3v24645675795414例、用Dijkstra算法求下图中v1v8点的最短路。第73页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)T()T()T()T()T()T()T()第74页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)T()T()T()T()T()T()T()第75页/共160页
22、v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)T(6)T()T()T()T()T()第76页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)T(6)T()T()T()T()T()第77页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(v1,4)T(6)T(9)T(8)T()T()T()第78页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)T(9)T(8)T()T()T()第79页/共160页v1v8v
23、7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)T(9)T(8)T()T()T()第80页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)T(9)P(8,v2)T()T()T()第81页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)T(9)P(8,v2)T()T()T()第82页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)T(9)P(8,v2)T(14)T(
24、13)T()第83页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)T(9)P(8,v2)T(14)T(13)T()第84页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)P(8,v2)T(14)T(13)T()P(9,v2)第85页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)P(8,v2)T(14)T(13)T()P(9,v2)第86页/共160页v1v8v7v6v5v4v3v24645675795
25、414P(0,v1)P(4,v1)P(6,v1)P(8,v2)T(14)T()P(9,v2)P(13,v5)第87页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)P(8,v2)T(14)T()P(9,v2)P(13,v5)第88页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)P(8,v2)T(14)T(17)P(9,v2)P(13,v5)第89页/共160页v1v8v7v6v5v4v3v24645675795414P(0,v1)P(4,v1)P(6,v1)P(8,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络分析
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内