《通信网基础第五部分网络拓扑结构分析ppt课件》由会员分享，可在线阅读，更多相关《通信网基础第五部分网络拓扑结构分析ppt课件（96页珍藏版）》请在金锄头文库上搜索。
1、信息工程学院信息论教研室信息工程学院信息论教研室BUPT Information Theory & Technology Education & Research Center 通讯网根底第五章网络拓扑构造分析通讯网实验室Cnl.sie.buptBUPT Information Theory & Technology Education & Research Center 概述网络拓扑构造分析是很根本，也是很重要的问题。拓扑构造是通讯网规划和设计的第一层次问题。通讯网的拓扑构造可以用图论的模型来代表，本章分析的主要问题为最小支撑树、最短途径和网络流量安排等问题。BUPT Information
2、 Theory & Technology Education & Research Center 5.1图论根底5.1.1图的定义和根本概念图论是运用数学的一个分支，有着丰富的内容，本节引见它的一些概念和结论。例5.1欧拉(Euler)7桥问题。有一些河穿过哥尼斯堡城，将该城分为4个部分，有7座桥将城中各个部分相连，当地有一个游戏，问能否从城的某一个部分出发遍历每一座桥同时不反复阅历任何一座桥。BUPT Information Theory & Technology Education & Research Center BUPT Information Theory & Technology
3、 Education & Research Center 5.1.1图的定义和根本概念解：Euler分析了这个问题，并且用图5.1来代表这个问题，4个端点表示4个城区，而边表示7座桥。假设定义端点的度为和它关联的边的个数，那么在图5.1中，各端点的度为3，3，3，5。假设存在一个遍历每座桥的遨游，除去起点和终点，对每个中间端点总是一进一出，所以那些中间端点的度应该为偶数，由于图5.1中度为奇数的端大于2个，这样图5.1不能够存在一个遍历一切桥的遨游。BUPT Information Theory & Technology Education & Research Center 图的定义定义5.
4、1所谓一个图G，是指给了一个端点集合V，以及边的集合或V中元素的序对集合E，图普通用来表示。假设图G有n端m条边，可将V和E表示为，。某边的端为，称这边和端关联，这个边也可记为:或。BUPT Information Theory & Technology Education & Research Center 一些根本概念有限图V，E无向图有向图空图孤立点图自环重边一个不含自环和重边的图称为简单图，以后假设没有特别声明主要讨论简单图。BUPT Information Theory & Technology Education & Research Center 度的定义对无向图的端，与该端关联
5、边的数目为该端的度数，记为：。对有向图的端，表示分开的边数，表示进入的边数。性质5.1对无向图对有向图BUPT Information Theory & Technology Education & Research Center 子图给定图，假设称图是G中由生成的子图，记为。假设，称为G的子图。特别，假设子图的端点集合为V，这个图被称为图G的支撑子图。假设，称图是G中由生成的子图，记为。BUPT Information Theory & Technology Education & Research Center 图的连通性思索边的一个序列，相邻两边有公共端，如(v1，v2)，(v2，v3)
6、，(v3，v4)，(vi，vi+1)，这个边序列称为链，链简单说就是一个延续轨迹。没有反复边的链称为简单链；没有反复端的链称为初等链或道路；假设链的起点与终点重合，称之为圈；假设道路的起点与终点重合,称之为初等圈。普通重点讨论道路和初等圈。BUPT Information Theory & Technology Education & Research Center 连通图任何两端间至少存在一条链的图，为连通图。否那么，就是非连通图。非连通图G有三个连通分支BUPT Information Theory & Technology Education & Research Center 图的例子
7、完全图两部图欧拉图正那么图BUPT Information Theory & Technology Education & Research Center 5.1.2树定义5.2无圈的连通图称为树。性质5.2除单点树，至少有两个度数为1的端(悬挂点)。性质5.3恣意树的边数m和端数n满足BUPT Information Theory & Technology Education & Research Center 定理5.1给定一个图T，假设，那么下面结论等价：1T是树；2T无圈，且；3T连通，且。5.1.2树BUPT Information Theory & Technology Educa
8、tion & Research Center 性质5.4假设T是树，那么：1T是连通图，去掉任何一条边，图便分成两个且仅仅两个连通分支；2T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。性质5.5设T是树，那么任何两点之间恰好有一条道路；反之，如图T中任何两点之间恰好有一条道路，那么T为树。5.1.2树BUPT Information Theory & Technology Education & Research Center 假设树T是连通图G的子图，TG，且T包含G的一切端，称T是G的支撑树或主树。连通图一定有支撑树。树边，连枝。5.1.2树BUPT Information T
9、heory & Technology Education & Research Center 5.1.3割集割集指的是某些端集或边子集。对连通图，去掉此类子集，图变为不连通。定义5.3割端与割端集设v是图G的一个端，去掉v和其关联边后，G的部分数添加，那么称v是图G的割端。去掉一个端集合后，G的部分数添加，这个端的集合称为割端集。BUPT Information Theory & Technology Education & Research Center 点连通度对于连通图,在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集的端数目，称为图的点连通度或连通度，连通度用表
10、示。BUPT Information Theory & Technology Education & Research Center 线连通度定义5.4割边与割边集设e是图G的一条边，去掉e后，G的部分数添加，那么称e是图G的割边。去掉一个边集合后，G的部分数添加，这个边的集合称为割边集。割边集中边数最少的割边集，称为最小割边集。最小割边集的边数目，称为线连通度，线连通度用表示。BUPT Information Theory & Technology Education & Research Center 性质5.5性质5.5对于恣意一个连通图，假设，为最小度，那么BUPT Informati
11、on Theory & Technology Education & Research Center 根本割集和根本圈对于任何一个连通图G，设T为G的一个支撑树，图中的边分为树边和连枝。对于支撑树，去掉树上任何一条边，树便分为两个连通分支，从而将原图的端分为两个集合，这两个集合之间的一切边构成一个极小边割集，这个边割集称为根本割集。每一条连枝决议的圈是根本圈，每条树边决议一个根本割集。BUPT Information Theory & Technology Education & Research Center 根本圈和根本割集根本割集和根本圈BUPT Information Theory &
12、 Technology Education & Research Center 根本圈和根本割集有许多运用，首先经过集合的对称差运算,由根本割集可以生成新的割集或它们的并集,现实上可以证明生成一切的割集；根本圈也有类似的性质。例5.2经过根本圈和根本割集分析求解电网络。根本割集和根本圈BUPT Information Theory & Technology Education & Research Center 分析：在每个等电势的区域笼一致个端点，一个电网络为一个连通图。假设这个图有n个端点，m条边，那么有n-1个独立电势变量。任取一个支撑树，有n-1个根本割集。在每个根本割集上，根据基尔霍
13、夫定律，流过根本割集电流的代数和为零。这n-1个方程由于每个方程含有独一的树枝项，所以这n-1个方程线性无关，经过这些方程可以求解一切的电势变量。根本割集和根本圈BUPT Information Theory & Technology Education & Research Center 反圈下面给出一个重要的概念：反圈。定义5.5反圈：给定图，假设，记；特别，当时，将记为或。设是的非空真子集，假设，称为由确定的反圈。BUPT Information Theory & Technology Education & Research Center 5.1.4图的矩阵表示下面将给出图的矩阵表示，
14、主要引见关联阵和邻接阵。1关联阵设图G有n个端，m条边，那么全关联阵，其中，BUPT Information Theory & Technology Education & Research Center 关联阵例5.3思索下面图5.4所表示的图BUPT Information Theory & Technology Education & Research Center 关联阵中每行对应一个端，每列对应一个边，由于完全表示了图中端集和边集的信息，所以关联阵是图的一个等价表示。每行非零元个数等于相应端的度数,每列有两个1；恣意两行或两列互换得到的关联阵本质上是一个图。将A0中每列的任一个1改为
15、-1,由于n行之和零，所以最多只需n-1行线性无关，再去掉任一行，得到关联阵A，这是一个n-1m矩阵。关联阵BUPT Information Theory & Technology Education & Research Center 可以证明A的每一个n-1阶非奇特方阵一一对应一个支撑树，并且该方阵的行列式的绝对值为1定理5.2(矩阵-树定理)用表示的转置,无向图G的主树数目关联阵vs支撑树BUPT Information Theory & Technology Education & Research Center 同时n-1阶矩阵可以直接写出,主对角线的元素为相应端点的度数,其他位置根
16、据相应的端点之间能否有边取值为-1或0。继续例5.3，假设去掉第一行，那么关联阵BUPT Information Theory & Technology Education & Research Center 关联阵共有8种支撑树如下：BUPT Information Theory & Technology Education & Research Center 邻接阵2邻接阵邻接阵是表示图的端与端关系的矩阵，其行和列都与端相对应。令为端，边的有向图，其邻接阵：BUPT Information Theory & Technology Education & Research Center 对于
17、例5.3中的图，邻接阵为：对于无向图，因此是邻接阵为对称阵。邻接阵BUPT Information Theory & Technology Education & Research Center 邻接阵包含了图的一切信息，和关联阵一样，是图的等价表示。邻接阵和关联阵以后被经常用来表示图。可以经过对邻接阵C做一些计算，得到图G的一些性质，例如可以计算C的幂来思索图能否连通。邻接阵BUPT Information Theory & Technology Education & Research Center 矩阵P为判别矩阵，1表示连通，0为不连通(1)置新矩阵P:=C;(2)置=1;(3)对一切
18、的,假设,那么对k=1,2,n，有;(4);(5)如转向步骤(3),否那么停顿。Warshall算法BUPT Information Theory & Technology Education & Research Center 5.2最短途径问题上节中引见的图只思索了图顶点之间的关联性，本节将要对图的边和端赋予权值，讨论有权图。权值在各种各样实践问题中有不同的物理意义，如费用，几何间隔，容量等。在本节中将讨论最小支撑树和最短途径问题等算法。BUPT Information Theory & Technology Education & Research Center 5.2.1最小支撑树给定
19、连通图，是定义在上的非负函数，为的一个支撑树。定义树的权为。最小支撑树问题就是求支撑树，使最小。下面引见求最小支撑树的方法，首先不加证明地援用定理5.3。BUPT Information Theory & Technology Education & Research Center 最小支撑树的特征定理5.3设是的支撑树，那么如下结论等价：1是最小支撑树；2对的任一树边，是由所决议的根本割集或反圈中的最小权边；3对的任一连枝，是由所决议的根本圈中的最大权边。这个定理描画了最小支撑树的特征。按照不同的逻辑，可以有下面不同的详细做法。BUPT Information Theory & Techno
20、logy Education & Research Center Prim算法反圈法Prim(1957年) (1)任取一点作为初始的 ；(2)在反圈 中选边的原那么是：从 中选一条权最小的边假设有多条权最小的边，那么任选一条；将选出边的邻端并入 构成 ；(3)假设在某一步， ，那么 不含支撑树；假设在某一步， ，那么由一切被选边生成的树是最小支撑树。BUPT Information Theory & Technology Education & Research Center 例5.4求以下图中的最小支撑树。Prim算法解：假设以为，按照Prim算法，选出的端序列为：，其中的顺序可以改动。最小
21、支撑树。Prim算法BUPT Information Theory & Technology Education & Research Center Kruskal算法避圈法 将一切边排序，然后由小到大选边，坚持所选的边不生成圈，假设选了n1条边，那么生成了一个最小支撑树。设是的无圈支撑子图,开场假设是连通的,那么它是最小支撑树；假设不连通,取为这样的一边,它的两个端点分属的两个不同连通分支,并且权最小。令=+,反复上述过程。BUPT Information Theory & Technology Education & Research Center 223344561BUPT Inform
22、ation Theory & Technology Education & Research Center 破圈法设是的连通支撑子图，开场，假设中不含圈，那么它是最小支撑树；假设中包含圈，设是中的一个圈，取上的一条权最大的边，令=-，反复上述过程。从连通图中寻觅圈，然后在圈中删去权最大的边，最后剩下的无圈连通图为最小支撑树BUPT Information Theory & Technology Education & Research Center 破圈法例5.5对于一个无向图,如何寻觅其中的圈?解：首先，度为1的顶点一定不在任何圈上，将这类悬挂点删去不影响对圈的寻觅，经过逐渐删去图中度为1的
23、顶点而使图简化。假设一个图不含度为1的端，可以从恣意一个端出发遨游，由于有限性，端一定会反复，而这就找到了一个圈。BUPT Information Theory & Technology Education & Research Center 223344561BUPT Information Theory & Technology Education & Research Center 5.2.2端间最短途径和路由知图，每条边有权需求求网络中端点之间的最端间隔和路由。这类问题分两种情况：1寻觅指定端至其它端的最短途径和路由，这个问题可以运用Dijkstra算法处理；2寻觅恣意二端最短途径和路
24、由,这个问题可以运用Floyd算法处理。BUPT Information Theory & Technology Education & Research Center Dijkstra算法 图的每一边上有一个权设是中的一条链，定义链的权为：。Dijkstra(1959年)算法可以简述如下：(1)初始，记，并且的标号为。(2)对任一边反圈计算的值。BUPT Information Theory & Technology Education & Research Center 在中选一边，设为；使，并令并且的标号为。(3)当出现下面情况之一时停顿。情况1：目的端满足；情况2：目的端满足，但。Di
25、jkstra算法 BUPT Information Theory & Technology Education & Research Center Dijkstra算法 例5.6在以下图中求到其他端点的最短间隔和路由。BUPT Information Theory & Technology Education & Research Center 计算如表5.1所示。Dijkstra算法 BUPT Information Theory & Technology Education & Research Center 对于Dijkstra算法,提出假设干问题如下：(1)假设端点有权如何处置?(2)
26、假设边的权可正可负,算法能否依然有效?(3)算法能否对有向图也适用？Dijkstra算法 BUPT Information Theory & Technology Education & Research Center 例5.7深度优先和广度优先搜索。假设要搜索的环境为图，每条边赋权1，搜索的起点为，运用Dijkstra算法求到恣意端的间隔，间隔表示了端的“代数。广度优先搜索可以简述如下：1开场取作为。Dijkstra算法 BUPT Information Theory & Technology Education & Research Center 2在中选边时，遵守如下原那么：首先在中选一
27、个“代数最小的端，如，然后选一切以为端点的边。假设的标号为，那么选中边的相邻端的标号应为；将新的端点参与到构成。3假设在某一步，阐明图不连通；假设在某一步,终了。留意，标号记录了该端的“代数和搜索到该端的路由。广度优先搜索BUPT Information Theory & Technology Education & Research Center 深度优先搜索1开场取作为。2在中选边时，遵守如下原那么：只选一条边，该边在中的端的“代数最大；将新的端点参与到构成。3假设在某一步，阐明图不连通；假设在某一步,终了。BUPT Information Theory & Technology Educ
28、ation & Research Center Floyd算法 定理5.4对于图,假设表示端和端之间的可实现的间隔,那么表示端和之间的最短间隔当且仅当对于恣意，有证明：首先，假设表示端和之间的最短间隔，那么BUPT Information Theory & Technology Education & Research Center 下面思索充分性：假设是任一个从端到端的链，那么反复运用充分条件，有Floyd算法 BUPT Information Theory & Technology Education & Research Center 由于表示端和之间的可实现的间隔，那么表示端和之间的最
29、短间隔。Floyd算法 BUPT Information Theory & Technology Education & Research Center Floyd算法 给定图及其边的权：初始化间隔矩阵和路由矩阵其中：BUPT Information Theory & Technology Education & Research Center F1：已求得和，根据下面的迭代求和：F2：假设kn，反复；k=n终止。Floyd算法 BUPT Information Theory & Technology Education & Research Center 对于Floyd算法,同样提出假设干问
30、题如下:(1)假设端点有权如何处置?(2)假设边的权可正可负,算法能否依然有效?(3)算法能否对有向图也适用？问题1和3在Dijkstra算法中有过讨论，这里重点讨论问题(2)。Floyd算法 BUPT Information Theory & Technology Education & Research Center 图的中心与中点知图为权图,根据Floyd算法的结果可以定义网络的中心和中点。中心对每个端点，先求此值最小的端称为网的中心，即满足下式的端：=BUPT Information Theory & Technology Education & Research Center 中点对
31、每个端点,计算,然后求出的最小值,相应的端点为中点。图的中心与中点BUPT Information Theory & Technology Education & Research Center 例5.8图G的间隔矩阵如下，用Floyd算法求恣意端间最短间隔和路由，并求中心和中点。BUPT Information Theory & Technology Education & Research Center 解：间隔矩阵包含了邻接矩阵和权的一切信息，按照Floyd算法计算结果如下：BUPT Information Theory & Technology Education & Research
32、 Center R矩阵更新BUPT Information Theory & Technology Education & Research Center 最后结果及验证BUPT Information Theory & Technology Education & Research Center 路由查找举例l找v1v4:路由查得r14=4，不转接v1v4；l找v3v4:路由查得r34=7，经7转接；l查v3v7得r37=7，无转接。l查v7v4得r74=1，经1转接：查v7v1得1无转接；查v1v4得4，无转接。l路由为v3v7v1v4l找v4v6:BUPT Information The
33、ory & Technology Education & Research Center 正向路由回溯路由BUPT Information Theory & Technology Education & Research Center n 从而，图的中心为 ，中点为上例中的中心和中点对于中心和中点，根据的计算结果可以得到：BUPT Information Theory & Technology Education & Research Center 5.3网络流量问题网络的目的是把一定的业务流从源端送到宿端，流量分配的优劣将直接关系到网络的运用效率和相应的经济效益。网络的流量分配受限于网络的拓
34、扑构造，边和端的容量，流量分配和路由规划关系亲密。本节中关于流量问题的内容均在有向图上思索，并且均是单商品流问题，即网络中需求安排的只需一种商品或业务；BUPT Information Theory & Technology Education & Research Center 5.3.1根本概念给定一个有向图，是定义在边集合上一个非负函数，称为容量；边的容量表示这条边能经过的最大流量。设是上述网络的一个流，该流有一个源和一个宿，假设能满足下述二个限制条件，称为可行流。BUPT Information Theory & Technology Education & Research Cent
35、er 可行流的条件1非负有界性：对恣意边有，2延续性:对恣意端有，BUPT Information Theory & Technology Education & Research Center 最大流问题为源宿间流的总流量。需求处理的根本问题分为两类:1最大流问题在确定流的源和宿的情况下,求一个可行流,使为最大。BUPT Information Theory & Technology Education & Research Center 最小费用流问题2最小费用流问题假设边的单位流费用为,流的费用为：最小费用流问题在确定流的源和宿的情况下,求一个可行流,使为最小。BUPT Informat
36、ion Theory & Technology Education & Research Center 下面引见割量和可增流路的概念。设是的真子集，且，表示起点和终点分别在和的边集合，这是一个带方向的反圈或割集,割集的正方向为从到。割量定义为这个割集中一切边容量的和:割量BUPT Information Theory & Technology Education & Research Center 边的流量和对可行流:表示前向边的流量和，,表示反向边的流量和，；BUPT Information Theory & Technology Education & Research Center 那么
37、源为宿为的恣意流有:1.，其中，对任:对一切,将上述等式求和：性质5.7BUPT Information Theory & Technology Education & Research Center 2.由非负，可得：性质5.7BUPT Information Theory & Technology Education & Research Center 下面讨论可增流路的概念。 从端s到端t的一个路，有一个自然的正方向，然后将路上的边分为两类：前向边集合和反向边集合。对于某条流，假设在某条路中，前向边均不饱和 ，反向边均有非0流量 ，称这条路为可增流路。在可增流路上增流不影响延续性条件，也
38、不改动其它边上的流量，同时可以使从源端到宿端的流量增大。可增流路BUPT Information Theory & Technology Education & Research Center 5.3.2最大流问题所谓最大流问题，在确定流的源端和宿端的情况下,求一个可行流,使为最大。对于一个网络，求最大流的方法采用可增流路的方法，下面的定理5.5为这种方法提供了保证。BUPT Information Theory & Technology Education & Research Center 定理5.5 (最大流-最小割定理)可行流 为最大流当且仅当 中不存在从 到 的可增流路。证明： 必要
39、性： 设 为最大流,假设 中存 在关于 的从 到 的可增流路 。构造一个新流 如下: 5.3.2最大流问题BUPT Information Theory & Technology Education & Research Center 不难验证新流为一个可行流,而且,矛盾。充分性:设为可行流,G中不存在关于这个流的可增流路。5.3.2最大流问题BUPT Information Theory & Technology Education & Research Center 令X*=v|G中存在从到的可增流路,从而。对于恣意边，有对于恣意边，有这样,那么流为最大流，为最小割。证毕。性质5.8：假设
40、一切边的容量为整数，那么必定存在整数最大流。5.3.2最大流问题BUPT Information Theory & Technology Education & Research Center 求最大流的根本思想是： 在一个可行流的根底上， 找 到 的可增流路，然后在此路上增流，直至无可增流路时，停顿。M算法：从任一可行流开场，通常以零流开场。1标志过程：从 开场给邻端加标志,加上标志的端称已标端;5.3.2最大流问题BUPT Information Theory & Technology Education & Research Center 2选查过程：从开场选查已标未查端；查某端，即标其
41、能够增流的邻端;一切邻端已标，那么该端已查。标志宿端，那么找出一条可增流路到宿端，进入增流过程。3增流过程：在已找到的可增流路上增流。5.3.2最大流问题BUPT Information Theory & Technology Education & Research Center 步骤：M0：初始令；M1：标源端：；M2：从始，查已标未查端，即标的满足以下条件的邻端，假设，且，标为:其中，为已标值。假设，且，标为:其中，其他端不标。5.3.2最大流问题BUPT Information Theory & Technology Education & Research Center 一切能加标的
42、邻端 已标，那么称 已查。倘假设一切端已查且宿端未标，那么算法终止。M3：假设宿端 已标，那么沿该可增流路增流。M4: 前往M1。5.3.2最大流问题BUPT Information Theory & Technology Education & Research Center 上面的算法是针对有向图且端无限制的情况。假设是有无向边，端容量及多源多宿的情况，可以进展一些变换，化为上述规范情形。这个算法的复杂度不是多项式的，但是经过简单改良后算法为多项式复杂度。 需求处理下面的情况：1.端有容量限制；2.无向边；3.多源多宿；5.3.2最大流问题BUPT Information Theory &
43、 Technology Education & Research Center 5.3.3最小费用流问题假设网络为图，源端为,宿端为，边的单位流费用为，流的费用为:所谓最小费用流问题:在确定流的源和宿的情况下,求一个可行流,使C为最小。BUPT Information Theory & Technology Education & Research Center 最小费用流问题是线性规划问题，但也可用图论方法求解,效率更高。对于它的存在性可以这样了解，流量为F的可行流普通不是独一的，这些不同的流的费用普通也不一样,有一个流的费用最小。寻觅最小费用流，可以用负价环法算法(Klein,1967年)
44、。所谓负价环的意义如下:负价环为有向环,同时环上费用的和为负。负价环算法的详细步骤如下：5.3.3最小费用流问题BUPT Information Theory & Technology Education & Research Center K0：在图G上找恣意流量为F的可行流;K1：做流的补图;做补图的方法如下:对于一切边，假设，构造边，容量为，单位费用为；对于一切边，假设，构造边，容量为，单位费用为。K2：在补图上找负价环。假设无负价环，算法终止。5.3.3最小费用流问题BUPT Information Theory & Technology Education & Research Ce
45、nter K3：在负价环上沿环方向使各边增流，增流数为：K4：修正原图每边的流量，得新可行流。K5：前往K1。上面的算法中需求寻觅负价环，这个可以经过Floyd算法来处理。5.3.3最小费用流问题BUPT Information Theory & Technology Education & Research Center 例5.10：知 ， ，要求 。求最小费用流。5.3.3最小费用流问题BUPT Information Theory & Technology Education & Research Center 解：上面可行流安排总费用为:C=102。下面做补图, 寻觅负价环, 调整可行流。5.3.3最小费用流问题BUPT Information Theory & Technology Education & Research Center 这个新可行流的补图如下：这个补图没有负价环。5.3.3最小费用流问题BUPT Information Theory & Technology Education & Research Center 习题5.45.65.85.10
