版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第六章 图与网络分析,北京物资学院信息学院 2011年5月,北京物资学院运筹学课件,本章主要内容,1 图的基本概念 2 最小树问题 3 最短路问题 4 网络的最大流问题 5 最小费用最大流*,1 图的基本概念,具体问题的图:城市之间的铁路交通图、电话线分布图、煤气管道图、航空线路图等。 抽象问题的图:5支球队进行比赛的关系图 一群人的认识关系图。,图是反映对象之间关系的一种工具,如果我们把对象用点表示,关系用线表示,就构成了一个图。,关系,对称的关系:甲与乙有这种关系,则乙与甲也有这种关系,如两点之间的距离等。 不对称的关系:甲与乙有这种关系,但乙与甲未必有这种关系:如两个人的认识关系,比赛结
2、果、交通路线中的单行线等。,关系的表示,对称的关系用边表示:e=vi,vj或e=vj,vi 不对称的关系用带箭头的弧表示:a=(vi,vj),图的分类: 无向图:G=(V,E) 有向图:D=(V,A),一般用p 和 q 分别表示一个图中的顶点数和边数,一、无向图中的一些概念,边的端点 e1=v1,v2,称v1,v2 相邻,e是v1及v2 的关联边,环:两个端点相同的边; 多重边:两个端点之间多于一条的边; 简单图:无环、无多重边的图; 多重图:无环、但允许有多重边的图,点的次(度):以v为端点的边的条数,称为点v的次, 记为dG(v)或d(v).(在计算点的次时,一个环算2次) 悬挂点:次为1
3、的点;悬挂边:悬挂点的关联边; 孤立点:次为0的点; 奇点:次为奇数的点;偶点:次为偶数的点。,定理1. 图G=(V,E)中,所有点的次之和是边数的两倍.即,定理2. 任一个图中,奇点的个数是偶数。,证明:设V1和V2分别是G中奇点和偶点的集合,由定理1,有,链:图G=(V,E)中一个点边交替的序列,如果满足,则称之为一条联结vi1和vik的链。,简单图中的链可以简记为,链的起点、中间点、终点,圈:起点和终点重合的链。,简单链(圈):链(圈)中所含的边均不相同。 初等链(圈):链(圈)中所含的点均不相同。又称为路(回路),连通图:任何两个顶点之间至少有一条链的图。 连通分支:不连通图的每一个连
4、通的部分图。,子图、支撑子图:图G=(V,E), G=(V,E),若VV,EE,则称G是G的子图;V= V,EE,则称G是G的支撑子图(部分图)。,割集:设G=(V,E),SV, T=VS, (S,T)=e|e=vivj, viS, viT 则称(S,T)是G的一个割集。,完全图:一个简单图中若任意两点之间均有边相连,则称之为完全图。 偶图(二分图):如果一个图的顶点能够分成两个不相交的非空集合V1,V2,使同一集合中任意两点之间均不相邻,则称之为偶图(二分图)。(完全二分图),二、有向图中的一些概念,给定有向图D=(V,A). 基础图:从D中去掉所有弧上的箭头后得到的无向图称为D的基础图,记
5、为G(D). 弧的始点、终点:a=(u,v),u为始点,v为终点。 链:D中的一个点弧交替序列,如果在基础图中对应的是一条链,则称之为D的一条链。(弧可以是逆向的) 路:如果一条链中的所有弧都是正向的,则称为一条路。 回路:起点和终点相同的路称为回路。 (简单路回路)、初等路(回路)可以类似定义。,引例:自来水管道的铺设问题 A点(水源); 需要使用自来水的场所共有7个: v1,v2,v7; 问题:为了各个场所都用上自来水,怎样铺设管道才能使挖开的道路数目最少?,共挖开9条路,共挖开6条路,2 最小树问题,树的定义及性质 图的支撑树 最小树问题,树的定义及性质,定义:无圈的连通图称为树.,e1
6、,e2,e4,e3,v4,v1,v5,v3,v2,v6,v7,v8,e5,e6,e7,树的性质: 1.设G是一个树,p(G)2,则G中至少有两个悬挂点。 2.如下三个论断中的两个保证G是树:(1)连通;(2)无圈; (3)q(G)=p(G)-1. 3. G=(V,E)是一个树的充要条件是G中任意两个顶点间有且仅有一条链。 4.从一个树中去掉任意一条边,则余下的图是不连通的。 5.在树中不相邻的两个点间添上一条边,恰好得到一个圈。,e1,e2,e4,e3,v4,v1,v5,v3,v2,v6,v7,v8,e5,e6,e7,图的支撑树(部分树),定义:设T=(V,E)是图G=(V,E)的支撑子图,如
7、果T=(V,E)是一个树,则称T是一个支撑树。,图 G,G的一个支撑树,连通图的支撑树满足: (1)支撑性;(2)连通性;(3)无圈性。,2. 求连通图的支撑树的方法:,支撑性 连通性,无圈性,破圈法,支撑性 无圈性,连通性,避圈法,连通性 无圈性,支撑性,反圈法,破圈法,找圈、破圈、直到无圈为止,A,v1,v2,v3,v4,v7,v6,v5,避圈法,(1)由连通图的所有顶点生成一个不含边的子图; (2)加边,但不能生成圈,直到连通为止。,反圈法,把图的顶点分成S和VS两部分,则割集(S,VS)中必有一条边包含在图的支撑树中。,S,VS,思考:假若考虑道路的长度,要求挖开的路面总长度最短,问题
8、该如何解决?,这就是我们接下来要介绍的最小树问题,最小树问题,赋权图:给图G=V,E中的每一条边vi ,vj赋上一个数字wij,称这样的图为赋权图, wij称为边vi ,vj上的权。 权可以表示距离、时间、费用等,通常为非负值。,支撑树的权:如果T=(V,E)是G的一个支撑树,则称E中所有边的权之和为支撑树T的权,记为w(T)。即,上例中支撑树的权为 3+7+5+2+2+3+4=26,最小支撑树:如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者,则称T*是G的最小支撑树(简称最小树)。,最小树问题:求一个赋权图的最小支撑树。,求最小树的方法,1. 破圈法 2. 加边法 3. 避圈法,破
9、圈法,从赋权图中任取一个圈,去掉圈中权最大的边,直到无圈为止。,A,v1,v2,v3,v4,v7,v6,v5,2,3,7,4,3,5,5,2,4,5,6,2,7,加边法,Step 1 将赋权图G中的所有边按权从小到大排序; Step 2 取G的所有顶点生成一个不含边的图T; Step 3 将G的边按权从小到大的顺序依次添加到T中,使T中不含圈,直到T成为连通图为止。(对于形成圈的边不添加),避圈法,定理:把图的顶点分成S和 VS两部分,则割集(S,VS)中权最小的边必包含在图的最小支撑树中。,7,5,2,10,S,VS,Step 1 从图G中任取一点vi, 让viS, 其余各点均包含在S=VS
10、中。 Step 2 从(S,S)中选一条权最小的边e=vivj,加到T中。 Step 3 令S vjS, SvjS,(将所选边的另一个顶点添加到S中)。 Step 4 重复2、3两步,直到图中所有点均包含在S中为止。,作业:1. 分别用三种方法求下图的最小支撑树,2,5,4,3,1,7,4,3,4,1,5,7,v1,v2,v3,v4,v5,v6,v7,水源,2. 某农场的水稻田用堤埂分割成很多小块。为了用水灌溉,需要挖开一些堤埂。问最少挖开多少条堤埂,才能使水浇灌到每小块稻田?,3 最短路问题,问题的提出 最短路问题的Dijkstra算法 求任意两点之间最短距离的矩阵算法,问题的提出,例1.
11、已知如图所示交通网络图,边旁的数字表示通过这段路所需要的费用,现某人要从v1出发到v8去,问他该走哪条路线才能花费最少?,该问题就是要在赋权图中所有从v1到v8 的路中,找一条权最小的路。称之为最短路。 其中路的权指路上所有边对应的权之和,又称为路长。,2. 最短路问题的Dijkstra算法,当边(弧)权wij 0 时,目前公认的求最短路的最好算法是由Dijkstra于1959年提出的,称为Dijkstra算法。这个算法事实上可以求出从一个给定的点到任意点的最短路。,算法的基本原理:,问:1.上图中从v1 到v3 的最短路分别是多少? 2.两图中从v1 到v3 的边权相等,为什么最短路不同?,
12、3. 假若v2 到v3 的边权不知道(如下图),还能否确定从v1到v3的最短路?,左图无法确定,右图中最短路为从v1直接到v3,路长为8.,例:某人要从甲地到乙地,可以选择的路线共有4条,分别需要经过A、B、C、D四个地方,如下图。假如经过A、B去乙地的路长已知;而从甲地经过C、D到乙地的路长未知,但是从甲到C、D的路长已知,分别为20、45公里,那么能否确定从甲地经过A、B、C、D哪个地方去乙地最近?,很明显,选择经过A到乙地一定是最短的路。因为从C、D到乙地的路长虽然还不知道,但是根据已知条件,可以推断出它们的路长一定比12公里长,所以不会比经过A到乙地短。,算法的实现过程: 从起点出发,
13、逐步向外探寻最短路,直到终点。,探寻最短路的方式:,给顶点标号 (标出从起点到各顶点的最短路及路长) 一旦找到从起点到vi的最短路,我们就给顶点vi标上标号,其中 (a)起点vs的标号为0,0; (b)顶点vi的标号为Lsi,i ,其中Lsi 表示从vs到vi的最短路的路长, i用来说明顶点vi的标号是从哪个顶点得到的(最短路的来源)。,算法的步骤: 1.给始点vs(最短路的起点)标号0,0。 2.确定割并计算相应的指标值: 由所有一个端点已标号另一个端点未标号的边构成割,记为:,对割里的每一条边(vi,vj),按下式计算指标kij值: kij = Lsi+ wij 即kij等于边(vi,vj
14、)中的已标号点vi的标号(Lsi,i)中的Lsi加上边(vi,vj)的权wij。,3 扩大标号范围。 找出当前割中指标值最小的一条边,给该边的未标号点vj标号(kij ,vi)。 4.重复2、3两步,直到终点vt得到标号为止。,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,例求例1中v1到v8的最短路,0,0,3,算例:,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,3,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,7,v
15、1,3,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,7,v1,3,8,v1,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,7,v1,3,8,v1,12,v4,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,7,v1,3,8,v1,12,v4,14,v4,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,7,v1,3,8,v1,12,v4,14,v
16、4,14,v5,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,7,v1,3,8,v1,12,v4,14,v4,14,v5,19,v7,最短路为: v1 v4 v5 v7 v8 路长为19,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0,0,6,v1,7,v1,3,8,v1,12,v4,14,v4,14,v5,19,v7,最短路为: v1 v4 v5 v7 v8 路长为19,例求例1中v1到v8的最短路,例3:求下图中v1到v8的最短路。,0,0,1,V1,3,V1,3,V4,5,V3
17、,6,V2,8,V5,9,V5,10,V5,11,V9,最短路长为11。 (1) v1v4v3v2v5v9v8 (2) v1v3v2v5v9v8,.求任意两点之间最短距离的矩阵算法,Dijkstra算法提供了求图中从给定点到任一其它点的最短路的方法。 若需要计算图中任意两点之间的最短距离。如何计算?,定义图中任意两点之间的邻接距离矩阵D(0) 构造任意两点之间最多经过一个中间点即可到达的最短距离矩阵D(1) 再构造D(2) , 表示最多经过2个中间点即可到达的最短距离矩阵 直到D(k) =D(k-1),v1,v5,v2,v3,3,6,5,5,2,2,4,v4,D(3)=D(2),作业:求下图中
18、v1到其它各点的最短路及路长,8,2,5,6,7,7,2,2,9,6,2,3,5,2,v1,v2,v3,v4,v5,v6,v7,v8,4 网络的最大流问题,问题的提出 基本概念与基本定理 寻求最大流的标号法(Ford Fulkerson),问题的提出,下图为联结某产品的产地v1和销地v6的交通网,每一条弧(vi,vj)代表从vi到vj的运输线,弧旁的数字表示运输线的最大通过能力,产品经过交通网从v1运到v6, 要求制定一个运输方案,使从v1运到v6的产品数量最多。,v1,v2,v3,v4,v5,v6,10,8,4,5,3,5,6,3,11,9,基本概念与基本定理,1.网络与流 网络: D=(V
19、,A,C),满足下列条件: (1)有向图; (2)有一个发点(vs)、一个收点(vt)和若干中间点; (3)每一条弧(vi,vj)A都对应一个容量c(vi,vj)0.,网络上的流:定义在弧集合上的一个函数f=f(vi,vj) (或简写为fij). 称 f(vi,vj)为弧(vi,vj)上的流量。,零流:若网络上所有的fij=0.,2. 可行流与最大流 可行流:满足以下条件的流 1) 容量限制 :对任意 (vi,vj)A ,0 fij cij 。 2) 平衡条件: 中间点:流入量=流出量 发点:流出量-流入量=流量v(f) 收点:流入量-流出量=流量v(f),最大流问题: 求一个可行流fij,使
20、v(f)达到最大。,3.增广链,给定一个可行流,网络中的弧可以分为:,饱和弧 非饱和弧,零流弧 非零流弧,给定一条从发点vs到收点vt的链,定义链的方向是从vs到vt,则链上的弧被分成两类: (1)前向弧 + (2)后向弧 -,增广链:从发点vs到收点vt的链,若满足:每一条前向弧都是非饱和弧,每一条后向弧都是非零流弧,则称之为增广链。,4. 割集与割的容量,割集的容量:,任何一个可行流的流量都不会超过任何一个割集的容量,定理2:可行流 f*是最大流的充要条件是D中不存在关于f*的增广链。,3. 寻求最大流的标号法(Ford Fulkerson),算法的思想:从一个可行流开始,寻找增广链。若找
21、到就调整可行流;若找不到增广链,则当前的可行流就是最大流。,算法的实现: (1)标号过程 (给顶点标号,寻找增广链) (2)调整过程 (增加当前可行流的流值),该算法是由Ford和Fulkerson于1956年提出的,又称Ford-Fulkerson算法。,(1)标号过程:,检查的过程就是给邻点标号的过程。,当所有vi的邻点都检查之后,vi成为标号已检查的点,而新得到标号的点成为标号未检查的点。,重复上述过程,直到vt得到标号或标号范围无法扩大为止。 若vt得到标号,则可找到一条增广链,否则算法结束。,(2)调整过程 倒向追踪找到一条增广链,令调整量,去掉标号,重复(1)(2)两个过程。,例1:用标号法求下列网络的最大流,s,t,v1,v2,v3,v4,(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年猎头行业行业痛点与解决方案报告
- 2026年保健食品细分市场研究报告:行业增长潜力分析
- 2026年物流行业组织架构优化与部门职责流程再造报告
- 2026年写字楼市场政策影响与商业地产投资策略报告
- 2026年汽车行业智能化升级报告及未来五年发展趋势分析
- 2026年医药行业报告:创新药物发展与市场前景分析
- 2026年电子信息制造行业分析报告:智能技术绿色生产新篇章
- 2026年健康产业市场细分与消费者需求分析报告
- 2026年区块链技术应用行业硬件销售前景研究报告
- 2026年信息技术行业资金链稳定与分红策略报告
- 2026年医疗保险审核部门面试题及应对策略
- 2026-2031中国法兰行业市场前景分析预测报告
- 施工便道临时方案
- 信息科技课程标准2025年版
- 眼科手术并发症处理规定
- 风机叶片覆冰安全培训课件
- 2025云南曲靖市人力资源和社会保障局招聘公益性岗位工作人员3人考试参考题库及答案解析
- 医院服务接待礼仪
- 腹部超声常见疾病诊断要点
- 《中职语文基础知识手册》全套教学课件
- 【MOOC】人工智能与信息社会-北京大学 中国大学慕课MOOC答案
评论
0/150
提交评论