电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

第二章通信网拓扑结构知识点梳理汇总VIP免费

第二章通信网拓扑结构知识点梳理汇总_第1页
1/30
第二章通信网拓扑结构知识点梳理汇总_第2页
2/30
第二章通信网拓扑结构知识点梳理汇总_第3页
3/30
第二章通信网拓扑结构通信网的拓扑结构是很基本,也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表,主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。§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和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是无向图2)若G是有向图下面定义图的边序列,链,道路,环和圈:相邻二边有公共端的边的串序排列(有限)(v1,v2),(v2,v3),(v3,v4),(vi,vj),称为边序列。边序列中,无重边的,成为链(link);若边序列中没有重复端,称为道路(path);若链的起点与终点重合,称之为环(ring);若道路的起点与终点重合,称之为圈(cycle)。任何二端间至少存在一条径的图,为连通图。否则,就是非连通图。对非连通图来说,它被分为几个最大连通子图,即几个“部分”。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素,则此图成为非连通图,如下例:G=ABC=A+B+C对于图的连通,可以通过下面的方法给予准确的描述:对于图G中的任意两个端点u和v,如果存在一条从u到v的链,称u和v有关系,容易知道这是一个等价关系;从而可以将图G做一个等价分类,每一个等价分类就是一个连通分支.连通分支只有一个的图为连通图.下面举一些图的例子:(1)完全图Kn:任何二端间有且只有一条边(即直通路由),称为完全图,其边、端数之间存在固定关系:下面是一个n=5的完全图(2)正则图:所有端度数都相同的连通图为正则图d(vi)=常数(i=1,2,n)正则图是连通性最均匀的图(3)尤拉图(Euler):端度数均为偶数的连通图为尤拉图。尤拉图的性质:尤拉图存在一个含所有的边且每边仅含一次的环.(4)两部图两部图的端点集合分为两个部分,所有边的端点分别在这两个集合中.完全两部图Km,n(5)2.1.3树:树是图论中一个很简单,但是又很重要的概念,在图论中运用是十分重要的。图的定义有多种,如下面的定义:1、任何二端有径且只有一条径的图称为树。2、无圈的连通图称为树.我们采用第2种关于图的定义方式,也就是:树:无圈的连通图称为树.树有以下性质:1.树是最小连通图,树中去一边则成为非连通图。2.树中一定无环。任何二端有径的图是连通图,而只有一条径就不能有环。3.树的边数m和端数n满足m=n-1此式可以用数学归纳法证明。4.除单点树,至少有两个度数为1的端(悬挂点)树上的边称为树枝(branch)定理2.1:给定一个图T,若p=|V|,q=|E|,则下面论断等价:(1)T是树;(2)T无圈,且q=p-1;(3)T连通,且q=p-1;证明:1)2),显然;2)3),反证:若T不连通,它有k个连通分支(k大于等于2),每个都...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

第二章通信网拓扑结构知识点梳理汇总

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部