资源描述：
《第六章网络规划与网络计划技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第六章网络规划与网络计划技术网络规划是图论的一个重要内容，也是近几I•年来运筹学领域屮发展迅速、且-
2、•分活跃的一个分支.由于它对实际问题的描述具有肓观性，使网络规划在T程设计和管理中得到广泛应用，已成为对各种系统进行分析、研究、管理的重要T具.网络规划的内容十分丰富,本章主要介绍了在路径问题、网络流问题等领域屮的一些应用方法，如：最小树问题、最人流问题和最小费用流问题.网络计划技术是指计划评审法和关键路径法,它们是五十年代在美国彼此独立发展起来的一种组织牛产和进行计划管理的科学方法.网络计划技术的基本原理是利用网络图來表达工程的进度安排及其组成
3、的各项活动之间的制约关系，计算各项活动的有关时间参数，使管理者対工程的全局能有全面、清晰的了解，从而制定工程进展的口程计划以求得完工期、资源和成本的优化方案.§1图与网络的基本概念一、图什么是图？首先我们通过下面的儿个例子來认识什么是图.例6.1哥尼斯堡七桥问题哥尼斯堡(konigsberg)城域有一个普雷格尔(Pregel)河系，由IH河、新河及其交汇而成的大河组成，它把该城分成了一岛三岸共四块陆地，陆地Z间有七座桥连通，如图6-1Q).这个城里的居民当吋热衷于这样一个问题：从岸上任一地方开始，能否通过每座桥一次且仅仅一次就能回到原地.1736
4、年欧拉发表了图论方面的第一篇论文，将此难题化成了一•个数学问题：用点表示两岸或小岛，用点ZI'可的联线表示陆地Z间的桥，这样就得到了图6-1(b)所示的一个图.从而原问题就变为：在图6-1(b)中，是否能从某一点出发只经过各条边一次且仅仅一次而乂冋到出发点，即一笔画问题•在图6-1(b)屮，虽然没有画出两岸、岛屿的人小形状和桥的长短，但保持了陆地间的关联情况.(a)C图6-1C(v-0例6.2在一群人中，他们分别是赵、钱、孙、李、周、吴、陈七人，对他们Z间相互认识的关系，我们用图6-2来表示.Vl£12V2023V3034V4从上而的例子可以看到
5、图可以很好地描述、刻画反映对象ZI'可的特定关系•一般情况下图中点的相对位置如何、点与点Z间联线的长短
6、11
7、直，对于反映对象Z间的关系并不是很重要，如例6.2也可以用图6-3來表示.可见图论小的图是对现实现实的具体事物及其相互关系的一种抽象表示，它比地图、天文图、电路图、儿何图等更捕象，也更具随意性，因而它是帮助人们认识客观事物的一-种更一•般的工具.所谓图就是点和边的集合.图的定义如下：一个图G为一•个有序二元组(兀E),记为G=(V,E)其小，孑是一个有限非空的集合，其元索称为G的结点或顶点，简称点，而孑成为G的结点集，简称点集,一般表示为
8、V-{vi,V2,…,V”};£是由卩中的无序对(V/,Vj)所构成的一个集合，其元素称为G的边，一-般表示为曰尸(％vy),而应称为G的边集.例6.3用图表示哥尼斯堡七桥问题.哥尼斯堡七桥问题的图G表示如下：G二F)其中:点集V-{vi,V2,V3,V1}边集E二{即，&⑷&2y&13,边(VyV),二(VyEl),012=(Vy叫)，e2=(KbV2)eiB=(ri,Ki),£13二(K1,KJ,e>3=(灼,必)1、端点和关联边对于e沪(匕，V),则称匕，匕是的端点，罚是匕，b的关联边•在图6-4中，n,旳是e】3的端点，d是旳
9、，内的关联边.2、相邻相邻的概念包括了点相邻与边相邻两种•若点％匕都有同一条关联边，则称点匕与匕,相邻；若两边具有同一个端点,则称该两边相邻•在图6-4中，点嗨旳相邻,边比,即,03,04相邻.3、重边、简单图若一条边的两个端点是同一点，则称该边为环.图6-4中氐称为环.若两个端点Z间冇多条边，则称这些边为多重边.图6-4中的知，处为多重边•没冇环和多重边的图称为简单图.如图6-2、6-3.4^次、奇点、偶点、孤立点、悬挂点和悬挂边点卩的关联边的数冃称为点y的次，记为d(y)；若〃(y)为奇数的点称为奇点；若6/(0为偶点的点称为偶点；次为0的点
10、为孤立点；次为1的点为悬挂点；悬挂点的关联边称为悬挂边.在图6-4中，d(内)二A,d(ri)=3；由于存在环色，所以d(r2)=5；点旳为悬挂点，边％为悬挂边.5、链、开链、闭链、简单链、初等链和圈在图G=(V,E)中,设％,比，…，％eV,勺，勺2,…，空wE・若空t=if2,…，k,则交替序列〃={%灼，比勺「…灼,％}称为一条从％至％的链，简记为〃=%,%,・・・，%.在“中，％称为始点，％称为终点；若始点与终点相同，则称“为闭链；若始点与终点是不同的点，则称“为开链；若链“中的边都不相同，则〃为简单链；若链〃中的边都不相同，也没有相同的
11、结点，则链“称为初等链.若在初等链〃中，始点与终点相同，即v-o=v.则初等链“称为圈.在图6-4中，链//j=v1v2v3v4是初等链
