通信网 05 网络拓扑结构分析

通信网理论基础通信网理论基础第五章网络拓扑结构分析本章目的网络拓扑结构分析是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次拓扑结构是通信网规划和设计的第层次问题。通信的拓扑结构图论的模型来代通信网的拓扑结构可以用图论的模型来代表，本章分析的主要问题为最小支撑树、最短路径和网络流量安排等问题。25.1图论基础511图的定义和基本概念5.1.1图的定义和基本概念例5.1欧拉(Euler)7桥问题。ADCBB3电网络（基尔霍夫）4图的定义定义5.1所谓一个图G，是指给了一个端点集合V，以及边的集合或V中元素的序对集合E，图一般用来表示。),(GEV集合，图般用来表示如果图G有n端m条边，可将V和E表示为)(}{V}{E为，。某边的端为，称这边和端关联，},...,,{21nvvvV},...,,{21meeeEjivv，jivv，这个边也可记为:或。)(jivv，ije5图的示例1v1ee6e1234{,,,}{}VvvvvEeeeeeev4v1e2e3e6123456{,,,,,}Eeeeeee其中，2v44e5e112213324423(,)(,)(,)(,)evvevvevvevv，，3v1v324423534614(,)(,)(,)(,)()evvevvGVE，可将右图记为1e3e6e1126(,),,GVEveee可将右图记为。与关联2v4v2e4e5e11261234,,vvvv与是相邻节点与是相邻边63v412346,,,eeeee与是相邻边图的相关概念1节点：表示物理实体，用表示。边节点间的连线表示两节点间存在连接关系iv边：节点间的连线，表示两节点间存在连接关系，用表示。空图：称为空图。ijeV空图：称为空图。孤立点图：称为孤立点图，也叫平凡图。1v5vVE也叫平凡图。无向图：设图，当对存在某种关系R等价于G(,)VEivjvjv2v4v对存在某种关系R等价于对存在某种关系R，称G为无向图。即图G的任意一条边都对jvjviv3v向图。即图G的任意条边都对应一个无序节点对,()ijvv，()()ijjivvvv3无向图示例7(,)(,)ijjivvvv图的相关概念2有向图：设图，当对存在某种关系R不等价于对存在某种关系R称G为无向G(,)VEivjv系R不等价于对存在某种关系R，称G为无向图。即图G的任意一条边都对应一个有序节点对jviv()()()对,。有权图：设图，如果对每一条边或()ijvv，(,)(,)ijjivvvvG(,)VEke它的每一个节点赋以一个实数，则称图G为有权图或加权图，称为权值。ivkpkp251v5v1v5v2.53.14.22.7有向图示例2v4v有权图示例2v4v1.85.383v3v图的相关概念3自环：若与一个边相关联的两个节点是同一个节点则称边为自环ke节点，则称边为自环。重边：在无向图中与同一对节点关联的两条或两ke条以上的边称为重边。在有向图中与同一对节点关联且方向相同的两条或两条以上的边称为重边。1v5v1ee4e1v5v1ee4e2v1vv2e5e6ee1v2vv2e5e6ee自环与重边23v4v3e7e8e3v4v3e7e8e9自环与重边33图的相关概念4简单图：不含有自环及重边的图。伪图：非简单图称为伪图。节点的度：与某节点相关联的边数定义为该节点节点的度：与某节点相关联的边数定义为该节点的度数，记为。有向图中，用表示离开或从射出的边数，即节点()idv()idviviv有向图中，用表示离开或从射出的边数，即节点的出度；用表示进入或射入节点的边数即节点的入度。节点的度数表示为()ii()idviviiviv()()()iiidvdvdv1v5v1e2e4e5e6e1v5v1e2e4e5e6e12()4()4dvdv11()4()2dvdv4v23e5e6e7ee2v4v3e567e8e23()()2dv2v1_1()()2dv103v3e8e3v38e性质5.1对图，，G(,)VE||Vn||Em（1）如果G是无向图，1()2niidvmnn（2）如果G是有向图，11()()nniiiidvdvm1证明（）每个边有两个端点按照端来计数就是等式1证明：（）每个边有两个端点，按照端来计数就是等式左边，这种计数对每条边均重复且恰恰重复一次；）对于有向图每条边有两个端它们和边的关系不同2()()dvdv（）对于有向图，每条边有两个端，它们和边的关系不同，出度按段计数每边各一次，类似，所以有()()vVvVvVvVdvdvm。11vVvV图的相关概念5子图：给定图，若，称图G(,)VE11V,VEE111G(,)VE是G中由生成的子图，记为。特别若子图的端点集合为V,这个图被称为图G的支撑子图（生成子图）。1V1[]GV若，称图是G中由生成的子图记为1E,E11V{|}vVvE是中某边的端点111G(,)VEE[]GE是G中由生成的子图，记为。1E1[]GE1v5v1v5v1v5v2v4v2v2v4v3v3v3v12abc图的相关概念6链（Chain）：有限条边的一种串序排列称为边序列或链。没有重复边的链称为简单链没有重复边的链称为简单链。没有重复端的链称为初等链或道路；起点和终点不在同一个节点的链叫开链。起点和终点重合的链叫圈（闭链）。起点和终点重合的道路叫初等圈。链中边的数目称为链的长度。链中边的数目称为链的长度。一般重点讨论道路和初等圈。13v1e4e122646233vevevevev链：1v5v2e4e5e6e122645583vevevevevvevevev简单链：道路2v4v7e1227455122745541vevevevvevevevev道路：初等圈：3v3e78e314图的连通性任何二端间至少存在一条链的图，为连通图。否则，就是非连通图。非连通图G有三个连通分支非连通图G有三个连通分支GG15图的例子1v5v1v5v2v4v2v4v242v4完全图两部图3v3vKK完全图两部图(1)22nnnmnK,mnKmn边数为2216图的例子1v4v1v5v3v+2v4v1v2v3v3vv5v2v4v1vvv1v2v3v42v4v欧拉图正则图23v175.1.2树定义5.2无圈的连通图称为树。性质5.2除单点树，至少有两个度数为1的端(悬挂点)。性质5.3任意树的边数m和端数n满足11nm18若且T含有G的所有端，称T是G的主树或支撑树；TG根树星树线树主树上的边称为树枝；非树枝的边称为连枝；主树是树枝集；连枝的边集称为连枝集或树补。树上任两端间添加一条连枝，则形成圈，称为基本圈。连接图G的主树T的树枝数称为图G的阶。若G有n个端，则它的阶为(G)1则它的阶ρ为ρ(G)=n-1。连接图G的连枝集的连枝数称为图G的空度，记为μ。设G有m条边，则μ(G)=m-n+1。19有m条边，则μ(G)mn+1。树的等价性质定理5.1给定一个图T，若，，则下面论断等价||Vn||Em面论断等价：（1）T是树；（2）T无圈，且；（3）T连通，且。1mn1mn531证明：由性质，可推导（）（2），（1）（3）。5.31211Tmn由性质，可推导（）（2），（1）（3）。证明（）（）。若有圈且可在圈中删去任意一条边图仍然连1Tmn若有圈且。可在圈中删去任意条边，图仍然连通。依次删除直至图变成连通无圈图或树，与假设矛盾；203112Tkk证明（）（）。若不连通且它有个连通的分支（）每个12(1)kiiTmnkkipmpn若不连通且。它有个连通的分支（），每个连通的分支为树。若第个树有个点，则1()2iiippkn，与假设矛盾。树是最小连通图；21树是最大无圈图。树的性质性质5.4：若T是树，则：5.4.1:T是连通图，去掉任何一条边，图便分成两个且仅仅两个连通分支；542T是无圈图但添加任何条边图便会包含个5.4.2:T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。1)TT证明是树连通且去掉个边(后111,)TTmneuveT证明：是树连通且；去掉一个边(后，若图变成三个连通分支，则补上后，图有两个连通分支，2(,)TeuvTT不连通，与已知条件矛盾。若图继续为连通图。则存在。对于图，两条12ee不同的边，，构成一个圈，与已知条件矛盾。22树的性质5.4.2(,)uvG再看，设是中任意(,)()uvP再看设中任两个不相邻的顶点，有唯一一条道路，如果添上一条以(,),)uvPuvePeG条道路，如果添上条以(为端点的边，则形成了中唯的个圈Ge了中唯一的一个圈。23树的性质性质5.5：设T是树，则任何两点之间恰好有一条道路反之如图T中任何两点之间恰好有条道道路；反之，如图T中任何两点之间恰好有一条道路，则T为树。证明：先证必要性。因为树是连通的，所以树中任意两个顶点之间必有道路。12121212(,)(,),()GuvPPPPPexyePPPe如果在中存在两条不同的道路和，因为，所以存在中的一条边。显然是连通1212(,),()(,)yxyPPeGG以存在中的条然是的，所以它含有一条的道路。如此，则是中的一个圈这与是树的假设矛盾GGGCC个圈。这与是树的假设矛盾。再证充分性。是连通的，如果中有一个圈，那么上的任意两顶点之间均有两条不同的道路这与假设矛盾24意两顶点之间均有两条不同的道路，这与假设矛盾。5.1.3割集割集指的是某些端集或边子集。对连通图，去掉此类子集图变为不连通去掉此类子集，图变为不连通。分为割边集、割端集和混合割集。割端与割端集设是图G的个端去掉和其关联边后G设v是图G的一个端，去掉v和其关联边后，G的部分数增加，则称v是图G的割端。去掉一个端集合后G的部分数增加这个端去掉一个端集合后，G的部分数增加，这个端的集合称为割端集去掉任意一个端，图的部分数不变，则称这种去掉任意个端，图的部分数不变，则称这种图为不可分图。25点连通度对于连通图,在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集的端数目称为图的点连通度最小割端集的端数目，称为图的点连通度或连通度，连通度用表示。262v5vace2v5vae6v4vbcdf1v4v5abcdef1v3v6vf3v6vbf割端与割端集割端与割端集4232434144{}{,}{,}{,}{,}vvvvvvvvvv割端集有：，，，，等。是割端456{}vvv是最小割端集。若图中没有和，则图是不可分图。2756vv若图中没有和，则图是不可分图。割边与割边集设e是图G的一条边，去掉e后，G的部分数增加，则称e是图G的割边。去掉一个边集合后，则割去掉个集后G的部分数增加，这个边的集合称为割边集。若某割边集S的任何真子集都不是割边集，则若某割边集S的任何真子集都不是割边集，则称S为割集。28线连通度割边集中边数最少的割边集，称为最小割边集。最小割边集的边数目，称为线连通度，线连通度用表示连通度用表示。291vc1v1v14v5vabdef14v5vde14v5vae2v3vdfg2v3vdfg2v3vf1vc{,,},{,,,},{,},{,}abccbdggfce割边集有等14v5vabde{,,},{,},{,}{,},{,}abcgfcegfce割集有等最小割边集有。2v3vdf最小割边集的边数，称为图的结合度，表征图的连通程度，与网络可靠性有关。30征图程度与靠性有关连通度的简单性质性质5.6对于任意一个连通图，若为最小度则),(GEV||||m2若，，为最小度，则nV||mE||nm22证明：首先，所以。考虑