网络分析法.ppt

第九章网络分析法
1. 了解图论的基本概念,会求最小树和最短路。
2. 熟练绘制简单的网络图,掌握工序时间参数的确定方法及各种时间参数的计算。
3. 掌握网络图的优化与调整,会缩短总工期,实现时间——费用——资源的优化配置。
图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学控制论,信息论,工程技术,交通运输,经济管理,电子计算机等各项领域。对于科学研究,市场和社会生活中的许多问题,可以同图论的理论和方法来加以解决。例如,各种通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局等问题,都可以应用图论的方法,简便、快捷地加以解决。
随着科学技术的进步,特别是电子计算机技术的发展,图论的理论获得了更进一步的发展,应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的最优问题。因此,图论越来越受到工程技术人员和经营管理人员的重视。
1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,如下图所示。
B
A
C
D
当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。
尽管试验者很多,
但是都没有成功。
村庄1
引例: 阿富汗战后建设, 30个村庄要通电话, 已知两两距离,如何用最少的电话线连通30个村庄?
村庄4
村庄3
村庄6
村庄2
村庄5
6
3
11
5
9
8
10
7
7
12
网络结构
DNS、内网WWW服务器
外网WWW服务器
楼层交换机
防火墙
网管工作站
OA骨干交换机
楼层交换机
用户工作站
CISCO 路由器
骨干交换机
PSTN
移动办公
DCN
其它部门
OA、EMAIL主机
网络拓扑结构
树型
混合型
为了寻找答案,1736年欧拉把陆地缩为一点,把桥作为连接点的边,将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题。
B
A
C
D