第二章 通信网的拓扑结构.doc

《第二章 通信网的拓扑结构.doc》由会员分享，可在线阅读，更多相关《第二章 通信网的拓扑结构.doc（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 通信网拓扑结构第二章 通信网拓扑结构 通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。2.1图论基础图论是应用数学的一个分支，本节介绍它的一些概念和结论。其基本内容可参见（1）和（2）。2.1.1图的定义 例2.1 哥尼斯堡7桥问题;所谓一个图，是指给了一个集合V，以及V中元素的序对集合E，V和E中的元素分别称为图的端点和边。下面用集合论的术语给出图的定义：设有集合V和E，V=v1，v2，vn， E=e1，e2， e

2、m ，且则V和E组成图G，称V为端集，E为边集。下面给出图的一些概念: 当eij=(vi，vj)，称边eij和端vi与vj关联； 当viRvj不等价于vjRvi 时，为有向图； 当viRvj等价于vjRvi(eij=eji)时，为无向图；当V=(此时E必为空集) ，为空图；自环，孤立点图，重边；简单图: 不含自环和重边的图称为简单图. 当V，E均有限元 V，E时，称为有限图。我们一般讨论的都是有限图，考虑到实数集的不可数性，任何有限图都可以表示为三维空间的几何图形，使每两条边互不相交，而且边均可用直线来实现。但是若要在平面实现则不一定能办到，稍后我们会给出平面图的概念。 子图:若A的端集与边集

3、分别为G的端集与边集的子集，则A为G的子图。若AG，且AG，则A为G的真子图。特别地，当A的端集和G的端集相等，称A为G的支撑子图。由端点子集诱导生成的子图. 图的运算:G1G2, G1G2, Gc等 图的几种表现形式: 集合论定义, 几何实现, 矩阵表示. 图的同构; 权图.2.1.2图的连通性 对无向图的端vi来说，与该端关联的边数定义为该端的度数：，记为：d(vi)。对有向图：d+(vi)表示离开vi的边数，d-(vi)表示进入vi的边数对图G=(V，E)，若|V|=n，|E|=m，则有如下基本性质： 1）若G是无向图 2）若G是有向图 下面定义图的边序列，链，道路，环和圈： 相邻二边有

4、公共端的边的串序排列（有限） (v1，v2)， (v2，v3)， (v3，v4)， (vi，vj)，称为边序列。边序列中，无重边的，成为链(link)；若边序列中没有重复端，称为道路(path)；若链的起点与终点重合，称之为环(ring)； 若道路的起点与终点重合,称之为圈(cycle)。 任何二端间至少存在一条径的图，为连通图。否则，就是非连通图。对非连通图来说，它被分为几个最大连通子图，即几个“部分”。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素，则此图成为非连通图，如下例: G=ABC=A+B+C对于图的连通, 可以通过下面的方法给予准确的描述: 对于图G中的任意两个

5、端点u和v, 如果存在一条从u到v的链, 称u和v有关系, 容易知道这是一个等价关系; 从而可以将图G做一个等价分类, 每一个等价分类就是一个连通分支.连通分支只有一个的图为连通图.下面举一些图的例子:(1)完全图Kn：任何二端间有且只有一条边（即直通路由），称为完全图， 其边、端数之间存在固定关系: 下面是一个n=5的完全图 (2)正则图：所有端度数都相同的连通图为正则图 d(vi)=常数（i=1，2，n） 正则图是连通性最均匀的图 (3)尤拉图(Euler): 端度数均为偶数的连通图为尤拉图。 尤拉图的性质: 尤拉图存在一个含所有的边且每边仅含一次的环.(4) 两部图 两部图的端点集合分为

6、两个部分, 所有边的端点分别在这两个集合中. 完全两部图Km,n(5)2.1.3树:树是图论中一个很简单，但是又很重要的概念，在图论中运用是十分重要的。图的定义有多种, 如下面的定义：1、 任何二端有径且只有一条径的图称为树。2、 无圈的连通图称为树.我们采用第2种关于图的定义方式, 也就是:树: 无圈的连通图称为树.树有以下性质: 1.树是最小连通图，树中去一边则成为非连通图。 2.树中一定无环。任何二端有径的图是连通图，而只有一条径就不能有环。 3.树的边数m和端数n满足m=n-1 此式可以用数学归纳法证明。 4.除单点树，至少有两个度数为1的端(悬挂点) 树上的边称为树枝 (branch

7、)定理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个树有个点，则，与q = p-1相矛盾；3）1），p=1时，显然。设，T连通，且q=p-1，首先易证T有悬挂点，不然，与q = p-1相矛盾；然后对点数进行归纳即可；定理2.2：若T是树，则：（1）T是连通图，去掉任何一条边，图便分成两个且仅仅两个分图；（2）T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。同时，若无向图满足（1）和（2），则T是

8、树。定理2.3：设T是树，则任何两点之间恰好有一条道路；反之，如图T中任何两点之间恰好有一条道路，则T为树。 定理2.2和2.3刻画了树的两个重要特征，事实上定理2.3也为图提供了另一个等价定义。上述两个定理的证明请读者自行完成。支撑树(Spanning Tree)： 考虑树T是连通图G的子图，TG，且T包含G的所有端，称T是G的支撑树。 由定义可知，只有连通图才有支撑树；反之有支撑树的图必为连通图。一般支撑树不止一个， 连通图至少有一个支撑树。支撑树上任二端间添加一条树支以外的边，则形成环(circuit)。支撑树外任一边称支撑树的连枝，连枝的边集称为连枝集或树补(Cotree)。不同支撑树

9、对应不同连枝集。 对非连通图来说，它可以分成K个最大连通子图，即K个“部分”，每部分各有支撑树。K个支撑树的集合形成图G的主林，其余的边为林补。主林的边数称为图的阶，用r表示。主林的连枝数称为空度，用m表示。有如下关系式： n=n1+n2+nk r=( n1-1)+ ( n2-1)+ + ( nk-1)=n-k m=m-n+k 例如： k=3； r=11-3=8； m=12-11+3=42.1.4割(cut) 割指的是某些子集(端集或边集)。对连通图，去掉此类子集，变为不连通。对非连通图，去掉此类子集，其部分数增加。 割分为割端集与割边集。1、割端与端集 设V是图G的一个端，去掉V和其关联边后

10、，G的部分数增加，则称V是图G的割端。去掉几个端后，G的部分数增加，这些端的集合称为割端集。有的连通图无割端，这种图称为不可分图。 对于连通图, 在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集，其任意真子集不为割集。 最小割端集的端数目，称为图的联结度。联结度越大，图的连通性愈不易被破坏。2、割边集与割集 连通图G的边子集S，去掉S使G为不连通，称S为割边集 在众多的割集中边数最少的割集，称为最小割边集。最小割边集的任一真子集不为割边集。最小割集的边数，称为结合度. 结合度同样表示图的连通程度，结合度越高，连通程度越好。3、基本割集与基本环（针对连通图讨论）1） 基本

11、割集设T为连通图G的一个支撑树，取支撑树的一边（枝）与某些连枝，定可构成一个极小边割集，此割集称为基本割集。即：基本割集是含支撑树T之一个树枝的割集。基本割集有n-1个.下面一个图来理解基本割集. 支撑树T= 连枝：， 则基本割集：（，）， (，)，(，)， (，)2）基本环T为连通图G的一个支撑树，G-T的边集为连枝集。取一连枝可与某些树枝构成环。这种包含唯一连枝的环称基本环。每个基本环只包含一个连枝-与连枝一一对应，其数目=连枝数，共m-n+1个。环和运算: 对于集合, 这个运算的意义为对称差运算.通过环和运算, 由基本割集和基本环可以生成新的环和割集或它们的并集,事实上可以生成所有的环和

12、割集. 例2.2 通过基本环和基本割集理解基尔霍夫定律. 下面的图理解基本环. 连枝集 ， ：， ：， ：， ：，2.1.5 图的平面性图G若可以在一个平面上实现，除端点以外，任何两条边均无其他交点，则称G是平面图。当平面图有一个平面实现后，它把全平面分成s个区域（含包含无穷远点的开区域）。注意一个图为平面图等效于能够在球面上有一个几何实现.设连通平面图有m边，n端，则s=m-n+2，此为著名的Euler公式。这个性质可以用数学归纳法证明或树的性质证明。 m=4，n=4，s=2定理2.4：简单连通图为平面图的必要条件是:m=3)上述结论可以推广到有重边和自环的情形. 证：形成区域至少3边，区域

13、周线上的边数至少3s(不考虑区域共边)，实际每边均在二区域周线上，最多有2m边（周线上）。考虑区域共边，有2m3s，代入Euler公式得m3n-6.此为平面图的必要，非充分条件。例2.3 讨论完全图K5和完全两部图K3,3的平面性.定理2.5连通两部图为平面图的必要条件是:m+4 =3)根据每个平面图G=（V，E），可以生成一个对偶图G。G的每个平面对应于G的每个顶点，G中相邻的两个面在G中有一些边与G中的两个面的每一条边界的边相交，如下图所示。但是简单平面图的对偶图可能不再是简单图。 定理2.6 图G为平面图当且仅当G不含K5和K3,3或它们的细分图为子图.2.1.6图的矩阵表示 很多时候，

14、需要将图表示在计算机中，这就有了图的矩阵表示。下面主要介绍关联阵和邻接阵。1 关联阵设图G有n个端，m条边，则全关联阵 ；端vi对应于矩阵的第 I行(共n行)；边ej对应于第j 列(共m列);其中: 下面是一个例子说明关联矩阵, 例2.4 由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， 再去掉任一行

15、，得到关联阵A，为n-1m阶。A中的每一个非奇异方阵对应一个支撑树。图G的支撑树数目可由以下方法得到：定理2.7(矩阵-树定理)用AT表示A的转置, 无向图G的主树数目t(G) = det(AAT)，注意上面的定理计算的主树数目为标号树的数目; 同时n-1阶矩阵det(AAT)可以直接写出, 主对角线的元素为相应端点的度数, 其余位置为-1或0, 而这取决于相应的端点之间是否有边.例2.5 t(Kn) = , t(Kn,m) = mn-1nm-1.t(Kn) = 的计算如下： 继续例2.4: 共有8种支撑树如下 2.邻接阵邻接阵是表征图的端与端关系的矩阵，其行和列都与端相对应。令G=（V，E）

16、是m端，n边的有向图，其邻接阵 其中， 如： 对于无向图 ，因此是邻接阵为对称阵。我们可以通过对C的一些计算，得到图G的性质。如：计算C的幂次可得到关于转接径长的一些信息。若Cij(2)=1则存在k，使Cik Ckj =1，即Cik= Ckj=1，i，j之间至少有径，径长为2；若Cij(2)=a，则vivj间有a条径长为2的径，若Cij(2)=0，则vivj间无径长为2的径；所以， Cij(2)即为vivj间径长为2即转接一次的径数。同理，若Cij(3)=1， 则有vivkvsvj，径长为3，即经过二次转接。由此可得下面结论:邻接阵幂之元素表示了二端间转接次数不超过b-1的径，但是经过转接的端

17、可能重复。已知图G的邻接阵C, 需要解决图G是否连通的问题? 当然通过计算邻接阵C和C的幂可以解决这个问题,考虑下面的小算法, 它解决同样的问题, 但效率很高.Warshall 1962(1)置新矩阵 P:= C;(2)置 i = 1; (3)对所有的j, 如果P(j,i)=1, 则对k=1,2,n P(j,k):= P(j,k) P(i,k);(4) i = i+1;(5)如n i转向步骤(3), 否则停止.本节介绍了图论的简要知识，1和2介绍了很好的基础知识。4介绍了网络优化算法的详尽的和较新的进展。本节内容同时也借鉴3的一些结果。某些图论知识在以后应用是会在介绍。2.2 最短径问题 上节

18、中介绍的图只考虑了图顶点之间的关联性，本节将要对图的边和端赋予权值，讨论有权图。权值在各种各样实际问题中有不同的实际意义，如费用，几何距离，容量等等。本节将介绍一些算法，大部分算法可借助计算机实现。2.2.1 最短支撑树给定连通图G=(V，E)，W(e)是定义在E上的非负函数，称W(e)为e的权。T=(V，)为G的一个支撑树。定义树T的权为。最短支撑树问题就是求支撑树，使W()最小。下面介绍求最短支撑树的方法。1) 无限制条件的情况 Prim在1957年提出一个方法，简称P算法。 图G有n端，端间“距离”dij(i，j=1，2，3，.n)已给定(若无边则dij=)，找一个支撑树，使其n-1个边

19、（树枝）的权和最小，步骤如下： P0:任取一端v1，子图G1=v1，在G1到G-G1中取最小的dij 得子图G2= v1， v2P1:求G3 得子图G3= v1，v2，v3 Pr-2:从Gr-1求Gr 得子图Gr= v1，v2，vr Pr-1:重复Pr-2，直至得到Gn为止例2.5: G1=v1G2=v1，v3G3=v1，v3，v6G4=v1，v3，v6，v7G5=v1，v3，v6，v7，v2G6=v1，v3，v6，v7，v2，v5G7=v1，v3，v6，v7，v2，v5，v4则W(T)=15 可以看出， Prim算法第K步运算，是以Gk作为整体寻找至G-Gk的最短边，每次并入Gk的边总是保持

20、余下m-k+1个中最短的，因此算法终止时，所得的支撑树为最短者(可用数学归纳法证明)。 从算法始至终止，共进行n-1步，每步从k个端与n-k个端比较，须经k(n-k)-1次，可得总计算量 约为n3量级。当n很大时，可借助计算机实现。另一个算法由Kruskal在1956年提出:设G(k)是G的无圈支撑子图,开始G(0)=(V,f)。若G(k)是连通的,则它是最小支撑树；若G(k)不连通,取e(k)为这样的一边,它的两个端点分属G(k)的两个不同连通分图,并且权最小。令G(k+1)= G(k)+ e(k),重复上述过程。上面算法的实现过程需要排序算法；Rosenstiehl和管梅谷提出了另一个算法

21、：设G(k)是G的连通支撑子图，开始G(0)=G，若G(k)中不含圈，则它是最小支撑树；若G(k)中包含圈，设m是G(k)中的一个圈，取m上的一条权最大的边e(k)，令G(k+1)= G(k)-e(k)，重复上述过程。上面算法的实现过程需要解决如小问题：对于一个无向图G, 如何寻找其中的圈?可以通过搜索图中度为1的顶点而逐步简化.上面算法的实施过程,都是一种贪心法原理的应用; 从局部最优的结果中寻找全局最优的结果.问题如果复杂, 这种方法一般只能找到准最优解.2) 有限制情况 在许多情况下，不但要求最短支撑树，还要求一些额外条件。有两种解决此类问题的方法穷举法和调整法。穷举法就是先把图中的支撑

22、树穷举出来，按条件逐个筛选，最后选出最短支撑树。这种方法较直观，但很烦琐。下面讨论调整法。以Esau-William算法为例(解决一种特定的问题):问题:图G有n个站,其中已知v1是主机，已知各边间距离dij，以及各个端站的业务量Fi（i，j=1，2，n），要求任端至v1的径边数K(即限转接次数 d(i)+Cij then begind(j):= d(i)+ Cijpred(j):=i；if jList, then 将j并入List;end; end; end; 上面的算法中没有指明List的结构, 如果将List组织为一个队列, 算法效率会更高, 计算复杂度为O(nm), 大约为目前最快的算

23、法, 上面两个算法的解决思路的比较是很有意义的。值得注意的是，如果附加一些条件，那么问题便很复杂了。如果边有两个权,相应的算法就复杂的多, 并且很可能无多项式算法.2、所有端间最短径算法 Floyd算法解决了图G中任意端间的最短距离和路由，并且也采用Label-correcting 的方法。给定图G及其边 (i, j)的权dij(i，j=1，2，3，n);F0：初始化距离矩阵W(0)和路由矩阵R(0) ; W(0)= Wij(0) nn其元素： 同时 R(0)= rij(0) nn F1：已求得W(k-1) 和R(k-1)，求W(k) 和R(k) ; wij(k)=minwij(k-1)，wi

24、k(k-1)+ wkj(k-1) F2：若kn，重复；k=n终止。上面的路由方法为前向路由，容易更改算法使它的路由为回溯路由; 算法要执行n次迭代, 第k次迭代的目的为经过端k转接是否可以使各端之间距离缩短. 从本质上讲, Floyd算法的迭代过程就是保证满足下面的定理成立.定理2.8 对于图G, 如果w(i, j)表示端i和j之间的可实现的距离, 那么w(i, j)表示端i和j之间的最短距离当且仅当对于任意i, k, j有: w(i, j) w(i, k) +w(k, j)Floyd算法计算量 : wij(k)=minwij(k-1)，wik(k-1)+ wkj(k-1)中，每定一k值，求w

25、ij经1次加，1次比较，求一次迭代为n2次加，n2次比较，共n个迭代，所以其运算量为n3级; 显然比重复使用Dijkstra算法效率高，同时存储效率也要高。对于Floyd算法, 同样提出若干问题如下: 1 如果端点有权如何处理? 2 如果边的权可正可负, 算法是否仍然有效? 3 算法是否对有向图也适用？例2.7 给定一个无向图G, 求任意两端之间最少转接次数和路由.例2.8图有六个端，端点之间的有向距离矩阵如下：1. 用D算法求V1到所有其他端的最短径长及其路径。2. 用F算法求最短径矩阵和路由矩阵，并找到V2至V4和V1至V5的最短径长及路由。3. 求图的中心和中点。解：1. D算法V1V2

26、V3V4V5V6指定最短径长,路由0V1W10, 19 1 3V3W131, 193 2 V5W152, 38 3 7V4W143, 18 7 V3W167, 5 8 V2W128, 52. F算法最短路径矩阵及最短路由阵为W5，R5有向距离为4有向距离为23. 中心为V3或V5中点为V2 在实际问题中，除了求最短径外，如当主路由（最短径）上业务量溢出或故障时，需寻求次短径或可用径。次短径指备用径，可用径指一批满足某种限制条件的径（如限径长，限转接次数.）。但这些问题一般没有多项式算法, 可以根据实际情况采用某种贪心策略获得近似解.3、网的中心与中点如网络用图G=(V, E)表示, 根据Flo

27、yd算法的计算结果可以定义网络的中心和中点.中心:对每个端点i, 先求 此值最小的端称为网的中心，即满足下式的端i*： =网的中心宜做维修中心和服务中心。中点:将“平均最短径长”最小的端，定义为中点，先计算 si = , 然后求出si的最小值, 相应的端点为中点. 网的中点可用做全网的交换中心。2.3网络流量问题 网络的目的是把一定的业务流从源端送到宿端。流量分配的优劣将直接关系到网络的使用效率和相应的经济效益。网络的流量分配受限于网络的拓扑结构，边和端的容量以及路由规划。本节及下节中关于流量的内容均在有向图上考虑，并且均是单商品流问题，即网络中需要输出的只有一种商品或业务。通信网络的服务对象

28、有随机性的特点, 关于通信业务随机性特点将在下一章中考虑, 本节中假设网络源和宿的流量为常量.2.3.1基本概念 给定一个有向图G=（V，E），C(e)是定义在E上一个非负函数，称为容量；对边eij，边容量为Cij ，表示每条边能通过的最大流量。设f= fij 是上述网络的一个流，若能满足下述二限制条件，称为可行流。 a)非负有界性：0fijCij； b)连续性: 对端vi有： v(f) = F为源宿间流fij的总流量.式中 （vi）=vj: ( vi， vj)E 流出vi的边的末端集合; (vi)=vj: ( vj， vi)E 流入vi的边的始端集合; 有n个连续性条件，共有2m+n个限制条

29、件，满足上述二限制条件的流称为可行流。 需要解决的问题分为两类: 1 最大流问题 在确定流的源和宿的情况下, 求一个可行流f, 使v(f) = F为最大; 2 最小费用流问题 如果边(i,j)的单位流费用为di,j , 流f的费用为: 所谓最小费用流问题: 在确定流的源和宿的情况下, 求一个可行流f, 使为最小. 下面介绍割量和可增流路的概念. 设X是V的真子集，且vsX，vtXc，（X，Xc）表示起点和终点分别在X和Xc的边集合，这个集合当然为一个割集,割集的正方向为从vs到vt。割量定义为这个割集中边容量的和: 对可行流fij: f(X，Xc)表示前向边的流量（和）fij, 其中viX，v

30、jXc f(Xc，X)表示反向边的流量 (和) fji, 其中viX，vjXc则源为vs宿为vt的任意流f有:(1) v(f)=f(X,Xc)-f(Xc,X), 其中vsX，vtXc证明： 对任viX : 对所有viX,求和上式： 源端 s: fs1+fs2+fs3 中转端 1: f14 -(fs1+f21)中转端 2: f21+f23 -(fs2)中转端 3: f3t -(fs3+f23+f53)-= f14+f3t-f53= f(X,Xc)-f(Xc,X)=F(2) FC(X,Xc)由（1）及f(X, Xc)非负，可得：下面讨论可增流路的概念。 从端s到端t的一个路，有一个自然的正方向，然

31、后将路上的边分为两类：前向边集合和反向边集合。对于某条流，若在某条路中，前向边均不饱和（fijcij），反向边均有非0流量（fij0），称这条路为可增流路径（或增广链）。在可增流路上增流不影响连续性条件，也不改变其它边上的流量，同时可以使从源端到宿端的流量增大。 若流 fi,j 已达最大流，f则从源至宿端的每条路都不可能是可增流路，即每条路至少含一个饱和的前向边或流量为0的反向边。2.3.2 最大流问题 所谓最大流问题，在确定流的源端和宿端的情况下, 求一个可行流f, 使v(f) 为最大。对于一个网络，求最大流的方法采用可增流路的方法，下面的定理2.9为这种方法提供了保证. 如果网络为图G =

32、 (V, E),源端为vs, 宿端为vt.定理2.9 (最大流-最小割定理)可行流f* = 为最大流当且仅当G中不存在从vs 到vt的可增流路.证明: 必要性: 设f*为最大流,如果G中存在关于f*的从vs 到vt的可增流路.令 0 fi,j ， 则标vj 为: (+，i，j)其中j =min(ci,j-fi,j ，i ) i 为vi 已标值。若（vj ,vi ）E，且 fj,i 0， 则标vj 为: (-，i，j)， 其中j =min（i ，fj,i ）其它端vj 不标。所有能加标的邻端vj 已标，则称vi已查。倘若所有端已查且宿端未标，则算法终止。M3：若宿端vi 已标，则沿该可增流路增流。M4: 返回M1。 上面的算法是针对有向图且端无限制的情况。若是有无向边，端容量及多源多宿的情况，可以进行一些变换，化为上述标准情形。 若端i和端j之间为无向边，容量为Ci,j，那么将它们化为一对单向边(i，j)和(j，i)，并且它们的容量均为Ci,j。 如果端i有转接容量限制Ci，那么将Vi 化为一对顶点，原终结于Vi的边全部终结于，原起始于Vi的边均起始于，且从至有一条边容量为Ci。 对多源多宿的情况，设原有源为，原有宿为，要求从源集到宿集的最大流量，可以虚拟一个新的源和新的宿，源到的各边容量均为无限大，到宿的各边容量也为无限大，这样多源多宿的问题就化为从到的最大流问题。见下图：仔细