第二章 通信网的拓扑结构

第2章通信网拓扑结构6第二章通信网拓扑结构通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。§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}，且EVVR则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的支撑子图。由端点子集诱导生成的子图.第2章通信网拓扑结构7图的运算: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是无向图niiEmvd1)2(2)(2）若G是有向图　　　mvdvdniinii11)()(下面定义图的边序列，链，道路，环和圈：相邻二边有公共端的边的串序排列（有限）(v1，v2)，(v2，v3)，(v3，v4)，(vi，vj)，称为边序列。边序列中，无重边的，成为链(link)；若边序列中没有重复端，称为道路(path)；若链的起点与终点重合，称之为环(ring)；若道路的起点与终点重合,称之为圈(cycle)。任何二端间至少存在一条径的图，为连通图。否则，就是非连通图。对非连通图来说，它被分为几个最大连通子图，即几个“部分”。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素，则此图成为非连通图，如下例:ACBGG=ABC=A+B+C对于图的连通,可以通过下面的方法给予准确的描述:对于图G中的任意两个端点u和v,如果存在一条从u到v的链,称u和v有关系,容易知道这是一个等价关系;从而可以将图G做一个等价分类,每一个等价分类就是一个连通分支.连通分支只有一个的图为连通图.第2章通信网拓扑结构8下面举一些图的例子:(1)完全图Kn：任何二端间有且只有一条边（即直通路由），称为完全图，其边、端数之间存在固定关系:2)1(2nnnm下面是一个n=5的完全图(2)正则图：所有端度数都相同的连通图为正则图d(vi)=常数（i=1，2，n）正则图是连通性最均匀的图d(v)=2非正则d(v)=3(3)尤拉图(Euler):端度数均为偶数的连通图为尤拉图。Euler图尤拉图的性质:尤拉图存在一个含所有的边且每边仅含一次的环.(4)两部图两部图的端点集合分为两个部分,所有边的端点分别在这两个集合中.完全两部图Km,n(5)第2章通信网拓扑结构92.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），每个都为树，若第i个树有ip个点，则2)1(1pkppqkii，与q=p-1相矛盾；3）1），p=1时，显然。设2p，T连通，且q=p-1，首先易证T有悬挂点，不然，pdqpipii1122121，与q=p-1相矛盾；然后对点数进行归纳即可；定理2.2：若T是树，则：（1）T是连通图，去掉任何一条边，图便分成两个且仅仅两个分图；（2）T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。同时，若无向图满足（1）和（2），则T是树。定理2.3：设T是树，则任何两点之间恰好有一条道路；反之，如图T中任何两点第2章通信网拓扑结构10之间恰好有一条道路，则T为树。定理2.2和2.3刻画了树的两个重要特征，事实上定理2.3也为图提供了另一个等价定义。上述两个定理的证明请读者自行完成。支撑树(SpanningTree)：考虑树T是连通图G的子图，TG，且T包含G的所有端，称T是G的支撑树。由定义可知，只有连通图才有支撑树；反之有支撑树的图必为连通图。一般支撑树不止一个，连通图至少有一个支撑树。支撑树上任二端间添加一条树支以外的边，则形成环(circuit)。支撑树外任一边称支撑树的连枝，连枝的边集称为连枝集或树补(Cotree)。不同支撑树对应不同连枝集。对非连通图来说，它可以分成K个最大连通子图，即K个“部分”，每部分各有支撑树。K个支撑树的集合形成图G的主林，其余的边为林补。主林的边数称为图的阶，用表示。主林的连枝数称为空度，用表示。有如下关系式：n=n1+n2++nk=(n1-1)+(n2-1)++(nk-1)=n-k=m-n+k例如：Gn=11m=12k=3；=11-3=8；=12-11+3=4第2章通信网拓扑结构112.1.4割(cut)割指的是某些子集(端集或边集)。对连通图，去掉此类子集，变为不连通。对非连通图，去掉此类子集，其部分数增加。割分为割端集与割边集。1、割端与端集设V是图G的一个端，去掉V和其关联边后，G的部分数增加，则称V是图G的割端。去掉几个端后，G的部分数增加，这些端的集合称为割端集。有的连通图无割端，这种图称为不可分图。对于连通图,在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集，其任意真子集不为割集。最小割端集的端数目，称为图的联结度。联结度越大，图的连通性愈不易被破坏。2、割边集与割集连通图G的边子集S，去掉S使G为不连通，称S为割边集在众多的割集中边数最少的割集，称为最小割边集。最小割边集的任一真子集不为割边集。最小割集的边数，称为结合度.结合度同样表示图的连通程度，结合度越高，连通程度越好。3、基本割集与基本环（针对连通图讨论）1）基本割集设T为连通图G的一个支撑树，取支撑树的一边（枝）与某些连枝，定可构成一个极小边割集，此割集称为基本割集。即：基本割集是含支撑树T之一个树枝的割集。基本割集有n-1个.下面一个图来理解基本割集.e1e6e2e3e4e5支撑树T={1e6e3e4e}连枝：2e，5e则基本割集：（1e，5e），(6e，2e，5e)，(3e，2e)，(4e，5e)2）基本环T为连通图G的一个支撑树，G-T的边集为连枝集。取一连枝可与某些树枝构成环。这种包含唯一连枝的环称基本环。第2章通信网拓扑结构12每个基本环只包含一个连枝---与连枝一一对应，其数目=连枝数，共m-n+1个。环和运算:对于集合,这个运算的意义为对称差运算.通过环和运算,由基本割集和基本环可以生成新的环和割集或它们的并集,事实上可以生成所有的环和割集.例2.2通过基本环和基本割集理解基尔霍夫定律.下面的图理解基本环.e1e8e9e7e6e5e4e3e2连枝集6(e，7e，8e，)9e6e：1c6{e，1e，3e，}2e7e：2c7{e，3e，}4e8e：3c8{e，3e，}2e9e：4c9{e，4e，}5e第2章通信网拓扑结构132.1.5图的平面性图G若可以在一个平面上实现，除端点以外，任何两条边均无其他交点，则称G是平面图。当平面图有一个平面实现后，它把全平面分成s个区域（含包含无穷远点的开区域）。注意一个图为平面图等效于能够在球面上有一个几何实现.设连通平面图有m边，n端，则s=m-n+2，此为著名的Euler公式。这个性质可以用数学归纳法证明或树的性质证明。m=4，n=4，s=2定理2.4：简单连通图为平面图的必要条件是:m=3n-6(n=3)上述结论可以推广到有重边和自环的情形.有重边有自环证：形成区域至少3边，区域周线上的边数至少3s(不考虑区域共边)，实际每边均在二区域周线上，最多有2m边（周线上）。考虑区域共边，有2m3s，代入Euler公式得m3n-6.此为平面图的必要，非充分条件。例2.3讨论完全图K5和完全两部图K3,3的平面性.定理2.5连通两部图为平面图的必要条件是:m+4=2n(n=3)根据每个平面图G=（V，E），可以生成一个对偶图G'。G的每个平面对应于G'的每个顶点，G中相邻的两个面在G'中有一些边与G中的两个面的每一条边界的边相交，如下图所示。但是简单平面图的对偶图可能不再是简单图。第2章通信网拓扑结构14定理2.6图G为平面图当且仅当G不含K5和K3,3或它们的细分图为子图.第2章通信网拓扑结构152.1.6图的矩阵表示很多时候，需要将图表示在计算机中，这就有了图的矩阵表示。下面主要介绍关联阵和邻接阵。1．关联阵设图G有n个端，m条边，则全关联阵mnijaA][0；端vi对应于矩阵的第I行(共n行)；边ej对应于第j列(共m列);其中:不关联与若关联与若在无向图中ijijijijveavea,0,1不关联与指向关联与离开关联与在有向图中ijijiijijiijijveavveavvea,0,,1,,1下面是一个例子说明关联矩阵,例2.40110010110000111100143210vvvvAe5v1e1v2v4v3e2e4e3由A0可以看出:(1)第i行非零元个数等于端vi度数,每列有两个1;(2)若第i行均为0元素，则vi为孤立端，G为非连通图;(3)若i行只有一个非O元，则vi为悬挂端;(4)如果将A0中每一个列中的任一个1改为-1,则n行之和0向量，所以最多只有n-1行线性无关，A0秩最大为n-1。将无向图全关联阵A0中每一个列中的任一个1改为-1，再去掉任一行，得到关联阵A，为n-1m阶。A中的每一个非奇异方阵对应一个支撑树。图G的支撑树数目可由以下方法得到：第2章通信网拓扑结构16定理2.7(矩阵-树定理)用AT表示A的转置,无向图G的主树数目(G)=det(AAT)，注意上面的定理计算的主树数目为标号树的数目;同时n-1阶矩阵det(AAT)可以直接写出,主对角线的元素为相应端点的度数,其余位置为-1或0,而这取决于相应的端点之间是否有边.例2.5(Kn)=2nn,(Kn,m)=mn-1nm-1.(Kn)=2nn的计算如下：)1()1(1...11......11......111...11