《图与网络模型》PPT课件.ppt

《《图与网络模型》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图与网络模型著名哥尼斯堡七桥问题:欧拉(1736).中国邮递员问题：中国管梅谷（1962）CDB135246AACBD例：铁路线状况很多问题用图表示简单明了点和边组成的称之图北京天津济南青岛郑州徐州连云港武汉南京上海e1e2e3e4e5e6e7e8e9e10例：球队比赛状况（用点表示五个球队，用边表示两队之间比赛过）例：人际关系(用点表示人，用弧表示谁认识谁的认识关系)甲(V1)乙(V2)丙(V3)丁(V4)戊(V5).赵(V1)孙(V2)钱(V3)李(V4)周(V5)陈(V6)吴(V7)e15e12e13e14e23e34e54e12e13e32e2

2、4e67e45e65无向图(简称图)，记为G（V，E）有向图(点和弧组成，弧有方向)，记为G（V，A）无向图中的链、圈连通图树：不存在圈的连通图支撑树：树的顶点及其个数＝连通图的顶点及个数有向图中的路基本术语网络规划问题最小支撑树问题最短路问题网络最大流问题最小费用流问题将庞大复杂的工程系统和管理问题用图描述,可以解决工程设计和管理决策的最优化问题.如,完成任务的时间最少,距离最短,费用最省等等.最小支撑树问题赋权图图中每条边上都赋予一个权数，该权数可代表很多实际含义，如代表长短、时间、费用，等等最小支撑树问题寻找图中的一个支撑树，其权（构成树的所有边上的权

3、数之和，称为树的权）最小。破圈法（也可用软件求解）例：某工厂内联结六个车间的道路网如图所示，图中每条边上的权数代表道路的长。如果沿道架设联结六个车间的电话线网，怎样架设节省材料？最小支撑树如下，其权＝15V6V4V2V5V3V161557244352134特点：要求连通到每个顶点某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，每条边上的权数为这条路的长度，单位为百米。请设计一个网络能联通7个学院办公室，并且线路长度最短。V1V2V3V4V5V6V7333104541782设计网络的线路长度为19（百米）最小支撑树问题的应用电信

4、网络（计算机网络、电话专用线网络、有线电视网络，等等）的设计运输网络的设计，使得网络中提供链接的部分（如铁路、公路，等等）的总成本最小。高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短。连接多个场所的管道网络设计（煤气、水）最短路问题最短链问题：在一个赋权的无向图中，寻找指定两点之间的一条链，此链上所有边的权数之和最小。最短路问题：在一个赋权的有向图中，寻找指定两点之间的一条路，此路上所有弧的权数之和最小。方法：Dijkstra标号法特点：联接指定的两顶点V6V4V2V5V3V1615572443524某工厂内联结甲（V1

5、）、乙（V6）两个车间的道路网如上图所示，图中每条边上的权数代表道路的长。如果沿道架设联结甲乙之间的电话线（或光缆线），怎样架设节省材料？（最短链问题）甲(V1)乙（V6）下图所示的是单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从V1出发，通过这个交通网到V8去，请找一条总费用最小的旅行路线。（最短路问题）V1V2V3V5V8V4V6V76312621104103446最短路问题的应用行进的总路程最少一序列活动的总成本最少一序列活动的总时间最少例：多阶段的成本优化(设备更新问题)某公司使用一台设备，每年年初，公司就要决定是购买新的设

6、备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费；若继续使用旧设备，则需支付一定的维修费。请制定一个五年之内的设备更新计划，使得五年内购置费和维修费总的支付费用最少。年份1　　2　　3　　4　　5年初价格11　11　12　12　　13使用年数第1年第2年第3年第4年第5年内　　内　　内　　内　　内年维修费5681118设备每年年初的价格表：使用不同时间的设备所需要的维修费：点Vi表示“第i年年初购进新设备”，则点的个数为V1、V2、V3、V4、V5弧eij表示“第i年年初购置的设备一直使用到第j年年初”权表示“购置费+使用中的维修费”组成该图的点和

7、弧如右所示：（从V1到V6的路中找最短的）13+5e56V6V512+512+5+6e45e46V5V6V412+512+5+612+5+6+8e34e35e36V4V5V6V311+511+5+611+5+6+811+5+6+8+11e23e24e25e26V3V4V5V6V211+511+5+611+5+6+811+5+6+8+1111+5+6+8+11+18e12e13e14e15e16V2V3V4V5V6V1权数(费用和)弧终点I始点V1V2V3V4V6V5五年总的支付费用为53，有两个最优方案：（1）V1，V3，V6即：在第1年、第3年各购置一台新

8、设备（2）V1，V4，V6即：在第1年、第4年各购置