版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
运筹学第十章图与网络分析第一页,共四十三页,编辑于2023年,星期三有向图:由点及弧所构成的图,记为D=(V,A),V,A分别是D的点集合和弧集合。一个方向是从vi指向vj的弧记为(vi,vj)图G或D中的点数记为p(G)或p(D),边(弧)数记为q(G)(q(D)),简记为p,q。若边e=[u,v]∈E,则称u,v为e的端点,也称u,v是相邻的,称e是点u(及点v)的关联边。若在图G中,某个边的两个端点相同,则称e是环。第二页,共四十三页,编辑于2023年,星期三若两个点之间有多于一条的边,称这些边为多重边。简单图:一个无环,无多重边的图。多重图:一个无环、但允许有多重边的图。给定一个图G=(V,E),如果图G’=(V’,E’),使V’=V及E’E,则称G’是G的一个支撑子图。点v的次:以点v为端点边的个数,记为dG(v)或d(v)。悬挂点:次为1的点。悬挂点的关联边称为悬挂边。第三页,共四十三页,编辑于2023年,星期三弧立点:次为零的点。定理1:图G=(V,E)中,所有点的次之和是边数的两倍,即Σd(v)=2qvV奇点:次为奇数的点。否则称为偶点。定理2:任一图中,奇点的个数为偶数。给定一个图G=(V,E),一个点边的交错序列(vi1,ei1,vi2,ei2,…,vik-1,eik-1,vik),如果满足eit=[vit,vit+1](t=1,2,…,k-1),则称为一条联结vi1第四页,共四十三页,编辑于2023年,星期三和vik的链,记为(vi1,vi2,…,vik),称点vi2,vi3,…,vik-1为链的中间点。链(vi1,vi2,…,vik)中,若vi1=vik,,则称之为一个圈,记为(vi1,vi2,…,vik-1,vi1)。若链(vi1,vi2,…,vik)中,点vi1,vi2,…,vik都是不同的,则称之为初等链;若圈(vi1,vi2,…,vik-1,vi1)中,vi1,vi2,…,vik-1都是不同的,则称之为初等圈。若链(圈)中含的边均不相同,则称之为简单圈。第五页,共四十三页,编辑于2023年,星期三连通图:图G中,若任何两个点之间,至少有一条链。连通分图(分图):若G是不连通图,它的每个连通的部分。基础图:给定一个有向图D=(V,A),从D中去掉所有弧上的箭头,所得到的无向图。记之为G(D)。给定D中的一条弧a=(u,v),称u为a的始点,v为a的终点,称弧a是从u指向v的。设(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一个点弧交错序列,如果这个序列在基础图G(D)第六页,共四十三页,编辑于2023年,星期三
中所对应的点边序列是一条链,则称这个点弧交错序列是D的一条链。如果(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一条链,并且对t=1,2,…,k-1,均有ait=(vit,vit+1),称之为从vi1到vik的一条路。若路的第一个点和最后一点相同,则称之为回路。第七页,共四十三页,编辑于2023年,星期三§2树2.1树及其性质定义1一个无圈的连通图称为树定理1设图G=(V,E)是一个树,p(G)≥2,则G中至少有两个悬挂点。定理2图G=(V,E)是一个树的充分必要条件是G中不含圈,且恰有p-1条边。定理3图G=(V,E)是一个树的充分必要条件是G是连通图,并且q(G)=p(G)-1。定理4图G是树的充分必要条件是任意两个顶点之间恰有一条链。第八页,共四十三页,编辑于2023年,星期三推论:(1).从一个树中去掉一条边,则余下的图是不连通的。(2).在树中不相邻的两个点间添上一条边,则恰好得到一个圈。2.2图的支撑树定义2设图T=(V,E’)是图的支撑子图,如果图T=(V,E’)是一个树,则称T是G的一个支撑树。定理5:图G有支撑树的充分必要条件是图G是连通的。第九页,共四十三页,编辑于2023年,星期三[证]必要性:显然。充分性:设图G是连通图,如果G不含圈,那么G本身是一个树,从而G是它自身的一个支撑子图G1。如果G含圈,任取一个圈,从圈中任意地去掉一条边,得到图G的一个支撑子图G1。如果G1不含圈,那么G1是G的一个支撑树(因G1是连通的);如果G1仍含圈,那么从G1中任取一个圈,从圈中再任意去掉一条边,得到图G的一个支撑子图G2,如此重复,最终可以得到G的一个支撑子图Gk,它不含圈,于是Gk是G的一个支撑树。第十页,共四十三页,编辑于2023年,星期三2.3最小支撑树问题定义3给图G=(V,E),对G中的每一条边[vi,vj],相应地有一个数wij,则称这样的图G为赋权图,wij称为边[vi,vj]上的权。设有一个连通图G=(V,E),每一边e=(vi,vj)有一个非负权w(e)=wij(wij≥0)定义4:如果T=(V,E’)是G的一个支撑树,称E’中所有边的权之和为支撑树T的权,记为w(T),即w(T)=Σwij
(vi,vj)∈T第十一页,共四十三页,编辑于2023年,星期三如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者,则称T*是G的最小支撑树(简称最小树)w(T*)=minw(T)T求最小树的方法:方法一(避圈法)开始选一条最小权的边,以后每一步中,总从未被选取的边中选一条权最小的边,并使之与已选取的边不构成圈。第十二页,共四十三页,编辑于2023年,星期三方法二(破圈法)任取一个圈,从圈中去掉一条权最大的边。在余下的图中,重复这个步骤,一直到一个不含圈的图为止,这时的图便是最小树。例用破圈法求下图的最小树12222312222333445第十三页,共四十三页,编辑于2023年,星期三§3最短路问题Dijkstra算法的基本思想:若{vs,v1,…,vk}是从vs到vk的最短路,则{vs,v1,…,vi}是从vs到vi的最短路。T(临时)标号:从vs到某一节点最短距离的上界。P(永久)标号:从vs到某一节点的最短距离。第十四页,共四十三页,编辑于2023年,星期三步骤:给vs标上永久标号P(vs)=0,其余节点标上临时标号T(vj)=∞(1)若节点vi是刚得到P标号的点。把与vi有弧(边)直接相连而且有属于T标号的节点,改为下列T标号T(vj)=min{T(vj),P(vi)+dij}(2)把T标号中标号最小的节点vj0的临时标号T(vj0)改为P(vj0),直至算法终止;否则转(1)第十五页,共四十三页,编辑于2023年,星期三例求节点v1到节点v5的最短距离及其路线vSv1v2v3v4v5122233344[解]P(vs)=0T(vj)=∞,j=1,…,5第一步:T(v1)=min{T(v1),P(vs)+ds1}=min{∞,0+4}=4(1)与节点vs直接相连的临时标号的节点为v1,v2,将这两个节点的临时标号改为第十六页,共四十三页,编辑于2023年,星期三T(v2)=min{T(v2),P(vs)+ds2}=min{∞,0+3}=3(2)在所有T标号中,最小的为T(v2)=3,于是令P(v2)=3第二步:(1)与节点v2直接相连的临时标号的节点为v3和v4,把这两个节点的T标号改为T(v1)=min{T(v1),P(v2)+d21}=min{4,3+2}=4T(v4)=min{T(v4),P(v2)+d24}=min{∞,3+2}=5(2).在所有T变化中,T(v1)=4最小,于是令P(v1)=4第十七页,共四十三页,编辑于2023年,星期三第三步:(1).与节点v1相连的临时标号的节点为v3,v4,把这两个节点的T标号改为T(v3)=min{T(v3),P(v1)+d13}=min{∞,4+3}=7T(v4)=min{T(v4),P(v1)+d14}=min{5,4+1}=5(2).在T标号中,T(v4)=5最小,令P(v4)=5第四步:(1).与节点v4相连的T标号有v3,v5把这两个节点的T标号改为第十八页,共四十三页,编辑于2023年,星期三T(v3)=min{T(v3),P(v4)+d43}=min{7,5+2}=7T(v5)=min{T(v5),P(v5)+d45}=min{∞,5+4}=9(2).T(v3)最小,P(v3)=7第五步:(1).与v3相连的临时标号有v5T(v5)=min{T(v5),P(v3)+d35}=min{9,7+3}=9(2).P(v5)=9最短路线:vs→v1→v4→v5vs→v2→v4→v5第十九页,共四十三页,编辑于2023年,星期三下面介绍当赋权有向图中,存在具负权的弧时,求最短路的方法。令d(1)(vs,vj)=wsj对t=2,3,…,d(t)(vs,vj)=min{d(t-1)(vs,vi)+wij}(j=1,2,…,p)若进行到某一步,例如第k步,对所有j=1,2,…,p,有d(k)(vs,vj)=d(k-1)(vs,vj)i第二十页,共四十三页,编辑于2023年,星期三则{d(k)(vs,vj)}j=1,2,…,p即为到各点的最短路的权。例求下图所示有向图中从v1到各点的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第二十一页,共四十三页,编辑于2023年,星期三
wijd(t)(v1,vj)v1v2v3v4v5v6v7v8v1v2v3
v4v5v6v7v8025-30-2406400-30720320t=1t=2t=3t=4t=5t=6025-3020-3611020-36615020-3361410020-336910020-336910说明:表中空格处为+。第二十二页,共四十三页,编辑于2023年,星期三例设备更新问题制订一设备更新问题,使得总费用最小第1年第2年第3年第4年第5年购买费1314161924使用年数0-11-22-33-44-5维修费810131827[解]设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种状态,以v6表示“第5年末”这种状态;以弧(vi,
vj)表示“第i年初购置的一台设备一直使用到第j年初”这一方案,以wij表示这一方案所需购置费和维护费之和。第二十三页,共四十三页,编辑于2023年,星期三这样,可建立本例的网络模型。于是,该问题就可归结为从图中找出一条从v1到v6的最短路问题。用Dijkstra标号法,求得最短路为v1v3v6
即第一年初购置的设备使用到第三年初予以更新,然后一直使用到第五年末。这样五年的总费用最少,为78。第二十四页,共四十三页,编辑于2023年,星期三v1v2v3v5v6v4214432228962316345244734273732(0)(21)(31)(44)(62)(78)第二十五页,共四十三页,编辑于2023年,星期三§4最大流问题如下是一运输网络,弧上的数字表示每条弧上的容量,问:该网络的最大流量是多少?vsv2v1v3v4vt432312234第二十六页,共四十三页,编辑于2023年,星期三4.1基本概念和基本定理(1)网络与流定义1给定一个有向图D=(V,A),在V中有一个发点vs和一收点vt,其余的点为中间点。对于每一条弧(vi,vj),对应有一个c(vi,vj)0,(cij)称为弧的容量。这样的有向图称为网络。记为D=(V,A,C)。网络的流:定义在弧集合A上的一个函数f={f(vi,vj)},称f(vi,vj)为弧(vi,vj)上的流量。(fij)第二十七页,共四十三页,编辑于2023年,星期三(2)可行流与最大流定义2满足下列条件的流称为可行流:1)0fijcij2)对于每一is,tfij=fji(vi,vj)A(vj,vi)A对于发点vs和收点vt,fsj–fjs=v(f)(vs,vj)A(vj,vs)A第二十八页,共四十三页,编辑于2023年,星期三ftj–fjt=–v(f)(vt,vj)A(vj,vt)A式中v(f)称为这个可行流的流量,即发点的净输出量(或收点的净输入量)。最大流问题:求一流{fij}满足0fijcijv(f)i=sfij–fji=0is,t–v(f)i=t且使v(f)达到最大。第二十九页,共四十三页,编辑于2023年,星期三(3)增广链给定可行流f={fij},使fij=cij的弧称为饱和弧,使fij<cij的弧称为非饱和弧,把fij=0的弧称为零流弧,fij>0的弧称为非零流弧。若是网络中连接发点vs和收点vt的一条链,定义链的方向是从vs到vt,则链上的弧被分成两类:前向弧:弧的方向与链的方向一致全体+后向弧:弧的方向与链的方向相反全体—第三十页,共四十三页,编辑于2023年,星期三定义3设f是一可行流,是从vs到vt的一条链,若满足下列条件,则称之为(关于流f的)一条增广链:在弧(vi,vj)+上,0fij<cij在弧(vi,vj)—上,0<fijcij(4)截集与截量设S,TV,ST=,我们把始点在S,终点在T中的所有弧构成的集合,记为(S,T)。定义4给定网络D=(V,A,C),若点集V被剖分为两个非空集合V1和V1,使vsV1,第三十一页,共四十三页,编辑于2023年,星期三vtV1,则把弧集(V1,V1)称为是(分离vs和vt的)截集。截集是从vs到vt的必经之路。定义5给定一截集(V1,V1),把截集(V1,V1)中所有弧的容量之和称为这个截集的容量(截量),记为C(V1,V1)。v(f)C(V1,V1)若对于一可行流f*,网络中有一截集(V1*,V1*),使得v(f*)=C(V1*,V1*),则f必是最大流,而(V1*,V1*),必定是容量最小的截集,即最小截集。第三十二页,共四十三页,编辑于2023年,星期三定理1可行流f*是最大流的充要条件是不存在关于f*的最大流。若f*是最大流,则网络中必存在一个截集(V1*,V1*),使得v(f*)=C(V1*,V1*)定理2任一网络D中,从vs到vt的最大流的流量等于分离vs,vt的最小截集的截量。4.2寻找最大流的标号法(FordFulkerson)思想:从一可行流出发,检查关于此流是否存在增广链。若存在增广链,则增大流第三十三页,共四十三页,编辑于2023年,星期三量,使此链变为非增广链;这时再检查是非还有增广链,若还有,继续调整,直至不存在增广链为止。过程:1)标号过程标号过程开始时,总先给vs标上(0,+),这时vs是标号而未检查的点,其余都是未标号的点。一般,取一个标号而未检查的点vi,对一切未标号的点vj;(1)若在弧(vi,vj)上,fij<cij,则给vj标号(vi,l(vj)),这里l(vj)=min[l(vi),cij–fij]。这时点第三十四页,共四十三页,编辑于2023年,星期三vj成为标号而未检查的点。(2)若在弧(vj,vi)上,fji>0,则给vj标号(–vi,l(vj)),这里l(vj)=min[l(vi),fji]。这时点vj成为标号而未检查的点。于是vi成为标号而已检查过的点。重复上述步骤,一旦vt被标上号,表明得到一条从vs到vt的增广链,转入调整阶段。若所有标号都已检查过,而标号过程进行不下去,则算法结束,这时的可行流就是最大流。第三十五页,共四十三页,编辑于2023年,星期三
2)调整过程首先按及其它点的第一个标号,利用“反向追踪”的方法,找出增广链。令调整量为=l(vt)令fij+
(vi,vj)+fij´=fij–(vi,vj)—
fij(vi,vj)去掉所有的标号,对新的可行流f´={fij´},重新进入标号过程。v(f´)=v(f)+第三十六页,共四十三页,编辑于2023年,星期三可结合下图理解其实际涵义。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第三十七页,共四十三页,编辑于2023年,星期三vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例求下列网络的最大流与最小截集。[解]一、标号过程(1)先给vs标上(0,+)。(2)检查vs,在弧(vs,v1)上,fs1=7,cs1=9,fs1<cs1,则v1的标号为(vs,l(v1)),其中第三十八页,共四十三页,编辑于2023年,星期三l(v1)=min{l(vs),cs1–fs1}=min{+,9–2}=2(3)检查v1,在弧(v1,v4)上,f14=7,c14=9,f14<c14,则v4的标号为(v1,l(v4)),其中l(v4)=min{l(v1),c14–f14}=min{2,3-1}=2(4)检查v4,在弧(v3
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 天然气开采业的资源管理考核试卷
- 体育锻炼中的受伤预防考核试卷
- 新材料在电力行业中的应用与发展前景考核试卷
- 印刷技术在智慧城市建设与公共交通中的应用考核试卷
- 商业活动泳池租赁协议
- 城市规划廉洁自律招投标协议
- 石英矿建设土石方施工合同
- 消费者权益仲裁协议书范本
- 教育机构设施施工协议
- 医疗器械供应链投标书
- 江苏省苏州市苏州园区五校联考2024-2025学年上学期八年级数学期中试题
- 颅骨缺损护理
- 2023年齐齐哈尔富裕县招聘警务辅助人员笔试真题
- 2024-2030年瓷砖行业市场现状供需分析及投资评估规划分析研究报告
- 2024年度一级注册消防工程师考试复习题库及答案(共1000题)
- 宾馆改造工程冬季施工方案
- 2024年餐厅服务员(高级)职业鉴定理论考试题库(含答案)
- 《人工智能基础》课件-AI的前世今生:她从哪里来
- 人教八年级上册英语第六单元《Section A (1a-2d)》教学课件
- 食品工业技术经济学智慧树知到期末考试答案章节答案2024年西华大学
- 家校携手 同心共育 四年期中考试家长会 课件
评论
0/150
提交评论