第章图与网络模型ppt课件.ppt
《第章图与网络模型ppt课件.ppt》由会员分享,可在线阅读,更多相关《第章图与网络模型ppt课件.ppt(41页珍藏版)》请在三一文库上搜索。
1、第十一章 图与网络模型,1 图与网络的基本概念 2 最短路问题 3 最小生成树问题 4 最大流问题 5 最小费用最大流问题,1,1 图与网络的基本概念,2,图论中图是由点和边构成,可以反映一些对象之间的关系。 例如:在一个人群中,对相互认识这个关系我们可以用图来表示,图11-1就是一个表示这种关系的图。,1 图与网络的基本概念,3,当然图论不仅仅是要描述对象之间关系,还要研究特定关系之间的内在规律,一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要的,如对赵等七人的相互认识关系我们也可以用图11-2来表示,可见图论中的图与几何图、工程图是不一样的。,1
2、图与网络的基本概念,4,如果我们把上面例子中的“相互认识”关系改为“认识” 的关系,那么只用两点之间的连线就很难刻画他们之间的关系了,这是我们引入一个带箭头的连线,称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。,1 图与网络的基本概念,无向图: 由点和边构成的图,记作G=(V,E)。 有向图: 由点和弧构成的图,记作D=(V,A)。 连通图: 对无向图G,若任何两个不同的点之间,至少存在一条链,则G为连通图。 回路: 若路的第一个点和最后一个点相同,则该路为回路。 赋权图: 对一个无向图G的每一条边(vi,vj),相应地有一个数wij,则称图G为赋权图,wi
3、j称为边(vi,vj)上的权。 网络: 在赋权的有向图D中指定一点,称为发点(记为vs),指定另一点称为收点(记为vt),其它点称为中间点,并把D中的每一条弧的赋权数cij称为弧(vi,vj)的容量,这样的赋权有向图D就称为网络。,5,2 最短路问题,最短路问题:对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路,使得这条路上所有弧的权数的总和最小,这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。 一、求解最短路的Dijkstra算法(双标号法) 步骤: 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I,没标号的点的
4、集合J以及弧的集合 3. 如果上述弧的集合是空集,则计算结束。如果vt已标号(lt,kt),则 vs到vt的距离为lt,而从 vs到vt的最短路径,则可以从vt 反向追踪到起点vs 而得到。如果vt 未标号,则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集,则转下一步。 4. 对上述弧的集合中的每一条弧,计算 sij=li+cij 。在所有的 sij中,找到其值为最小的弧。不妨设此弧为(Vc,Vd),则给此弧的终点以双标号(scd,c),返回步骤2。,6,2 最短路问题,例1 求下图中v1到v6的最短路 解:采用Dijkstra算法,可解得最短路径为v1 v3 v4 v6 各
5、点的标号图如下:,7,2 最短路问题,例2 电信公司准备在甲、乙两地沿路架设一条光缆线,问如何架设使其光缆线路最短?下图给出了甲乙两地间的交通图。权数表示两地间公路的长度(单位:公里)。 解:这是一个求无向图的最短路的问题。可以把无向图的每一边(vi,vj)都用方向相反的两条弧(vi,vj)和(vj,vi)代替,就化为有向图,即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,8,2 最短路问题,例2最终解得: 最短路径v1 v3 v5 v6 v7,每点的标号见下图,9,(
6、0,s) V1 (甲地),15,17,6,2,4,4,3,10,6,5,(13,3) v2,(22,6) V7 (乙地),V5 (14,3),V6 (16,5),V3 (10,1),V4 (18,5),2 最短路问题,例3 设备更新问题。某公司使用一台设备,在每年年初,公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备,就要支付一定的购置费,当然新设备的维修费用就低。如果继续使用旧设备,可以省去购置费,但维修费用就高了。请设计一个五年之内的更新设备的计划,使得五年内购置费用和维修费用总的支付费用最小。 已知:设备每年年初的价格表 设备维修费如下表,10,2 最短路问题,例3的解: 将
7、问题转化为最短路问题,如下图: 用vi表示“第i年年初购进一台新设备”,弧(vi,vj)表示第i年年初购进的 设备一直使用到第j年年初。 把所有弧的权数计算如下表:,11,2 最短路问题,(继上页) 把权数赋到图中,再用Dijkstra算法求最短路。 最终得到下图,可知,v1到v6的距离是53,最短路径有两条: v1 v3 v6和 v1 v4 v6,12,3 最小生成树问题,树是图论中的重要概念,所谓树就是一个无圈的连通图。,13,图11-11中,(a)就是一个树,而(b)因为图中有圈所以就不是树, (c)因为不连通所以也不是树。,3 最小生成树问题,14,给了一个无向图G=(V,E),我们保
8、留G的所有点,而删掉部分G的边或者说保留一部分G的边,所获得的图G,称之为G的生成子图。在图11-12中,(b)和(c)都是(a)的生成子图。 如果图G的一个生成子图还是一个树,则称这个生成子图为生成树,在图11-12中,(c)就是(a)的生成树。 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树,并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),3 最小生成树问题,一、求解最小生成树的破圈算法 算法的步骤: 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边(如果有两条或两条以上的边都是权数最大的边,则任意去掉其中一条)。 3、如果所
9、余下的图已不包含圈,则计算结束,所余下的图即为最小生成树,否则返回第1步。,15,3 最小生成树问题,例4 用破圈算法求图(a)中的一个最小生成树,16,图11-13,3 最小生成树问题,例5、某大学准备对其所属的7个学院办公室计算机联网,这个网络的可能联通的途径如下图,图中v1,v7 表示7个学院办公室,请设计一个网络能联通7个学院办公室,并使总的线路长度为最短。,17,解:此问题实际上是求图11-14的最小生成树,这在例4中已经求得,也即按照图11-13的(f)设计,可使此网络的总的线路长度为最短,为19百米。 “管理运筹学”软件有专门的子程序可以解决最小生成树问题。,4 最大流问题,最大
10、流问题:给一个带收发点的网络,其每条弧的赋权称之为容量,在不超过每条弧的容量的前提下,求出从发点到收点的最大流量。 一、最大流的数学模型 例6 某石油公司拥有一个管道网络,使用这个网络可以把石油从采地运送到一些销售点,这个网络的一部分如下图所示。由于管道的直径的变化,它的各段管道(vi,vj)的流量cij(容量)也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油,问每小时能运送多少加仑石油?,18,v5,4 最大流问题,19,我们可以为此例题建立线性规划数学模型: 设弧(vi,vj)上流量为fij,网络上的总的流量为F,则有:,4 最大流问题,20,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第章图 网络 模型 ppt 课件
链接地址:https://www.31doc.com/p-2631785.html