第二章 通信网的拓扑结构VIP免费

第二章 通信网拓扑结构 通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。§2.1 图论基础图论是应用数学的一个分支，本节介绍它的一些概念和结论。其基本内容可参见（1）和（2）。2.1.1 图的定义 例 2.1 哥尼斯堡 7 桥问题;所谓一个图，是指给了一个集合 V，以及 V 中元素的序对集合 E，V 和E 中的元素分别称为图的端点和边。下面用集合论的术语给出图的定义：设有集合 V 和 E，V={v1，v2，……，vn}， E={e1，e2，…… em} ，且V ×V ⃗R E 则 V 和 E 组成图 G，称 V 为端集，E 为边集。下面给出图的一些概念: 当 eij=(vi，vj)，称边 eij和端 vi与 vj关联； 当 viRvj不等价于 vjRvi 时，为有向图； 当 viRvj等价于 vjRvi(eij=eji)时，为无向图；当 V=φ(此时 E 必为空集) ，为空图；自环，孤立点图，重边；简单图: 不含自环和重边的图称为简单图. 当 V，E 均有限元 ∣V∣，∣E∣≠∞时，称为有限图。我们一般讨论的都是有限图，考虑到实数集的不可数性，任何有限图都可以表示为三维空间的几何图形，使每两条边互不相交，而且边均可用直线来实现。但是若要在平面实现则不一定能办到，稍后我们会给出平面图的概念。 子图:若 A 的端集与边集分别为 G 的端集与边集的子集，则 A 为 G 的子图。若AG，且 AG，则 A 为 G 的真子图。特别地，当 A 的端集和 G 的端集相等，称 A 为G 的支撑子图。由端点子集诱导生成的子图. 图的运算:G1G2, G1G2, Gc等 图的几种表现形式: 集合论定义, 几何实现, 矩阵表示. 图的同构; 权图.2.1.2 图的连通性 对无向图的端 vi 来说，与该端关联的边数定义为该端的度数：，记为：d(vi)。对有向图：d+(vi)表示离开 vi的边数，d-(vi)表示进入 vi的边数对图 G=(V，E)，若|V|=n，|E|=m，则有如下基本性质： 1）若 G 是无向图 ∑i=1nd(vi)=2m(=2|E|) 2）若 G 是有向图 ∑i=1nd+( vi)=∑i=1nd−( vi)=m 下面定义图的边序列，链，道路，环和圈： 相邻二边有公共端的边的串序排列（有限） (v1，v2)， (v2，v3)， (v3，v4)， (vi，vj)，称为边序列。边序列中，无重边的，成为链(link)；若边序列中没有重复端，称为道路(path)...