下载此文档

第六章网络规划与网络分析 PPT课件.ppt

文档分类：IT计算机 | 页数：约91页举报非法文档有奖

1/91

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/91 下载此文档

文档列表 文档介绍

第六章网络规划与网络分析
内容
图与网络
树
最短路问题
网络最大流问题
最小费用最大流
案例:网络的中心与选址问题图与网络
自然界和人类社会中许多事物以及事物之间的关系,都可以用点和线连接起来的图形来描述。
例如
用点表示城市,点间联线表示城市间的道路,就可描述城市间的交通,如果联线旁标注城市间的距离——网络图中称为权,形成加权图,就称为网络图,就可进一步研究从一个城市到另一个城市的最短路径;或者标上单位运价,就可分析运费最小的运输方案。
例6-1由点及不带箭头的连线所组成的图形。
点的相对位置如何、点与点之间联线的长短曲
直,对反映对象之间的关系并不重要。
表示5个球队之间的赛事关系。
点a,b,c,d,e,f----5个球队,
两点的连接------两球队之间的赛事关系。
例 6-2 由点及带箭头的连线所组成的图形。
图 6-2 是一张管道运输网示意图--城市间物资运输关系,
v1,v2,v3,v4,v5,v6,v7----7个城市,
箭线旁的数字---物流的最大容量。现在要求出从v1地到v7地的可运送的最大流方案。
边---两点间不带箭头的连线
弧---带箭头的连线。
一、无向图
由点和边组成的图称为无向图,图 6-3即为无向图
(1)无向图
定义6-1 无向图是一个无序二元组(V,E),记为
G=(V,E),其中是p个点的集合,简称定点集;
E=(e1, e2,…,eq)是条边的集合,简称边集合,并且是一个无序二元组,记为。
顶点数:点集V中元素的个数称为图G的顶点数,记为
。如图 6-3,
为
的端点,
为
的关联边。
若点
vi,vj
有边相连,即
,则称vi,vj相邻, vi,vj与e关联。
v3,v5相邻, v3,v5与e7关联。
图6-3
。如图 6-3,
端点:对于边
,称vi,vj为e的端点。
e为vi,vj的关联边。
边数:边集 E中元素的个数,记为
(2)简单图
不含环和多重边的图称为简单图,含有多重边的图称为多重图。
(3) 点的次(度)
以点v为端点的边数叫做点v的次,记作d(v)。
如图6-3中, d(v1)=4,d(v2)=4。
若
,则称
称为图G的次序列。
环(自回路):一条边的两个端点如果相同,称此边为环。如
图6-3中的e1。
多重边:两个点之间多于一条边的,如图6-3中的e4, e5.
次为 1 的点-----悬挂点,连接悬挂点的边------悬挂边。
次为0的点----孤立点。
次为奇数的点-----奇点,次为偶数的点------偶点。
定理 6-1 任何图G =(V,E)中,所有点的次数之和等于边数的2倍。即
证:由于每条边必有两个顶点关联,在计算点的次时,每条边均被计算了两次,所以顶点次数之和等于边数的2倍。
定理 6-2 任何图G =(V,E)中,奇点的个数必为偶数。
证:设图中奇点与偶点的集合分别为V1和V2,
由定理 6-1 知
由于2q(G)为偶数,而是若干个偶数之和,也
为偶数。所以必为偶数,即奇点的个数必
为偶数。

第六章网络规划与网络分析 PPT课件来自淘豆网www.taodocs.com转载请标明出处.

第六章网络规划与网络分析 PPT课件.ppt

【精品】PPT课件第8章线性规划与网络流

【精品】PPT课件第4章网络需求分析

【精品】PPT课件第11章网络系统集成案例分析

精品-优秀PPT课件--精品-优秀PPT课件--6第六章距离衰减理论

精品PPT课件----第六章网络通信安全

精品PPT课件----第六章、房价管理及经营统计分析PPT（庄军）

网络操作系统PPT教学课件-第五章_Windows网络

移动通信课件553——第六章移动通信网络规划及优化_精品

计算机网络技术PPT教学课件-第9章网络安全与网络管理技术

运筹学课件------6-第六章图与网络分析

第六章 网络规划与网络分析 PPT课件.ppt

第六章网络规划与网络分析 PPT课件.ppt