网络规划与网络计划技术.ppt

《网络规划与网络计划技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络规划与网络计划技术我们都生活在一个网络社会中，从某种意义上说现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物资分派网络等各种网络所组成的复杂的网络系统。网络规划就是研究如何有效地计划，管理和控制这个网络系统，使之发挥最大的社会和经济效益。由于图的结构的直观性，运用图论的方法更有助于我们分析问题，描述问题，解决问题。网络规划是运筹学的一个经典和重要分支，所研究的问题涉及经济管理，工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。一、图什么是图？哥尼斯堡七桥问题例：在一群人中，他们分别是赵、

2、钱、孙、李、周、吴、陈七人，对他们之间相互认识的关系，我们用图来表示如下：可见图论中的图是对现实现实的具体事物及其相互关系的一种抽象表示，它比地图、天文图、电路图、几何图等更抽象，也更具随意性，因而它是帮助人们认识客观事物的一种更一般的工具。所谓图就是点和边的集合。图的定义如下：一个图G为一个有序二元组（V，E），记为G=（V，E）其中，V是一个有限非空的集合，其元素称为G的结点或顶点，简称点，而V成为G的结点集，简称点集，一般表示为V={v1,v2,…,vn}；E是由V中的无序对（vi,vj）所构成的一个集合，其元素称为G的边

3、，一般表示为eij=（vi,vj），而E称为G的边集。例用图表示哥尼斯堡七桥问题。哥尼斯堡七桥问题的图G表示如下：G=（V，E）其中：点集V={v1,v2,v3,v4}边集E={e14,e14,e42,e42,e13,e43,e23}边e14=(v1,v4)，e14=(v1,v4)，e42=(v4,v2)，e42=(v4,v2)e13=(v1,v3)，e43=(v4,v3)，e23=(v2,v3)为了便于叙述，以下图为例，介绍有关术语与概念。1、端点和关联边对于eij=(vi,vj)，则称vi,vj是eij的端点，eij是vi,

4、vj的关联边。在图中，v1,v3是e13的端点，e23是v2,v3的关联边。2、相邻相邻的概念包括了点相邻与边相邻两种。若点vi,vj都有同一条关联边，则称点vi与vj相邻；若两边具有同一个端点，则称该两边相邻。在图6-4中，点v2,v3相邻，边e13,e13,e23,e34相邻。v1e13v2v3v4v5e12e13e23e34e24e45e223、重边、简单图若一条边的两个端点是同一点，则称该边为环。图中e22称为环。若两个端点之间有多条边，则称这些边为多重边。图中的e13,e13为多重边。没有环和多重边的图称为简单图。4、

5、次、奇点、偶点、孤立点、悬挂点和悬挂边点v的关联边的数目称为点v的次，记为d(v)；若d(v)为奇数的点称为奇点；若d(v)为偶点的点称为偶点；次为0的点为孤立点；次为1的点为悬挂点；悬挂点的关联边称为悬挂边。在图中，d(v3)=4，d(v1)=3；由于存在环e22，所以d(v2)=5；点v5为悬挂点，边e45为悬挂边。v1e13v2v3v4v5e12e13e23e34e24e45e22v1e13v2v3v4v5e12e13e23e34e24e45e226、连通图在一个图中，若任意两点之间至少存在一条链，则该图就称为连通图，否则

6、称为不连通图。v1e13v2v3v4v5e12e13e23e34e24e45e227、子图、真子图、支撑子图二、有向图、无向图1、有向图、无向图2、基础图、路、回路三、网络在实际工作中，有很多问题的可行解方案都可通过一个赋权有向图表示，例如：物流渠道的设计、物资运输路线的安排、排水管道的铺设等。所以，赋权图被广泛应用于解决工程技术及科学管理等领域的最优化问题。通常，我们把赋权图称为网络，赋权有向图称为有向网络，赋权无向图称为无向网络。网络分析内容主要涉及网络优化问题，即最小树问题、最短路问题、最大流问题、最小费用最大流问题、网络

7、计划问题等等。§最小树问题一、树树是图论中的一个重要概念。所谓树就是一个无圈的连通图。如图6-10中的(a)就是一棵树，而(b)因为有圈（v3,v4,v5,v3），所以(b)就不是树，(c)也不是树，因为(c)不是连通图。树是一个很有价值的概念和方法，在计算机科学，有机化学，电网络分析，最短连接及渠道设计等领域都有广泛的应用。例如分枝定界法过程的表示、决策树等。例如，以决策树为例：12个硬币中有一枚是假的，但偏轻还是偏重不知道，如何用天平用最少的次数找到假币？关于树的一些性质：(1)在树中，任意两顶点间有且仅有一条道路(2)在树

8、中，顶点数比边数多１。(3)在树中，任意两个不相邻顶点加上一条边则恰好得到一个圈。(4)在树中，去掉任一条边，则树为不连通的。最小支撑树最小支撑树的一个应用例子：假设要建造一个连接若干城镇的通讯网络，已知城镇vi,vj直接拉线的造价为Cij，试设计一个总造价最小