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

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

1、通信网理论基础通信网理论基础第五章 网络拓扑第五章 网络拓扑结构分析结构分析本章目的本章目的网络拓扑结构分析是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次拓扑结构是通信网规划和设计的第层次问题。通信的拓扑结构图论的模型来代通信网的拓扑结构可以用图论的模型来代表，本章分析的主要问题为最小支撑树、最短路径和网络流量安排等问题。25.1 图论基础图论基础5 1 1图的定义和基本概念图的定义和基本概念5.1.1图的定义和基本概念图的定义和基本概念例5.1欧拉(Euler)7桥问题。ADCB B3电网络（基尔霍夫）4图的定义图的定义定义5.1 所谓一个图G，是指给了一个端点集合V，以及

2、边的集合或V中元素的序对集合E，图一般用来表示。),(GEV集合，图般用来表示如果图G有n端m条边，可将V和E表示为)(VE为，。某边的端为，称这边和端关联，,.,21nvvvV,.,21meeeE jivv，jivv，这个边也可记为:或。)(jivv，ije5图的示例图的示例1v1ee6e1234,Vv v v vEe e e e e ev4v1e2e3e6123456,Ee e e e e e其中，2v44e5e112213324423(,)(,)(,)(,)ev vev vev vev v，3v1v324423534614(,)(,)(,)(,)()ev vev vGV E，可将右图记为

3、1e3e6e1126(,),GV Eve e e可将右图记为。与关联2v4v2e4e5e11261234,vv v v与是相邻节点与是相邻边63v412346,ee e e e与是相邻边图的相关概念图的相关概念1 节点：节点：表示物理实体，用表示。边边节点间的连线表示两节点间存在连接关系iv 边边：节点间的连线，表示两节点间存在连接关系，用表示。空图空图：称为空图。ijeV 空图空图：称为空图。孤立点图：孤立点图：称为孤立点图，也叫平凡图。1v5vV E 也叫平凡图。无向图：无向图：设图，当对存在某种关系R等价于G(,)V Eivjvjv2v4v对存在某种关系R等价于对存在某种关系R，称G为无

4、向图。即图G的任意一条边都对jvjviv3v向图。即图G的任意条边都对应一个无序节点对,()ijvv，()()ijjiv vv v3无向图示例无向图示例7(,)(,)ijjiv vv v图的相关概念图的相关概念2有向图：有向图：设图，当对存在某种关系R不等价于对存在某种关系R称G为无向G(,)V Eivjv系R不等价于对存在某种关系R，称G为无向图。即图G的任意一条边都对应一个有序节点对jviv()()()对,。有权图：有权图：设图，如果对每一条边或()ijvv，(,)(,)ijjiv vv vG(,)V Eke它的每一个节点赋以一个实数，则称图G为有权图或加权图，称为权值。ivkpkp2 5

5、1v5v1v5v2.53.14.22.7有向图示例有向图示例2v4v有权图示例有权图示例2v4v1.85.383v3v图的相关概念图的相关概念3自环：自环：若与一个边相关联的两个节点是同一个节点则称边为自环ke节点，则称边为自环。重边：重边：在无向图中与同一对节点关联的两条或两ke条以上的边称为重边。在有向图中与同一对节点关联且方向相同的两条或两条以上的边称为重边。1v5v1ee4e1v5v1ee4e2v1vv2e5e6ee1v2vv2e5e6ee自环与重边自环与重边23v4v3e7e8e3v4v3e7e8e9自环与重边自环与重边33图的相关概念图的相关概念4简单图：简单图：不含有自环及重边的

6、图。伪图：伪图：非简单图称为伪图。节点的度度：与某节点相关联的边数定义为该节点节点的度度：与某节点相关联的边数定义为该节点的度数，记为。有向图中，用表示离开或从射出的边数，即节点()id v()idviviv有向图中，用表示离开或从射出的边数，即节点的出度出度；用表示进入或射入节点的边数即节点的入度入度。节点的度数表示为()ii()idviviiviv()()()iiid vdvdv1v5v1e2e4e5e6e1v5v1e2e4e5e6e12()4()4d vd v11()4()2d vdv4v23e5e6e7ee2v4v3e567e8e23()()2d v2v1_1()()2dv103v3e

7、8e3v38e性质性质5.1 对图，G(,)V E|Vn|Em（1）如果G是无向图，1()2niid vmnn（2）如果G是有向图，11()()nniiiidvdvm1证明（）每个边有两个端点按照端来计数就是等式 1证明：（）每个边有两个端点，按照端来计数就是等式左边，这种计数对每条边均重复且恰恰重复一次；）对于有向图每条边有两个端它们和边的关系不同2()()dvdv（）对于有向图，每条边有两个端，它们和边的关系不同，出度按段计数每边各一次，类似，所以有()()v Vv Vv Vv Vdvdvm。11v Vv V图的相关概念图的相关概念5 子图子图：给定图，若，称图G(,)V E11V,V E

8、E111G(,)V E是G中由生成的子图，记为。特别若子图的端点集合为V,这个图被称为图G的支撑子图（生成子图）支撑子图（生成子图）。1V1 G V 若，称图是G中由生成的子图记为1E,E11V|vV vE是 中某边的端点111G(,)V EEG E是G中由生成的子图，记为。1E1G E1v5v1v5v1v5v2v4v2v2v4v3v3v3v12abc图的相关概念图的相关概念6链（链（Chain）：有限条边的一种串序排列称为边序列或链。没有重复边的链称为简单链简单链没有重复边的链称为简单链简单链。没有重复端的链称为初等链初等链或道路道路；起点和终点不在同一个节点的链叫开链开链。起点和终点重合的

9、链叫圈（闭链）圈（闭链）。起点和终点重合的道路叫初等圈初等圈。链中边的数目称为链的长度链的长度。链中边的数目称为链的长度链的长度。一般重点讨论道路和初等圈。13v1e4e1 2 2 6 4 6 2 3 3ve v e v e v e v链：1v5v2e4e5e6e1 2 2 6 4 5 5 8 3ve v e v e v e vve v e v e v简单链：道路2v4v7e1 2 2 74 5 51 2 2 74 5 5 4 1ve v e v e vve v e v e v e v道路：初等圈：3v3e78e314图的连通性图的连通性任何二端间至少存在一条链的图，为连通图。否则，就是非连通

10、图。非连通图G有三个连通分支非连通图G有三个连通分支G G15图的例子图的例子1v5v1v5v2v4v2v4v242v4完全图完全图两部图两部图3v3vKK完全图完全图两部图两部图(1)22nn nm nK,m nKmn边数为22 16图的例子图的例子1v4v1v5v3v+2v4v1v2v3v3vv5v2v4v1vvv1v2v3v42v4v欧拉图正则图欧拉图正则图23v175.1.2 树树定义定义5.2无圈的连通图称为树。性质性质5.2除单点树，至少有两个度数为1的端(悬挂点)。性质性质5.3任意树的边数m和端数n满足1 1 nm18 若且T含有G的所有端，称T是G的主树主树或支撑树支撑树；T

11、G根树星树线树根树星树线树 主树上的边称为树枝树枝；非树枝的边称为连枝连枝；主树是树枝集树枝集；连枝的边集称为连枝集连枝集或树补树补。树上任两端间添加一条连枝，则形成圈，称为基本圈基本圈。连接图G的主树T的树枝数称为图G的阶阶。若G有n个端，则它的阶 为(G)1则它的阶为(G)=n-1。连接图G的连枝集的连枝数称为图G的空度空度，记为。设G有m条边，则(G)=m-n+1。19有m条边，则(G)m n+1。树的等价性质树的等价性质定理定理5.1给定一个图T，若，则下面论断等价|Vn|Em面论断等价：（1）T是树；（2）T无圈，且；（3）T连通，且。1mn1mn5 31证明：由性质，可推导（）（2

12、），（1）（3）。5.31 211Tmn由性质，可推导（）（2），（1）（3）。证明（）（）。若 有圈且可在圈中删去任意一条边图仍然连1Tmn若 有圈且。可在圈中删去任意条边，图仍然连通。依次删除直至图变成连通无圈图或树，与假设矛盾；20 3112Tkk证明（）（）。若 不连通且它有 个连通的分支（）每个12(1)kiiTmnkkipmpn若 不连通且。它有 个连通的分支（），每个连通的分支为树。若第 个树有 个点，则1()2iiippkn，与假设矛盾。树是最小连通图；树是最小连通图；21树是最大无圈图。树是最大无圈图。树的性质树的性质性质性质5.4：若T是树，则：5.4.1:T是连通图，去掉

13、任何一条边，图便分成两个且仅仅两个连通分支；5 4 2 T是无圈图但添加任何条边图便会包含个5.4.2:T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。1)TT证明是树连通且去掉个边(后11 1,)TTmneu veT证明：是树连通且；去掉一个边(后，若图变成三个连通分支，则补上 后，图 有两个连通分支，2(,)Teu vTT不连通，与已知条件矛盾。若图继续为连通图。则存在。对于图，两条12ee不同的边，构成一个圈，与已知条件矛盾。22树的性质树的性质5.4.2(,)u vG再看，设是 中任意(,)()u vP再看设中任两个不相邻的顶点，有唯一一条道路，如果添上一条以(,),)u v

14、Pu vePeG条道路，如果添上条以(为端点的边，则形成了中唯的个圈Ge了中唯一的一个圈。23树的性质树的性质性质性质5.5：设T是树，则任何两点之间恰好有一条道路反之如图T中任何两点之间恰好有条道道路；反之，如图T中任何两点之间恰好有一条道路，则T为树。证明：先证必要性。因为树是连通的，所以树中任意两个顶点之间必有道路。12121212(,)(,),()Gu vPPPPPex y ePPPe如果在 中存在两条不同的道路 和，因为，所以存在 中的一条边。显然是连通1212(,),()(,)yx yPPeGG以存在 中的条然是的，所以它含有一条的道路。如此，则是 中的一个圈这与 是树的假设矛盾G

15、GGCC个圈。这与 是树的假设矛盾。再证充分性。是连通的，如果 中有一个圈，那么 上的任意两顶点之间均有两条不同的道路这与假设矛盾24意两顶点之间均有两条不同的道路，这与假设矛盾。5.1.3 割集割集割集割集指的是某些端集或边子集子集。对连通图，去掉此类子集图变为不连通去掉此类子集，图变为不连通。分为割边集、割端集和混合割集。割端与割端集设 是图G的个端去掉 和其关联边后G设v是图G的一个端，去掉v和其关联边后，G的部分数增加，则称v是图G的割端割端。去掉一个端集合后G的部分数增加这个端去掉一个端集合后，G的部分数增加，这个端的集合称为割端集割端集去掉任意一个端，图的部分数不变，则称这种去掉任

16、意个端，图的部分数不变，则称这种图为不可分图不可分图。25点连通度点连通度对于连通图,在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集的端数目称为图的点连通度最小割端集的端数目，称为图的点连通度或连通度，连通度用表示。262v5vace2v5vae6v4vbcdf1v4v5abcdef1v3v6vf3v6vbf割端与割端集割端与割端集割端与割端集割端与割端集4232434144 ,vv vv vv vv vv割端集有：，等。是割端456 vvv是最小割端集。若图中没有 和，则图是不可分图。2756 vv若图中没有 和，则图是不可分图。割边与割边集设e是图G的一条边，去掉

17、e后，G的部分数增加，则称e是图G的割边。去掉一个边集合后，则割去掉个集后G的部分数增加，这个边的集合称为割边集。若某割边集S的任何真子集任何真子集都不是割边集，则若某割边集S的任何真子集任何真子集都不是割边集，则称S为割集。28线连通度线连通度割边集中边数最少的割边集，称为最小割边集。最小割边集的边数目，称为线连通度，线连通度用表示连通度用表示。291vc1v1v14v5vabdef14v5vde14v5vae2v3vdfg2v3vdfg2v3vf1vc,a b cc b d gg fc e割边集有等14v5vabde,a b cg fc eg fc e割集有等最小割边集有。2v3vdf最小

18、割边集的边数，称为图的结合度，表征图的连通程度，与网络可靠性有关。30征图程度与靠性有关连通度的简单性质连通度的简单性质性质性质5.6对于任意一个连通图，若为最小度则),(GEV|m2若，为最小度，则nV|mE|nm22证明：首先，所以。考虑一个大小为的割边集，将每条边换成它的邻()2v Vd vmn2mn考虑个大小为的割边集，将每条边换成它的邻端，这是一个大小最多为的割端集，所以。一定存在某个端它的度为则与该端关联的边一定存在某个端，它的度为，则与该端关联的边构成一个大小为的割边集，所以。综上2m综上，。2mn31基本割集和基本圈基本割集和基本圈对于任何一个连通图G，设T为G的一个支撑树，每

19、条连枝决定的圈是基本圈每一条连枝决定的圈是基本圈。确定了连通图的一个支撑树后，每条树边可以决定一个基本割集。对于支撑树，去掉树上任何一条边，树便分为两对于支撑树，去掉树上任何条边，树便分为两个连通分支，从而将原图的端分为两个集合，这两个集合之间的所有边形成一个极小边割集，这两个集合之间的所有边形成个极小边割集，这个边割集称为基本割集。32基本圈和基本割集的例基本圈和基本割集的例基本圈和基本割集e ee e1 1e e2 2e e6 6e e3 3e e5 5e e4 4e e5 5图 5.3 基 本 圈 和 基 本 割 集1634,Te e e e支撑树1634156253245,(,),(,

20、),(,),(,)()()Te e e ee ee e ee ee ee e ee e e e支撑树基本割集为基本圈为336236154(,),(,)e e ee e e e基本圈为。基本圈和基本割集有许多应用，首先通过集合的对称差运算对称差运算 由基本割集可以生成新的割集或它们对称差运算对称差运算,由基本割集可以生成新的割集或它们的并集,事实上可以证明生成所有的割集；基本圈也有类似的性质也有类似的性质。1152625(,),(,),Se eSe e e基本割集有：332445 (,),(,)Se eSe e512126(,)SSSe e e6131235(,)SSSe e e e()SSSe

21、 e11123136(,)SSSSe e e()SSSSe e e e e71414(,)SSSe e823356(,)SSSe e e1212412456(,)SSSSe e e e e13234346(,)SSSSe e e()SSSS34924246(,)SSSe e e10342345(,)SSSe e e e141341234(,)SSSSe e e e15123413456(,)SSSSSe e e e e基本圈和基本割集的应用基本圈和基本割集的应用例5.2 通过基本圈和基本割集分析求解电网络。10nmn个端点，条边，有个独立电势变量。基尔霍夫电流定律：流过基本割集的电流的代数和为

22、；10n基尔霍夫电流定律流过基本割集的电流的代数和为；可通过个线性无关的方程求解。基尔霍夫电压定律：环绕一个基本圈的电势差为350.1mn基尔霍夫电压定律：环绕个基本圈的电势差为可通过个线性无关的方程求解。反圈反圈 5.5(,)GV ESTV定义反圈：给定图，若，,(,),;)GGGS Tu vEuS vTTVSSTSS记：特别，当时，将，记为（）或（。)GGGGXVXXX特别，当时，将，记为）或设是 的非空真子集，若（），称（）为由确定的反圈X确定的反圈。1vcS=V1,V2)T=V3,V4,V54v5vabde,)S,TG=b,c,d,g2v3v5dfg362g5.1.4 图的矩阵表示图的

23、矩阵表示图的矩阵：关联阵和邻接阵。1 关联阵每行对应一个端每列对应一个边完全表示了每行对应个端，每列对应个边，完全表示了图中端集和边集的信息，是图的一种等价表示。设图 有 个端条边则全关联阵其中0,1,ijn mijjiGnmAaaev设图 有 个端，条边，则全关联阵其中若 与 关联在无向图中0,1jjijjiaevaevv 在无向图中若 与 不关联与 关联 离开1,1,0ijjiiijjiiaevvaevv 与 关联 离开在有向图中与 关联 指向与 不关联370,ijjiaev与 不关联例例5.3的全关联阵的全关联阵例例5.3考虑下面图5.4所表示的图1e12e5v1e1v2e24e5v4v

24、3e2e4e3解：依照定义，全关联阵为图5.4 例5.3图1001111000A00110100110A3800110关联阵的简单性质关联阵的简单性质(1)每行非零元个数等于相应端的度数,每列有两个1个1；(2)任意两行或两列互换得到的关联阵本质上是一个图。(3)A0的秩小于n，所以最多只有n-1行线性无关，()0的秩小于，所以最多只有行线性无关，再去掉任一行，得到关联阵A，这是一个m(n-1)矩阵。矩阵39关联阵的简单性质关联阵的简单性质A的每一个n-1阶非奇异方阵一一对应一个支撑树123eee1234510011eeeee12311100110vBv1021001111000vAv2311

25、0011vv340110100110vv12512101eeevB223110011Bvv40矩阵矩阵-树定理树定理定理定理5.2(矩阵-树定理)用表示的转置,无向图G的支撑树数目TAA()det()Tt GAA同时n-1阶矩阵可以直接写出,主对角线的元素为相应端点的度数 其余位置根据相应的端点之()()TAA素为相应端点的度数,其余位置根据相应的端点之间是否有边取值为-1或0210()det1318t G01241例5.3，如果去掉第一行，则210()det1318t G()012共有8种支撑树如下：42邻接阵邻接阵2 邻接阵邻接阵是表示图的端与端关系的矩阵，其行和列都与端相对应行和列都与端

26、相对应。(,)GV Enm令为 端，边的有向图，ij n nCc其邻接阵：有边ijij1,vv0,vvijc若 到 有边其中，若 到 无边ij,若 到 无43例例5.3的邻接阵的邻接阵对于例5.3中的图，邻接阵为：0111v1e1v210101101Ce5e2e41010v4v3e3图5.4 例5.3图对于无向图，因此是邻接阵为对称阵。jiijcc 44图连通的图连通的Warshall算法算法由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。邻接阵和关联阵以后被经常用来表示图邻接阵和关联阵以后被经常用来表示图。可以通过对邻接阵C做一些计算，得到图G的些性质例如可以计算 的幂来考虑图的

27、一些性质，例如可以计算C的幂来考虑图是否连通。453(3),(,)i jCi jC例如中的的元素，如果不为零，由于(3),i ji kk ll ji kk lklCc c ccc，则至少存在一组或个长度为 的链使端 和端 相连v1e1v2,13l jcij 或一个长度为 的链使端 和端 相连。0111e5e2e410101101Cv4v3e3图54 例53图110110103121图5.4 例5.3图231211212C4621311212Warshall算法算法(1)置新矩阵P:=C;节点序号（逐列扫描）节点序号（逐列扫描）(2)置;(3)对所有的,如果,则对1i j,1j ip1,2,kn

28、()对所有的,如果,则对;(4);,j i,:j kj ki kppp1ii,考察节点考察节点i与所有节与所有节(4);(5)如转向步骤(3),否则停止。1ii ni考察节点考察节点i与所有节与所有节点点k之间连接关系之间连接关系13144725Warshall算法举例算法举例311000110001100011000141100000110PC1001100011100011iP250011100011,1100011 1,:jj kj kkif pppp,1,j kj kkppp11000110001100011000110001100011000110002110000011000111

29、iP3110000011000111iP4110000011100111iP5110000011100111iP,200011 1,jif p,300011 1,jif p,400111 1,jif p,500111 1,jif p48,2,:j kj kkppp,3,:j kj kkppp,4,:j kj kkppp,5,:j kj kkppp5.2 最短路径问题最短路径问题上节中介绍的图只考虑了图顶点之间的关联性，本节将要对图的边和端赋予权值，讨论有权图。讨论有权图权值在各种各样实际问题中有不同的物理意义如费用几何距离容量等意义，如费用，几何距离，容量等。在本节中将讨论最小支撑树和最短路径

30、问题等算法。495.2.1 最小支撑树最小支撑树给定连通图，是定义在上的,)GV E（()w eE非负函数，为的一个支撑树。定义树的权为。(,)TTV EGT()()w Tw e义树的权为最小支撑树问题就是求支撑树使Te E()最小支撑树问题就是求支撑树，使最小。下面介绍求最小支撑树的方法，首T()w T先不加证明地引用定理5.3。50最小支撑树的特征最小支撑树的特征5.3,:TG定理设是 的支撑树 则如下论断等价(1);(2)TTe ee是最小支撑树对的任一树边是由 所决定的基本割集或(2),;Te ee对的任树边是由 所决定的基本割集或反圈中的最小权边(3),Te ee对的任一连枝是由 所

31、决定的基本圈中的最大权边。这个定理描述了最小支撑树的特征。依照不同地逻辑可以有下面不同地具体做法 最大权边。不同地逻辑，可以有下面不同地具体做法。51Prim 算法算法Pr(1957)im：反圈法0()(1)(2)()kXX（）任取一点作为初始的；在反圈中选边的原则是：()()()()kX从中选一条权最小的边（如果有多条权最小的边，则任选一条）；()(1)();(3)()kkkXXXG则任选条）；将选出边的邻端并入形成若在某步则 不含支撑树()()(3),()kkXGXV若在某一步，则 不含支撑树；若在某一步，则由所有被选边生成的树是最小支撑树。52例例5.4例5.4 求下图中的最小支撑树。1

32、367254,v v v v v v v选出的端序列为：1367254*,()15v v v v v v vw T最小支撑树复杂度分析复杂度分析：算法从开始到终止，需要选出条边每步使 个端与1()1nknkk nk条边，每步使 个端与个端比较，需要次比131(1)(1)(2)(3)()nk nknnnO n较，然后选出反圈中权最小的边，计算量最大为：531(1)(1)(2)(3)()kk nknnnO nnKruskal算法算法(避圈法避圈法)()主要思想：将所有边排序，由小到大选边，只要保持所选边不形成圈，选了n-1 条边后，就可以形成了一个最小支撑树。就可以形成了个最小支撑树设是的无圈支撑

33、子图，开始若是连通的 则它是最小支撑树若不()kGG(0),)GV（()kG()kG若是连通的,则它是最小支撑树；若不连通,取为这样的一边，它的两个端点分属的个连通分支 并权最小()kG()kG()ke属的两个不同连通分支,并且权最小。令，重复上述过程。()kG(1)()()kkkGGe令K-算法也称“避圈法”。54Kruskal算法示例算法示例边大小关系为：3613671265ddddddddd23144527dddd选取的端点序列为：3617254,v v v v v v v选取的端点序列为：P结论与 算法一致！55破圈法破圈法设是的连通支撑子图，开始，()kGG(0)GG若中不含圈，则它

34、是最小支撑树；若中包含圈，设是中的一个圈，取上的一()kG()kG中包含圈，设是中的个圈，取上的条权最大的边，令，重复上述过程(1)()()kkkGGe()ke复上述过程。56如何寻找图中的圈如何寻找图中的圈例5.5 对于一个无向图,如何寻找其中的圈?考虑到去掉图的悬挂点，不影响对图的圈的寻找在逐渐去掉图的悬挂点后继续的寻找，在逐渐去掉图的悬挂点后，继续对剩下的图重复上述的操作。最后得到的图没有悬挂点如果图没有悬挂点可以图没有悬挂点。如果图没有悬挂点，可以从一个端出发漫游，这样任何一个漫游都会找到个会寻找到一个圈。575.2.2 端间最短路径和路由端间最短路径和路由已知图，每条边有权需要求网络

35、中任意端点之间的最短距离和,)GV E（(,)i j,0i jw需要求网络中任意端点之间的最短距离和路由。这类问题分两种情况：1 寻找指定端至其它端的最短路径和路由，这个问题可以使用Dijkstra算法解决；2 寻找任意二端最短路径和路由,这个问题可以使用Floyd算法解决。58指定端至其它端的最短路径和路由指定端至其它端的最短路径和路由Dijkstra算法算法Dijkstra算法算法()0.GVEw e图（，）的每一边上有一个权()().(1959)eGww eDijkstra设 是 中的一条链，定义链 的权为：算法可以简述如下：(0)1111()()()(1959)(1),0(,1).(2

36、)()()()kkkDijkstraXvvi lXvXvXw算法可以简述如下：初始记，并且 的标号为对任一边反圈计算的值0()()00(2)(,)()(,),.()(,)(,iliilkkili lXvXvXwXi lvXv对任边反圈计算的值在中选一边，设为0().i()kXi使并令并且的标号为（）()00 0000 0000(,)()min(),.(3).kii liillii llli lXwwwvi使并令并且的标号为（）当出现下面情况之一时停止()()()12,(.kjkkjvXvXX 情况情况但）59(j例例5.6例例5.6在下图中求到其余端点的最短距离和路由1v由。15234vvvv

37、v置定端距离路由1523401018426321置定端距离路由84263218352336545365453656260Dijkstra算法的进一步讨论算法的进一步讨论j对于Dijkstra算法,提出若干问题如下：(1)如果端点有权如何处理?(2)如果边的权可正可负 算法是否仍然有(2)如果边的权可正可负,算法是否仍然有效?(3)算法是否对有向图也适用？11v2v1v23带负边的图带负边的图613v带负边的图带负边的图搜索搜索例例5.7深度优先和广度优先搜索。如果要搜索的环境为图，每条边赋权1，搜索的起点为，应用Dijkstra算法求到任意端,)GV E（1v1v的距离，距离表示了端的“代”数

38、。ivivi广度优先搜索：(0)1()()12kkvXXX（）开始取 作为；（）在中选边时，遵守如下原则：首先在中选一2()(1)iiXXvvvli（）在中选边时，遵守如下原则：首先在中选个“代数”最小的端，如，然后选所有以 为端点的边。如果 的标号为则选中边的相邻端的标号应为；()(1)()(,)(1,)iiikkkvliXX果 的标号为，则选中边的相邻端的标号应为；将新的端点计入到形成；如果在某步表示图不连通如果在某62()()VkkXX（3）如果在某一步，表示图不连通；如果在某一步，结束；(0)1X深度优先搜索：（）开始取 作为(0)1()12kvXX（）开始取 作为；（）在中选边时，遵

39、守如下原则：只选一条边，该边()()(1)()kkkkXXXX 在中的“代”数最大，将新的端点计入到形成；（3）如果在某一步，表示图不连通；如果在某()VkX如果在某步表示图不；如果在某一步，结束；63广度优先搜索示例广度优先搜索示例BFS(Breadth First Search)BFS(Breadth First Search)广度优先搜索过程广度优先生成树广度优先搜索过程广度优先生成树64使用广度优先搜索在访问了起始顶点v 之后，由出发依次访问的各个未曾被访问过的邻接v 出发，依次访问v 的各个未曾被访问过的邻接顶点w1,w2,wt，然后再顺序访问w1,w2,t的所有还未被访问过的邻接顶

40、点再从这些访wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点如此做下去直到图中所有顶过的邻接顶点，如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。65深度优先搜索示例深度优先搜索示例DFS(Depth First Search)DFS(Depth First Search)66 DFS 在访问图中某一起始顶点v 后，由v 出发，访问它的任邻接顶点1再从1出发访问访问它的任一邻接顶点w1；再从

41、w1 出发，访问与w1邻接但还没有访问过的顶点w2；然后再从2出发进行类似的访问如此进行下去w2 出发，进行类似的访问，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u 为止接着退回步退到前次刚访问过的顶止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有则访问此顶点之后再从此顶点出发进果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索重复上述过程直到连通图中所有顶进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。67任意二端最短路径和路由任意二端最短路径和路由Floyd算法算法Floyd算法算法定理

42、5.4对于图,如果表示端和端(,)w i jGij之间的可实现的距离,那么表示端 和之间的最短距离当且仅当对于任意，有:(,)w i jiji,k,j之间的最短距离当且仅当对于任意，有,j(,)(,)(,)w i jw i kw k j()i jij证明首先如果表示端 和端 之间的最短距离(,)(,)(,)(,)w i jijw i jw i kw k j证明：首先，如果表示端 和端 之间的最短距离，则下面考虑充分性12(,)kiji i iij下面考虑充分性：若 是任一个端 到端 的链，有11112211223(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)()kw i jw i

43、 iw ijw i iw i iw ijw i iw i iw i iw ijw68Floyd算法算法y给定图及其边的权G(,)i ji,jw(1in,1jn)：初始化距离矩阵和路由矩阵其中0F(0)W(0)R其中：(0)ijijweEweE若若0ijijweEij若若(0)(0)wijijjr 若其它0,ij其它69Floyd算法算法yF1：已求得和，依据下面的迭代(k-1)W(k-1)R求和(k)W(k)R(k)(k 1)(k 1)(k-1)i()(k)(k 1)(k 1)(k 1)i,ji,ji,kk,jwmin(w,ww)(1)()(1)kkk若(1)()(1),(),(1)()(1)

44、,kkki ki ji jki jkkki ji ji jrwwrrww若若F2：若kn，重复；k=n终止。示例示例示例示例5.85.8示例示例示例示例5.85.870Floyd算法的进一步讨论算法的进一步讨论y对于Floyd算法,同样提出若干问题如下:(1)如果端点有权如何处理?(2)如果边的权可正可负 算法是否仍然有效?(2)如果边的权可正可负,算法是否仍然有效?(3)算法是否对有向图也适用？()问题1和3在Dijkstra算法中有过讨论，这里重点讨论问题(2)重点讨论问题(2)。71图的中心与中点图的中心与中点已知图为权图,根据Floyd算法的结G(,)V E果可以定义网络的中心和中点。

45、中心()对每个端点，先求此值最小的端称为网的中心，即满足下式的端：i(),max()ni jjw()()*,max()minmax()nniji jijjww网的中心可以作为维修中心或服务中心。72图的中心与中点图的中心与中点中点对每个端点,计算,i(),nii jjsw然后求出的最小值,相应的端点为中点。is网的中点可做全网的交换中心。示例示例示例示例5.85.8示例示例示例示例5.85.873例例5.8例5.8 图G的距离矩阵如下，用Floyd算法求任意端间最短距离和路由，并求中心和中点。点01.29.20.5053.12.041.51 2506 701.2506.79.26.7015.6

46、w3.1415.600 521 50740.521.50例例5.8解：距离矩阵包含了邻接矩阵和权的所有信息，依照Floyd算法计算结果如下：75例例5.80.001001001.209.201000.501000.001005.001003.102.0002345671034567(0)1001000.001001004.001.50w1.205.001000.006.701001009 201001006 700 001560100(0)1204567R12305679.201001006.700.0015.601001003.104.0010015.600.001000 502 00150

47、1001001000 001234067123450712345600.001001001.209.201000.501000 001005001003102 00023456710345670.502.001.501001001000.001234560(1)1000.001005.001003.102.001001000.001001004.001.50w1.205.001000.006.701001.70(1)10345671204567R1230561w1.205.001000.006.701001.709.201001006.700.0015.609.701003.104.00100

48、15.600.00100R123056112340611234507760.502.001.501.709.701000.001231160例例5.8077447770777670.002.502.001.207.905.600.502 500 0035037010 403102 00(7)70777677707767R1110511(7)2.500.003.503.7010.403.102.002.003.500.003.209.904.001.50w1.203.703.200.006.706.801.700544440442232202w1.203.703.200.006.706.801.

49、707.9010.409.906.700.0013.508.405.603.104.006.8013.500.005.1012311200.502.001.501.708.405.100.00对于中心和中点根据的计算结果可以得到对于中心和中点，根据的计算结果可以得到：7.9，10.4，9.9，6.8，13.5，13.5，8.4 19 725 224 123 256 838 119 2it 19.7，25.2，24.1，23.2，56.8，38.1，19.2从而，图的中心为，中点为is 4v7v返回返回返回返回返回返回返回返回77返回返回返回返回返回返回返回返回5.3 网络流量问题网络流量问题网

50、络的目的是把一定的业务流从源端送到宿端，流量分配的优劣将直接关系到网络的使用效率和流量分配的优劣将直接关系到网络的使用效率和相应的经济效益。网络的流量分配受限于网络的拓扑结构，边和端的容量，流量分配和路由规划关系密切。本节中关于流量问题的内容均在有向图上考虑，并且均是单商品流问题，即网络中需要安排的只并且均是单商品流问题，即网络中需要安排的只有一种商品或业务；785.3.1 基本概念基本概念给定一个有向图，是定义在边G(V,E)()c e集合上一个非负函数，称为容量；边的容量表示这条边能通过的最大流量。E,i je,i jc的容量表示这条边能通过的最大流量设是上述网络的一个流，该流有一个源和个