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

第6页共36页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第6页共36页第二章通信网拓扑结构通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。§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⃗RE则V和E组成图G，称V为端集，E为边集。下面给出图的一些概念:当eij=(vi，vj)，称边eij和端vi与vj关联；当viRvj不等价于vjRvi时，为有向图；当viRvj等价于vjRvi(eij=eji)时，为无向图；当V=φ(此时E必为空集)，为空图；自环，孤立点图，重边；简单图:不含自环和重边的图称为简单图.当V，E均有限元∣V∣，∣E∣≠∞时，称为有限图。我们一般讨论的都是有限图，考虑到实数集的不可数性，任何有限图都可以表示为三维空间的几何图形，使每两条边互不相交，而且边均可用直线来实现。但是若要在平面实现则不一定能办到，稍后我们会给出平面图的概念。第7页共36页第6页共36页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第7页共36页子图:若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)；若链的起点与终点重合，称之为环(ring)；若道路的起点与终点重合,称之为圈(cycle)。任何二端间至少存在一条径的图，为连通图。否则，就是非连通图。对非连通图来说，它被分为几个最大连通子图，即几个“部分”。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素，则此图成为非连通图，如下例:第8页共36页第7页共36页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第8页共36页G=ABC=A+B+C对于图的连通,可以通过下面的方法给予准确的描述:对于图G中的任意两个端点u和v,如果存在一条从u到v的链,称u和v有关系,容易知道这是一个等价关系;从而可以将图G做一个等价分类,每一个等价分类就是一个连通分支.连通分支只有一个的图为连通图.下面举一些图的例子:(1)完全图Kn：任何二端间有且只有一条边（即直通路由），称为完全图，其边、端数之间存在固定关系:m=(n2)=n(n−1)2下面是一个n=5的完全图(2)正则图：所有端度数都相同的连通图为正则图d(vi)=常数（i=1，2，n）正则图是连通性最均匀的图(3)尤拉图(Euler):端度数均为偶数的连通图为尤拉图。尤拉图的性质:尤拉图存在一个含所有的边且每边仅含一次的环.(4)两部图两部图的端点集合分为两个部分,所有边的端点分别在这两个集合中.完全两部图Km,n第9页共36页第8页共36页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第9页共36页(5)第10页共36页第9页共36页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第10页共36页2.1.3树:树是图论中一个很简单，但是又很重要的概念，在图论中运用是十分重要的。图的定义有多种,如下面的定义：1、任何二端有径且只有一条径...