《2226图与网络分析.ppt》由会员分享,可在线阅读,更多相关《2226图与网络分析.ppt(87页珍藏版)》请在三一文库上搜索。
1、本讲学习目标,图与网络的基本知识 树及最小支撑树问题 最短路问题 网络最大流问题 最小费用最大流问题,图与网络的基本知识,哥尼斯堡七桥问题,一笔画问题,欧拉,一个图是由点和连线组成。(连线可带箭头,也可不带,前者叫弧,后者叫边),图的组成与表示,一个图是由点集 和 中元素的无序对的一个集合 构成的二元组,记为G =(V,E),其中 V 中的元素 叫做顶点,V 表示图G的点集合;E中的元素 叫做边,E 表示图 G 的边集合。,例,图1,无向图与有向图,如果一个图是由点和边所构成的,则称其为无向图(undirected graph) 如果一个图是由点和弧所构成的,那么称它为有向图(directed
2、 graph),记作D=(V, A),简单图与完全图,一条边的两个端点是相同的,那么称为这条边是环。 如果两个端点之间有两条以上的边,那么称为它们为多重边。 一个无环,无多重边的图称为简单图,一个无环,有多重边的图称为多重图。 每一对顶点间都有边相连的无向简单图称为完全图。 有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,以点v为端点的边的个数称为点v 的度(次),记作d(v) 度为零的点称为弧立点,度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点,度为偶数的点称为偶点。,d(v1)= ?4 d(v2)= ?3,度(次),定理1 所有顶点度数之和等于所有边数的
3、2倍。,所有顶点的入次之和等于所有顶点的出次之和。,有向图中,以 vi 为始点的边数称为点vi的出次,用 表示 ;以 vi 为终点的边数称为点vi 的入次, 用 表示;vi 点的出次和入次之和就是该点的次。 入次与出次有这样的关系:,定理2 在任一图中,奇点的个数必为偶数。,次数与边数的关系,设 G1=( V1 , E1 ),G2 =( V2 ,E2 )如果 V2 V1 , E2 E1 称 G2 是G1 的子图;如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图。,子图,支撑子图,子图与支撑子图,由两两相邻的点及其相关联的边构成的点边序列称为链。 如:v1,e1,v2
4、,e4,v4,记作(v1 ,v2,v4),链,圈、连通图,若链(v1,v2,vn),有v1=vn,则称之为圈 若链中所含的点均不相同则称为初等链 若图中任意两点之间均至少有一条链,则称此图为连通图,否则称为不连通图。,网络,给定一个图G=(V,E)或有向图D=(V,A),在V中指定两个点,一个称为始点(或发点),记作v1,一个称为终点(或收点),记作vn,其余的点称为中间点。对每一条弧 ,对应一个数 ,称为弧上的“权”。通常把这种赋权的图称为网络。,树及最小支撑树问题,树,一个连通的无圈的无向图叫做树。 树中次为1的点称为树叶,次大于1的点称为分支点。,树的性质,n 个顶点的树必有n-1 条边
5、。 树中任意两个顶点之间,恰有且仅有一条链(初等链)。 树连通,但去掉任一条边, 必变为不连通。 树无回路(圈),但不相邻的两个点之间加一条边,恰得到一个回路(圈)。,设连通图 是图G=(V , E )的一支撑子图,如果图 是一个树,那么称K 是G 的一个生成树(支撑树),或简称为图G 的树。,生成树,如果图 是图G的一个生成树,那么称E上所有边的权的和为生成树T 的权,记作S(T)。 如果图G的生成树T* 的权S(T*),在G 的所有生成树T 中的权最小,即 那么称T*是G 的最小生成树。,最小生成树,最小生成树的应用例子,某六个城市之间的道路网如图所示,要求沿着已知长度的道路联结六个城市的
6、电话线网,使电话线的总长度最短。,求最小支撑树的方法,避圈法 将所有边按权值从小到大排序,每次从未选的边中选一条权最小的,逐步衔接,但不接成圈 破圈法 任取一个圈,从中去掉权最大的边。在余下的图重复该步骤,直到不含圈为止,例:避圈法,v1,v2,v3,v4,v5,1,2,1,2,例:破圈法,课堂练习,P281:10.4;,最短路问题,最短路的一般提法为:设 为连通图,图中各边 有权 ( 表示 之间没有边), 为图中任意两点,求一条路 ,使它为从 到 的所有路中总权最短。即: 最小。,什么是最短路问题?,算法步骤: 1.给始点vs以P标号 ,这表示从vs到 vs的最短距离为0,其余节点均给T标号
7、, 。 2.设节点 vi 为刚得到P标号的点,考虑点vj,其中 ,且vj为T标号。对vj的T标号进行如下修改: 3.比较所有具有T标号的节点,把最小者改为P标号,即: 当存在两个以上最小者时,可同时改为P标号。若全部节点均为P标号,则停止,否则用vk代替vi,返回步骤(2)。,狄杰斯特拉(Dijkstra)算法,例、 用Dijkstra算法求下图从v1到v6的最短路。,解 (1)首先给v1以P标号,给其余所有点T标号。,(2),(3),(4),(5),(6),(7),(8),(9),(10),反向追踪得v1到v6的最短路为:,首先设任一点vi到任一点vj都有一条弧。 显然,从v1到vj的最短路
8、是从v1出发,沿着这条路到某个点vi再沿弧(vi,vj)到vj,则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长,P1i表示从v1到vi的最短路长,则有下列方程:,Warshall-Floyd算法,求解步骤,第1步,令 即用v1到vj的直接距离做初始解。 第2步,使用递推公式: 求 ,当进行到第t步,若出现 停止计算, 即为v1到各点的最短路长。 第3步,逆向追踪得到从v1到vj的最短路径,例,求图中v1到各点的最短路,最短路问题的应用案例,某企业使用一台设备,在每年年初,企业领导部门就要决定是购买新的(支付购置费),还是继续使用旧的(支付维修费),
9、试制定一个五年内设备更新的计划,使得总的支付费用最少。,解:(1)分析:可行的购置方案(更新计划)很多! 如: 1) 每年购置一台新的,则对应的费用为: 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年购置新的,一直用到第五年年底,则总费用为: 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。 (2)方法:将此问题用一个赋权有向图来描述,然后求这个赋权有向图的最短路。 设 Vi 表示第i年初,(Vi ,Vj )表示第i 年初购买新设备用到第j年初(j-1年底),而Wij 表示相应费用,则5年的一个更新计划相当于从V1 到V6的一条路。,例四、 某
10、工厂使用一种设备,这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备,每年需支付购置费用;若继续使用旧设备,需要支付维修与运行费用,而且随着设备的老化会逐年增加。计划期(五年)内中每年的购置费、维修费与运行费如表所示,工厂要制定今后五年设备更新计划,问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,作业,P282:10.7,10.8,课堂练习:,例1:10名研究生参加6门课程考试。由于选修内容不同,考试门数也
11、不一样。表1给出了每个研究生参加考试的课程(打#的)。规定考试在三天内结束,每天上下午各排一门。研究生提出希望每人每天最多考一门,又课程A必须在第一天上午考,课程F安排在最后一门,课程B只能安排在下午考。试列出一张满足各方面要求的考试日程表。,例2:某公司在六个城市c1,c6中有分公司,从ci到cj的直接航程票价记在下述矩阵中的(i,j)位置上(表示无直接航路)。请帮助该公司设计一张任意两城市间的票价最便宜的路线表。,最大流问题,设一个赋权有向图D=(V, E),在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧(vi , vj)E ,都有一个非负数cij,叫做弧的
12、容量。我们把这样的图D叫做一个容量网络,简称网络,记做 D=(V,E,C)。 网络D上的流,是指定义在弧集合E上的一个函数 其中f(vi ,vj) =fij 叫做弧(vi,vj)上的流量。,基本概念,称满足下列条件的流为可行流: (1)容量条件:对于每一个弧(vi ,vj)E有 0 fij cij (2)平衡条件: 对于发点vs,有 对于收点vt ,有 对于中间点,有,可行流中 fijcij 的弧叫做饱和弧,fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧,fij0 的弧叫做零流弧。,可行流,图中 为零流弧,其余为非饱和弧。,例,定理 可行流f 是最大流的充分必要条件是不存在从vs到vt
13、 的关于f 的一条可增广链。,增广链,是一个增广链,显然图中增广链不止一条,例,截集,例,容量为24,设 ,,则截集为,容量为20,求最大流的标号法,求最大流的标号法,调整过程 设 1令 2去掉所有标号,回到第一步,对可行流重新标号。,求下图所示网络中的最大流,弧旁数为,(1 ,1),v2,v1,v4,v3,vs,vt,(3 , 3),(5 , 1),(1 , 1),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,1),(vs,+),(-v1, 1),(+ vs , 4),(+v2,1),(+ v3 ,1),例,(-v2,1),最小截集,课堂作业:,P283:10.12;,最
14、小费用最大流问题,例 求网络的最小费用最大流,弧旁权是(bij , cij),已知网络G =(V,E,C,d),f是G上的一个可行流, 为一条从vs到vt的增广链, 称为链的费用。,结论:如果可行流 f在流量为W(f )的所有可行流中的费用最小,并且 *是关于f 的所有增广链中的费用最小的增广链,那么沿增广链u *调整可行流f,得到的新可行流f *也是流量为W(f*)的所有可行流中的最小费用流。当f * 是最大流时,就是最小费用最大流。,若 * 是从vs到vt的增广链中费用最小的增广链,则称 * 是最小费用增广链。,基本概念,寻找关于f 的最小费用增广链: 构造一个关于f 的赋权有向图L(f
15、) ,其顶点是原网络G的顶点,而将G中的每一条弧 ( vi, vj )变成两个相反方向的弧(vi, vj)和(vj , vi),并且定义图中弧的权lij为: 1.当 ,令 2.当(vj,vi)为原来网络G中(vi, vj)的反向弧,令 在网络G中寻找关于f 的最小费用增广链等价于在L(f )中寻求从vs 到vt 的最短路。,步骤: (1)取零流为初始可行流 ,f (0) =0。 (2)一般地,如果在第k-1步得到最小费用流 f (k-1),则构造图 L( f (k-1) )。 (3)在L( f (k-1) )中,寻求从vs到vt的最短路。若不存在最短路,则f (k-1)就是最小费用最大流;否则
16、转(4)。 (4)如果存在最短路,则在可行流f (k1)的图中得到与此最短路相对应的增广链,在增广链上,对f (k1)进行调整,调整量为:,令,得到新可行流f (k) 。对f (k)重复上面步骤,返回(2)。,例 求网络的最小费用最大流,弧旁权是(bij , cij),课堂练习:,表1给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题,画出网络图并求解数值解。,表1:,中国邮递员问题,连通图G中,若存在一条道路,经过每边一次且仅一次,则称这条路为欧拉道路。若存在一条回路,经过每边一次且仅一次,则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 定理 一个多重连通图G是
17、欧拉图的充分必要条件是G中无奇点。 推论 一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。,欧拉图,奇偶点图上作业法 (1)找出图G中的所有的奇顶点,把它们两两配成对,而每对奇点之间必有一条通路,把这条通路上的所有边作为重复边追加到图中去,这样得到的新连通图必无奇点。 (2)如果边e=(u,v)上的重复边多于一条,则可从重复边中去掉偶数条,使得其重复边至多为一条,图中的顶点仍全部都是偶顶点。 (3)检查图中的每一个圈,如果每一个圈的重复边的总长不大于该圈总长的一半,则已经求得最优方案。如果存在一个圈,重复边的总长大于该圈总长的一半时,则将这个圈中的重复边去掉,再将该圈中原来没有重复边的各边加上重复边,其它各圈的边不变,返回步骤(2)。,判定标准1: 在最优邮递路线上,图中的每一条边至多有一条重复边。 判定标准2 : 在最优邮递路线上,图中每一个圈的重复边总权小于或等于该圈总权的一半。,例 求解下图所示网络的中国邮路问题,图中数字为该边的长。,l12+2 l23+2 l36+ l89+2 l78+l69+l14+2 l47=51,课堂作业:,P283:10.15,
链接地址:https://www.31doc.com/p-2976014.html