网络拓扑结构分析概要

信息工程学院信息论教研室BUPTInformationTheory&TechnologyEducation&ResearchCenter通信网基础第五章网络拓扑结构分析通信网实验室Cnl.sie.bupt.cnBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn2概述•网络拓扑结构分析是很基本，也是很重要的问题。•拓扑结构是通信网规划和设计的第一层次问题。•通信网的拓扑结构可以用图论的模型来代表，本章分析的主要问题为最小支撑树、最短路径和网络流量安排等问题。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn35.1图论基础5.1.1图的定义和基本概念•图论是应用数学的一个分支，有着丰富的内容，本节介绍它的一些概念和结论。•例5.1欧拉(Euler)7桥问题。有一些河穿过哥尼斯堡城，将该城分为4个部分，有7座桥将城中各个部分相连，当地有一个游戏，问能否从城的某一个部分出发遍历每一座桥同时不重复经历任何一座桥。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn4BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn55.1.1图的定义和基本概念•解：Euler分析了这个问题，并且用图5.1来代表这个问题，4个端点表示4个城区，而边表示7座桥。如果定义端点的度为和它关联的边的个数，那么在图5.1中，各端点的度为3，3，3，5。•如果存在一个遍历每座桥的漫游，除去起点和终点，对每个中间端点总是一进一出，所以那些中间端点的度应该为偶数，由于图5.1中度为奇数的端大于2个，这样图5.1不可能存在一个遍历所有桥的漫游。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn6图的定义•定义5.1所谓一个图G，是指给了一个端点集合V，以及边的集合或V中元素的序对集合E，图一般用来表示。•如果图G有n端m条边，可将V和E表示为，。•某边的端为，称这边和端关联，这个边也可记为:或。),(GEV},...,,{21nvvvV},...,,{21meeeEjivv，)(jivv，jie,jivv，),(GEVBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn7一些基本概念•有限图∣V∣，∣E∣∞•无向图•有向图•空图•孤立点图•自环•重边•一个不含自环和重边的图称为简单图，以后如果没有特别声明主要讨论简单图。)(jivv，)(ijvv，VE)(iivv，BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn8图的定义•对无向图的端，与该端关联边的数目为该端的度数，记为：。•对有向图的端，表示离开的边数，表示进入的边数。•性质5.1•对无向图•对有向图iviv)(div),(GEVnV||mE||niimvd12)(　　　mvdvdniinii11)()()(diviviv)(divBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn9子图•给定图，若称图是G中由生成的子图，记为。若，称为G的子图。特别，若子图的端点集合为V，这个图被称为图G的支撑子图。•若，称图是G中由生成的子图，记为。),(GEV},|),{(,V111VvuEvuEV),(G111EV1V][1VG21EE),(G212EV1EE}|{V11中某边的端点是EvVv),(G111EV1E][1EGBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn10图的连通性•考虑边的一个序列，相邻两边有公共端，如(v1，v2)，(v2，v3)，(v3，v4)，(vi，vi+1)，这个边序列称为链，链简单说就是一个连续轨迹。•没有重复边的链称为简单链；没有重复端的链称为初等链或道路；•若链的起点与终点重合，称之为圈；若道路的起点与终点重合,称之为初等圈。一般重点讨论道路和初等圈。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn11连通图•任何两端间至少存在一条链的图，为连通图。否则，就是非连通图。•非连通图G有三个连通分支GBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn12图的例子•完全图•两部图•欧拉图•正则图nKBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn135.1.2树•定义5.2无圈的连通图称为树。•性质5.2除单点树，至少有两个度数为1的端(悬挂点)。•性质5.3任意树的边数m和端数n满足1nmBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn14•定理5.1给定一个图T，若，，则下面论断等价：•（1）T是树；•（2）T无圈，且；•（3）T连通，且。nV||mE||1nm1nm5.1.2树BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn15•性质5.4若T是树，则：•（1）T是连通图，去掉任何一条边，图便分成两个且仅仅两个连通分支；•（2）T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。•性质5.5设T是树，则任何两点之间恰好有一条道路；反之，如图T中任何两点之间恰好有一条道路，则T为树。5.1.2树BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn16•如果树T是连通图G的子图，TG，且T包含G的所有端，称T是G的支撑树或主树。•连通图一定有支撑树。•树边，连枝。5.1.2树BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn175.1.3割集•割集指的是某些端集或边子集。对连通图，去掉此类子集，图变为不连通。•定义5.3割端与割端集•设v是图G的一个端，去掉v和其关联边后，G的部分数增加，则称v是图G的割端。去掉一个端集合后，G的部分数增加，这个端的集合称为割端集。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn18点连通度•对于连通图,在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。•最小割端集的端数目，称为图的点连通度或连通度，连通度用表示。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn19线连通度•定义5.4割边与割边集•设e是图G的一条边，去掉e后，G的部分数增加，则称e是图G的割边。去掉一个边集合后，G的部分数增加，这个边的集合称为割边集。•割边集中边数最少的割边集，称为最小割边集。最小割边集的边数目，称为线连通度，线连通度用表示。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn20性质5.5•性质5.5对于任意一个连通图，若，，为最小度，则),(GEVnV||mE||nm2BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn21基本割集和基本圈•对于任何一个连通图G，设T为G的一个支撑树，每一条连枝决定的圈是基本圈。•确定了连通图的一个支撑树后，每条树边可以决定一个基本割集。•对于支撑树，去掉树上任何一条边，树便分为两个连通分支，从而将原图的端分为两个集合，这两个集合之间的所有边形成一个极小边割集，这个边割集称为基本割集。BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn22•基本圈和基本割集e1e6e2e3e4e5图5.3基本圈和基本割集基本割集和基本圈BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn23•基本圈和基本割集有许多应用，首先通过集合的对称差运算,由基本割集可以生成新的割集或它们的并集,事实上可以证明生成所有的割集；基本圈也有类似的性质。•例5.2通过基本圈和基本割集分析求解电网络。基本割集和基本圈BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn24•分析：在每个等电势的区域抽象一个端点，一个电网络为一个连通图。如果这个图有n个端点，m条边，则有n-1个独立电势变量。任取一个支撑树，有n-1个基本割集。在每个基本割集上，根据基尔霍夫定律，流过基本割集电流的代数和为零。这n-1个方程由于每个方程含有唯一的树枝项，所以这n-1个方程线性无关，通过这些方程可以求解所有的电势变量。基本割集和基本圈BUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn25反圈•下面给出一个重要的概念：反圈。•定义5.5反圈：给定图，若，记；特别，当时，将记为或。设是的非空真子集，若，称为由确定的反圈。(,)GVE(,)GVE(,)GVE(,)GVE,STV[,]{(,):,}GSTuvEuSvT\TVS[,]GST()GS()SXXV()GX()GXXBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt.cn265.1.4图的矩阵表示•下面将给出图的矩阵表示，主要介绍关联阵和邻接阵。•1关联阵设图G有n个端，m条边，则全关联阵，其中，不关联与若关联与若在无向图中ijijijijveavea,0,1不关联与指向关联与离开关联与在有向图中ijijiijijiijijveavveavvea,0,,1,,10,[]ijnmAaBUPTInformationTheory&TechnologyEducation&ResearchCenter2020年2月cnl.sie.bupt