通信网理论基础第二章 通信网拓扑结构分析1.ppt
第二章 通信网拓扑结构分析n 通信网的拓扑结构分析是很基本的问题，是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短路径和网络流量问题等。2.1 图论基础 2.1.1图的定义 例2.1 Euler7桥问题；Kirchhoff应用树去研究电网络分析问题；Cayley将树应用到化学领域等。n所谓一个图，是指给了一个集合V，以及V中元素的序对集合E，V和E中的元素分别称为图的端点和边。记为n 如果端点集合为V=v1，v2，vn,边集合为E=e1，e2，em，n当eij=(vi，vj)，称边eij和端vi与vj关联；n无向图：对任意vi，vj，如果(vi，vj)E，就有(vj，vi)E;n有向图：对任意vi，vj，如果(vi，vj)E，不一定有(vj，vi)E;n当V=，为空图；n当E=，为孤立点图；n自环，伪图，重边；n简单图简单图:不含自环和重边的图称为简单图。n有限图：当集合V，E均有限时，称为有限图。我们一般讨论的都是有限图。考虑到实数集的不可数性，任何有限图都任何有限图都可以表示为三维空间的几何图形，使每可以表示为三维空间的几何图形，使每两条边互不相交，而且边均可用直线来两条边互不相交，而且边均可用直线来实现实现。n子图子图:若A的端集与边集分别为G的端集与边集的子集，则A为G的子图。若AG，且AG，则A为G的真子图。特别地，当A的端集和G的端集相等，称A为G的支撑子图。由端点子集诱导生成的子图,由边子集诱导生成的子图。n图的运算:nG1G2,G1G2,Gc等。n图的几种表现形式:集合论定义,几何实现,矩阵表示。n图的同构;权图。2.1.2图的连通性 n对无向图的端vi来说，与该端关联的边数定义为该端的度数：记为：d(vi)。n对有向图：d+(vi)表示离开vi的边数，d-(vi)表示进入vi的边数。n对图G=(V，E)，若|V|=n，|E|=m，则有:：n 1）若G是无向图 n n2）若G是有向图 n下面定义图的边序列，链，道路，环和圈：n 相邻二边有公共端的边的串序排列（有限）(v1，v2)，(v2，v3)，(v3，v4)，(vi，vj)，称为边序列。边序列中，无重边的，成为链(link)；若边序列中没有重复端，称为道路(path)；若链的起点与终点重合，称之为环(ring)；若道路的起点与终点重合,称之为圈(cycle)。n任何二端间至少存在一条路径的图，为连通图。否则，就是非连通图。对非连通图来说，它被分为几个最大连通子图。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素，则此图成为非连通图，如下例:n对于图的连通,可以通过下面的方法给予准确的描述:n 对于图G中的任意两个端点u和v,如果存在一条从u到v的链,称u和v有关系,容易知道这是一个等价关系;从而可以将图G做一个等价分类,每一个等价分类就是一个连通分支。连通分支只有一个的图为连通图。n 如果没有特别申明，一般考虑简单连通图。n下面举一些图的例子:n(1)完全图Kn：任何二端间有且只有一条边，称为完全图，其边、端数之间存在关系:n n 下面是一个n=5的完全图n(2)正则图：所有端度数都相同的连通图为正则图n d(vi)=常数（i=1，2，n）n 正则图是连通性最均匀的图n(3)欧拉图(Euler):端度数均为偶数的连通图为欧拉图。n欧拉图的性质:欧拉图存在一个含所有的边且每边仅含一次的环。n(4)两部图n 两部图的端点集合分为两个部分,所有边的端点分别在这两个集合中。n 完全两部图Km,nn(5)哈密尔顿图n 如果图有一个圈能够经过所有的顶点。2.1.3树:树是图论中一个很简单，但又很重要的概念。n图的定义有多种,如下面的定义：n1 任何二端有径且只有一条径的图称为树。n2 无圈的连通图称为树.n我们采用第2种关于图的定义方式,也就是:n树树:无圈的连通图称为树无圈的连通图称为树.n树有以下性质:n 1.树是最小连通图，树中去一边则成为非连通图。n 2.树中一定无环。任何二端有径的图是连通图，而只有一条径就不能有环。n 3.树的边数m和端数n满足：m=n-1n 4.除单点树，至少有两个度数为1的端(悬挂点)。n定理2.1：给定一个图T，若p=|V|，q=|E|，则下面论断等价：n（1）T是树；n（2）T无圈，且q=p-1；n（3）T连通，且q=p-1；n证明：n1）2），显然；n2）3），反证：若T不连通，它有k个连通分支（k大于等于2），每个都为树，若第i个树有 个点，则有下面的矛盾n n3）1），反证：若T有圈，从圈中去掉任意一条边仍然保持连通，去掉若干条边后得到一个支撑树，但这与q=p-1相矛盾。n定理2.2：若T是树，则：n（1）T是连通图，去掉任何一条边，图便分成两个且仅仅两个连通分支；n（2）T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。n同时，若无向图满足（1）和（2），则T是树。n定理2.3：设T是树，则任何两点之间恰好有一条道路；反之，如图T中任何两点之间恰好有一条道路，则T为树。n支撑树(Spanning Tree)：n 考虑树T是连通图G的子图，TG，且T包含G的所有端，称T是G的支撑树。n 只有连通图才有支撑树；反之有支撑树的图必为连通图。一般支撑树不止一个，连通图至少有一个支撑树。支撑树上任二端间添加一条树边以外的边，则形成环。支撑树外任一边称支撑树的连枝，连枝的边集称为连枝集。不同支撑树对应不同连枝集。2.1.4 割n割指的是某些子集(端集或边集)。对连通图，去掉此类子集，图变为不连通。n 割分为割端集、割边集和混合割集。n1 割端与割端集n 设V1是图G的一个端子集，去掉V1和其关联边后，G-V1不连通，则称V1是图G的割端集。特别若V1 为独点集，其中的端为割端。n 对于连通图,在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。n 最小割端集的端数目，称为图的联结度。n n2 割边与割边集n 连通图G的边子集E1，去掉E1使G为不连通，称E1为割边集。特别若E1为独点集，其中的边为割边。n 在众多的割集中边数最少的割边集，称为最小割边集。最小割集的边数，称为结合度。n特别，完全图Kn的联结度为n-1;n完全图K1的结合度为0。n3、基本割集与基本环 n1）基本割集n设T为连通图G的一个支撑树，取支撑树的一条树枝与某些连枝，定可构成一个极小边割集，此割集称为基本割集。基本割集有n-1个。n2）基本环nT为连通图G的一个支撑树，G-T的边集为连枝集。取一连枝可与某些树枝构成环，这种包含唯一连枝的环称基本环。n每个基本环只包含一个连枝，其数目与连枝一一对应，共m-n+1个。n下面一个图来理解基本割集。n支撑树：连枝：n则基本割集：n下面的图理解基本环。n支撑树 连枝集 n基本环为：n例2.2 通过基本环和基本割集理解基尔霍夫定律。n环和运算:对于集合,这个运算的意义为对称差运算。n通过环和运算,由基本割集和基本环可以生成新的环和边割集或它们的并集,事实上可以生成所有的环和边割集。n 2.1.5 图的平面性 n 图G若可以在一个平面上实现，除端点以外，任何两条边均无其他交点，则称G是平面图。当平面图有一个平面实现后，它把全平面分成f个区域（含包含无穷远点的开区域）。n设连通平面图有m边,n端，f个区域，则：nEuler:f=m-n+2 n定理2.4：简单连通图为平面图的必要条件是:n例2.3 讨论完全图K5和完全两部图K3,3的平面性。n定理2.5：连通两部图为平面图的必要条件是:n定理2.6：图G为平面图当且仅当G不含K5和K3,3或它们的细分图为子图。2.1.6图的矩阵表示 n 很多时候，需要使用图的矩阵表示。下面主要介绍关联阵和邻接阵。n1 关联阵 n 从全关联阵去掉任何一行就可以得到关联阵。n 如果将关联阵的每列中任何一个1改为-1，将这个矩阵记为A。对于连通图，这个矩阵的秩为n-1。每个满秩子阵对应图G的一个支撑树。n下面是一个例子说明关联矩阵,n例2.4n定理2.7(矩阵-树定理)n用AT表示A的转置,无向图G的主树数目n (G)=det(AAT)n注意上面的定理计算的主树数目为标号树的数目；同时n-1阶矩阵det(AAT)可以直接写出,主对角线的元素为相应端点的度数,其余位置为-1或0,而这取决于相应的端点之间是否有边。n例2.5(Kn)=nn-2,(Kn,m)=mn-1nm-1n继续例2.4:共有8种支撑树如下n n2.邻接阵n邻接阵是表征图的端与端关系的矩阵，其行和列都与端相对应。n n对于无向图，邻接阵为对称矩阵。n已知图G的邻接阵C,需要解决图G是否连通的问题?当然通过计算邻接阵C和C的幂可以解决这个问题,考虑下面的小算法,它解决同样的问题,但效率很高。n Warshall 1962n(1)置新矩阵 P:=C;n(2)置 i=1;n(3)对所有的j,如果P(j,i)=1,则对k=1,2,nn P(j,k):=P(j,k)P(i,k);n(4)i=i+1;n(5)如n i转向步骤(3),否则停止.
