第二章 通信网的拓扑结构

第二章 通信网拓扑结构

通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。

§2.1图论基础

图论是应用数学的一个分支，本节介绍它的一些概念和结论。其基本内容可参见（1）和（2）。

2.1.1图的定义

例2.1 哥尼斯堡7桥问题;

所谓一个图，是指给了一个集合V，以及V中元素的序对集合E，V和E中的元素分别称为图的端点和边。

下面用集合论的术语给出图的定义：

RE设有集合V和E，V={v1，v2，……，vn}， E={e1，e2，…… em} ，且VV则V和E组成图G，称V为端集，E为边集。

下面给出图的一些概念:

当eij=(vi，vj)，称边eij和端vi与vj关联； 当viRvj不等价于vjRvi 时，为有向图； 当viRvj等价于vjRvi

(eij=eji)时，为无向图；

当V=φ(此时E必为空集) ，为空图； 自环，孤立点图，重边；

简单图: 不含自环和重边的图称为简单图.

当V，E均有限元 ∣V∣，∣E∣≠∞时，称为有限图。我们一般讨论的都是有限图，考虑到实数集的不可数性，任何有限图都可以表示为三维空间的几何图形，使每两条边互不相交，而且边均可用直线来实现。但是若要在平面实现则不一定能办到，稍后我们会给出平面图的概念。

子图:若A的端集与边集分别为G的端集与边集的子集，则A为G的子图。若AG，且AG，则A为G的真子图。特别地，当A的端集和G的端集相等，称A为G的支撑子图。由端点子集诱导生成的子图.

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

图的运算:

G1G2, G1G2, Gc等

图的几种表现形式: 集合论定义, 几何实现, 矩阵表示.

图的同构; 权图.

2.1.2图的连通性

对无向图的端vi来说，与该端关联的边数定义为该端的度数：，记为：d(vi)。对有向图：d+(vi)表示离开vi的边数，d-(vi)表示进入vi的边数

对图G=(V，E)，若|V|=n，|E|=m，则有如下基本性质： 1）若G是无向图

d(v)2m(2E)

ii1nn 2）若G是有向图

di1 (vi)d(vi)m　　　i1n下面定义图的边序列，链，道路，环和圈：

相邻二边有公共端的边的串序排列（有限） (v1，v2)， (v2，v3)， (v3，v4)， (vi，vj)，称为边序列。边序列中，无重边的，成为链(link)；若边序列中没有重复端，称为道路(path)；若链的起点与终点重合，称之为环(ring)； 若道路的起点与终点重合,称之为圈(cycle)。

任何二端间至少存在一条径的图，为连通图。否则，就是非连通图。对非连通图来说，它被分为几个最大连通子图，即几个“部分”。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素，则此图成为非连通图，如下例:

GACB

G=ABC=A+B+C

对于图的连通, 可以通过下面的方法给予准确的描述:

对于图G中的任意两个端点u和v, 如果存在一条从u到v的链, 称u和v有关系, 容易知道这是一个等价关系; 从而可以将图G做一个等价分类, 每一个等价分类就是一个连通分支.连通分支只有一个的图为连通图.

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

下面举一些图的例子:

(1)完全图Kn：任何二端间有且只有一条边（即直通路由），称为完全图， 其边、端数之间存在固定关系:

nn(n1) m 22 下面是一个n=5的完全图

(2)正则图：所有端度数都相同的连通图为正则图 d(vi)=常数（i=1，2，n） 正则图是连通性最均匀的图

非正则d(v)=3

(3)尤拉图(Euler): 端度数均为偶数的连通图为尤拉图。

d(v)=2Euler图

尤拉图的性质: 尤拉图存在一个含所有的边且每边仅含一次的环. (4) 两部图

两部图的端点集合分为两个部分, 所有边的端点分别在这两个集合中. 完全两部图Km,n (5)

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

2.1.3树:

树是图论中一个很简单，但是又很重要的概念，在图论中运用是十分重要的。 图的定义有多种, 如下面的定义：

1、任何二端有径且只有一条径的图称为树。 2、无圈的连通图称为树.

我们采用第2种关于图的定义方式, 也就是: 树: 无圈的连通图称为树. 树有以下性质:

1.树是最小连通图，树中去一边则成为非连通图。

2.树中一定无环。任何二端有径的图是连通图，而只有一条径就不能有环。 3.树的边数m和端数n满足m=n-1 此式可以用数学归纳法证明。

4.除单点树，至少有两个度数为1的端(悬挂点) 树上的边称为树枝 (branch)

定理2.1：给定一个图T，若p=|V|，q=|E|，则下面论断等价： （1）T是树；

（2）T无圈，且q=p-1； （3）T连通，且q=p-1； 证明：

1）2），显然；

2）3），反证：若T不连通，它有k个连通分支（k大于等于2），每个都为树，若第i个树有pi个点，则q(pi1)pkp2，与q = p-1相矛盾；

i1k3）1），p=1时，显然。设p2，T连通，且q=p-1，首先易证T有悬挂点，

1p1p不然，qdi2p，与q = p-1相矛盾；然后对点数进行归纳即可；

2i12i1

定理2.2：若T是树，则：

（1）T是连通图，去掉任何一条边，图便分成两个且仅仅两个分图； （2）T是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。 同时，若无向图满足（1）和（2），则T是树。

定理2.3：设T是树，则任何两点之间恰好有一条道路；反之，如图T中任何两点之间恰好有一条道路，则T为树。

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

定理2.2和2.3刻画了树的两个重要特征，事实上定理2.3也为图提供了另一个等价定义。上述两个定理的证明请读者自行完成。

支撑树(Spanning Tree)：

考虑树T是连通图G的子图，TG，且T包含G的所有端，称T是G的支撑树。

由定义可知，只有连通图才有支撑树；反之有支撑树的图必为连通图。一般支撑树不止一个， 连通图至少有一个支撑树。支撑树上任二端间添加一条树支以外的边，则形成环(circuit)。支撑树外任一边称支撑树的连枝，连枝的边集称为连枝集或树补(Cotree)。不同支撑树对应不同连枝集。

对非连通图来说，它可以分成K个最大连通子图，即K个“部分”，每部分各有支撑树。K个支撑树的集合形成图G的主林，其余的边为林补。主林的边数称为图的阶，用表示。主林的连枝数称为空度，用表示。有如下关系式： n=n1+n2++nk

=( n1-1)+ ( n2-1)+ + ( nk-1)=n-k =m-n+k 例如：

n=11m=12G k=3； =11-3=8； =12-11+3=4

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

2.1.4割(cut)

割指的是某些子集(端集或边集)。对连通图，去掉此类子集，变为不连通。对非连通图，去掉此类子集，其部分数增加。 割分为割端集与割边集。 1、割端与端集

设V是图G的一个端，去掉V和其关联边后，G的部分数增加，则称V是图G的割端。去掉几个端后，G的部分数增加，这些端的集合称为割端集。有的连通图无割端，这种图称为不可分图。

对于连通图, 在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集，其任意真子集不为割集。

最小割端集的端数目，称为图的联结度。联结度越大，图的连通性愈不易被破坏。

2、割边集与割集

连通图G的边子集S，去掉S使G为不连通，称S为割边集

在众多的割集中边数最少的割集，称为最小割边集。最小割边集的任一真子集不为割边集。最小割集的边数，称为结合度. 结合度同样表示图的连通程度，结合度越高，连通程度越好。

3、基本割集与基本环（针对连通图讨论） 1）基本割集

设T为连通图G的一个支撑树，取支撑树的一边（枝）与某些连枝，定可构成一个极小边割集，此割集称为基本割集。即：基本割集是含支撑树T之一个树枝的割集。基本割集有n-1个.

下面一个图来理解基本割集.

e1e5e2e6e3 支撑树T={e1e4

e6e3e4} 连枝：e2，e5

则基本割集：（e1，e5）， (e6，e2，e5)，(e3，e2)， (e4，e5) 2）基本环

T为连通图G的一个支撑树，G-T的边集为连枝集。取一连枝可与某些树枝构成环。这种包含唯一连枝的环称基本环。

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

每个基本环只包含一个连枝---与连枝一一对应，其数目=连枝数，共m-n+1个。

环和运算: 对于集合, 这个运算的意义为对称差运算.

通过环和运算, 由基本割集和基本环可以生成新的环和割集或它们的并集,事实上可以生成所有的环和割集.

例2.2 通过基本环和基本割集理解基尔霍夫定律.

下面的图理解基本环.

e2e6e1e5e8e3e4e9e7

连枝集 (e6，e7，e8，e9) e6：c1{e6，e1，e3，e2} e7：c2{e7，e3，e4} e8：c3 e9：c4

{e8，e3，e2}

{e9，e4，e5}

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

2.1.5 图的平面性

图G若可以在一个平面上实现，除端点以外，任何两条边均无其他交点，则称G是平面图。当平面图有一个平面实现后，它把全平面分成s个区域（含包含无穷远点的开区域）。注意一个图为平面图等效于能够在球面上有一个几何实现.

设连通平面图有m边，n端，则s=m-n+2，此为著名的Euler公式。这个性质可以用数学归纳法证明或树的性质证明。

m=4，n=4，s=2

定理2.4：简单连通图为平面图的必要条件是:

m<=3n-6 (n>=3)

上述结论可以推广到有重边和自环的情形.

有重边有自环

证：形成区域至少3边，区域周线上的边数至少3s(不考虑区域共边)，实际每边均在二区域周线上，最多有2m边（周线上）。考虑区域共边，有2m3s，代入Euler公式得m3n-6.

此为平面图的必要，非充分条件。

例2.3 讨论完全图K5和完全两部图K3,3的平面性.

定理2.5连通两部图为平面图的必要条件是:

m+4 <= 2n (n>=3)

根据每个平面图G=（V，E），可以生成一个对偶图G'。G的每个平面对应于G'的每个顶点，G中相邻的两个面在G'中有一些边与G中的两个面的每一条边界的边相交，如下图所示。但是简单平面图的对偶图可能不再是简单图。

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

定理2.6 图G为平面图当且仅当 G不含K5和K3,3或它们的细分图为子图.

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

2.1.6图的矩阵表示

很多时候，需要将图表示在计算机中，这就有了图的矩阵表示。下面主要介绍关联阵和邻接阵。

1．关联阵

设图G有n个端，m条边，则全关联阵 A0[aij]nm；

端vi对应于矩阵的第 I行(共n行)；边ej对应于第j 列(共m列);

其中:

a1,若ej与vi关联 在无向图中ij

aij0,若ej与vi不关联aij1,ej与vi关联,离开vi 在有向图中aij1,ej与vi关联,指向vi

a0,e与v不关联jiij

下面是一个例子说明关联矩阵, 例2.4

v11v1A02v30v40v100111000

11010110e1v2e4v4e5e2e3v3

由A0可以看出:

(1)第i行非零元个数等于端vi度数, 每列有两个1; (2)若第i行均为0元素，则vi为孤立端， G为非连通图; (3)若i行只有一个非O元，则vi为悬挂端;

(4)如果将A0中每一个列中的任一个1改为-1, 则n行之和0向量，所以最多只有n-1行线性无关，A0秩最大为n-1。

将无向图全关联阵A0 中每一个列中的任一个1改为-1， 再去掉任一行，得到关联阵A，为n-1m阶。A中的每一个非奇异方阵对应一个支撑树。图G的支撑树数目可由以下方法得到：

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

定理2.7(矩阵-树定理)

用AT表示A的转置, 无向图G的主树数目

(G) = det(AAT)，

注意上面的定理计算的主树数目为标号树的数目; 同时n-1阶矩阵det(AAT)可以直接写出, 主对角线的元素为相应端点的度数, 其余位置为-1或0, 而这取决于相应的端点之间是否有边. 例2.5 (Kn) = n(Kn) = nn2n2, (Kn,m) = mn-1nm-1.

的计算如下：

...1...... .........n1(n1)(n1)n11 AAT1n111111 1...1

0...0n...0 .........0...n nn2

继续例2.4:

v1v2v3v4210131=8012v13111v21210v31131v41012

共有8种支撑树如下

2.邻接阵

邻接阵是表征图的端与端关系的矩阵，其行和列都与端相对应。 令G=（V，E）是m端，n边的有向图，其邻接阵 C[Cij]nn

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

1,若vi到vj有边其中，Cij

0,若vi到vj无边00 如： C00011000010

101100000010对于无向图CijCji ，因此是邻接阵为对称阵。

我们可以通过对C的一些计算，得到图G的性质。如：计算C的幂次可得到关于转接径长的一些信息。

若Cij(2)=1则存在k，使Cik Ckj =1，即Cik= Ckj=1，i，j之间至少有径，径长为2；若Cij(2)=a，则vivj间有a条径长为2的径，若Cij(2)=0，则vivj间无径长为2的径；所以， Cij(2)即为vivj间径长为2即转接一次的径数。

C(3)ck1nikckj(2)ck1s1nnikckscsj

同理，若Cij(3)=1， 则有vivkvsvj，径长为3，即经过二次转接。 由此可得下面结论:邻接阵幂C之元素表示了二端间转接次数不超过b-1的 径，但是经过转接的端可能重复。

已知图G的邻接阵C, 需要解决图G是否连通的问题? 当然通过计算邻接阵C和C的幂可以解决这个问题,考虑下面的小算法, 它解决同样的问题, 但效率很高.

Warshall 1962

(1)置新矩阵 P:= C; (2)置 i = 1;

(3)对所有的j, 如果P(j,i)=1, 则对k=1,2,…,n P(j,k):= P(j,k) P(i,k); (4) i = i+1;

(5)如n  i转向步骤(3), 否则停止.

本节介绍了图论的简要知识，[1]和[2]介绍了很好的基础知识。[4]介绍了网络优化算法的详尽的和较新的进展。本节内容同时也借鉴[3]的一些结果。某些图论知识在以后应用是会在介绍。

b最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

§2.2 最短径问题

上节中介绍的图只考虑了图顶点之间的关联性，本节将要对图的边和端

赋予权值，讨论有权图。权值在各种各样实际问题中有不同的实际意义，如费用，几何距离，容量等等。本节将介绍一些算法，大部分算法可借助计算机实现。

§2.2.1 最短支撑树

给定连通图G=(V，E)，W(e)是定义在E上的非负函数，称W(e)为e的权。T=(V，ET)为G的一个支撑树。定义树T的权为W(T)eETW(e)。最短支撑

树问题就是求支撑树T，使W(T)最小。下面介绍求最短支撑树的方法。

1) 无条件的情况

Prim在1957年提出一个方法，简称P算法。

图G有n端，端间“距离”dij(i，j=1，2，3，….n)已给定(若无边则dij=)， 找一个支撑树，使其n-1个边（树枝）的权和最小，步骤如下： P0:任取一端v1，子图G1={v1}，在G1到G-G1中取最小的dij

vj(GG1)viG1Min(dij)d12*

得子图G2={ v1， v2} P1:求G3

viG2vj(GG2)*Min(dij)di3

得子图G3={ v1，v2，v3} …

Pr-2:从Gr-1求Gr

viGr1vj(GGr1)Min*(dij)dir

得子图Gr={ v1，v2，…，vr} Pr-1:重复Pr-2，直至得到Gn为止 例2.5:

v23v124v44v313562v6v5v7 G1={v1} G2={v1，v3}

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

G3={v1，v3，v6} G4={v1，v3，v6，v7} G5={v1，v3，v6，v7，v2} G6={v1，v3，v6，v7，v2，v5} G7={v1，v3，v6，v7，v2，v5，v4} 则W(T)=15

可以看出， Prim算法第K步运算，是以Gk作为整体寻找至G-Gk的最短边，每次并入Gk的边总是保持余下m-k+1个中最短的，因此算法终止时，所得的支撑树为最短者(可用数学归纳法证明)。

从算法始至终止，共进行n-1步，每步从k个端与n-k个端比较，须经k(n-k)-1次，可得总计算量

[k(nk1](n1)(n2)(n3)

k1n116约为n3量级。当n很大时，可借助计算机实现。

另一个算法由Kruskal在1956年提出:

设G(k)是G的无圈支撑子图,开始G(0)=(V,)。若G(k)是连通的,则它是最小支撑树；若G(k)不连通,取e(k)为这样的一边,它的两个端点分属G(k)的两个不同连通分图,并且权最小。令G(k+1)= G(k)+ e(k),重复上述过程。

上面算法的实现过程需要排序算法； Rosenstiehl和管梅谷提出了另一个算法：

设G(k)是G的连通支撑子图，开始G(0)=G，若G(k)中不含圈，则它是最小支撑树；若G(k)中包含圈，设是G(k)中的一个圈，取上的一条权最大的边e(k)，令G(k+1)= G(k)-e(k)，重复上述过程。

上面算法的实现过程需要解决如小问题： 对于一个无向图G, 如何寻找其中的圈? 可以通过搜索图中度为1的顶点而逐步简化.

上面算法的实施过程,都是一种贪心法原理的应用; 从局部最优的结果中寻找全局最优的结果.问题如果复杂, 这种方法一般只能找到准最优解.

2) 有情况

在许多情况下，不但要求最短支撑树，还要求一些额外条件。有两种解决此类问题的方法穷举法和调整法。穷举法就是先把图中的支撑树穷举出来，按条件逐个筛选，最后选出最短支撑树。这种方法较直观，但很烦琐。下面讨论调整法。以Esau-William算法为例(解决一种特定的问题):

问题:

图G有n个站,其中已知v1是主机，已知各边间距离dij，以及各个端站的业务量Fi（i，j=1，2，…，n），要求任端至v1的径边数K(即限转接次数

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

算法主要思想:

v3v2v4v5v1

vnvk

从上图开始(星形树),采用贪心法原则,逐步用边eij(2i,jn)替换vi

至v1的边,为此需要计算转接损失矩阵T(tij), 每次选用一条边使新树的长度减少最多,但每次要注意新树是否满足条件。实质上，每次都和上次得到的树做比较，看看能否有进展。

步骤：

EW0：起始，n个端为n个部分，邻接阵为全零阵；

EW1：计算到v1各个部分的距离D1i，和不在同一个部分内的两端之间的边的转接损失tij

D1imin(d1i)

viGiGi是包含vi的部分

tijdijD1ii,j EW2：ti*j*min(tij)

测试增加边(i*,j*)边后是否仍满足条件，若满足，在邻接阵置 ai*j*1；若不满足，则重复EW2；

EW3：考虑形成的新的部分，若部分数大于1，返回；等于1，终止； 说明：若tij0,i,j,则说明星形树已经是最好。 实例2.6(其中K=3, M=50)：

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

v2v3103304123627400v11210

计算T矩阵：

v45v5

v20121v390115 Tv44501v51530t34=-11 最小，

取边（3, 4）最替换边(3, 1)；

如此反复，最后得树为: {(3, 4), (4, 1), (2, 5), (5, 1)} 树长=12

上面的例中, 如果将边(3, 2), (2,1)和(4, 5)的权改为2, 3.5和3.5, 容易得到一个简单的反例, 存在一个树长为11的支撑树, 也满足问题中要求的条件，说明上述EW算法得到的不是全局最优解.

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

§2.2.2、端间最短径

当网络结构已定，我们需要寻找端间的最短距离和路由。分两种情况： 寻找指定端至其它端的最短径和路由，我们采用Dijkstra算法； 寻找任意二端最短径和路由, 用Floyd算法。 1)指定端至其它端最短径和路由算法:

已知 图G=(V，E)及dij ，求端vs至其它端的最短径和路由，用Dijkstra算法：

8vs2 由上图可以看出：

v14v33v21

直边不一定是最短径，如ds2，其实vs与v2间最短径长为3(经v3转接)。但可肯定，与vs相连的直边最小的一个必定为最短径(如es3)，其它转接至vs必不短。因此，算法从始找邻近端， 从vs最邻近端找起， 每次得一个最短径。

下面我们介绍Dijkstra算法，暂时不考虑端有权, 对于端有权的情况稍后处理; 首先我们会用到下列计算中的名词：

置定：某端置定即表示得到了至该端的最短径 标值：至该步时的暂时最短径，（置定端可供转接） wi为vs vi暂时的的最短径长 wj*为vs vi的置定时的最短径长

Dijkstra算法步骤：

端点集合Vp表示置定的端点集合, V- Vp为没有置定的端点集合;

D0 开始置定vs，ws*=0（vs vs），其它端暂置wj=( 如果边(s, j)存在, wj = ds,j) D1 计算未置定端vj的标值的公式

wj :=min（wj，wi +dij）, 其中viVp vjV- Vp D2 取最小值,

wj* = min wj 然后, 置定端vj*Vp ; 当所有端置定，算法结束. 不然, 返

回D1.

上面的算法没有给出取得最短径的路由, 不过对于路由可以很简单处理. 路由的给出方法可以有许多种, 如前向路由和回溯路由等. 对于Dijkstra算法, 可以给出回溯路由, 即给出最短径的前一个端点的标号, 而这个端点标号可以在算法D1的更新计算中获得; 每个端点的标号可以由两部分组成, 即距离和前一个端点标号.

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

例2.6：

vs82v14v33v2133v4 置定端 距离 路由 Vs 0 s V3 2 s V2 3 3 V4 5 3 V1 6 2 6 Vs V1 V2 V3 V4 0     8 4 2 6 8 3 5 6 5 6 D算法计算量:当有个k端已置定，需做(n-k)次加法，(n-k)次比较以更新各端的暂定值，(n-k-1)次比较求最小值，则总计算量约为

3(nk)k1n3n(n1)3O(n2) 22对于Dijkstra算法, 提出若干问题如下: 1 如果端点有权如何处理?

2 如果边的权可正可负, 算法是否仍然有效? 3 算法是否对有向图也适用？

上面Dijkstra算法中使用的为Label-setting的方法, 下面介绍一个用Label-correcting技术的方法, 效率要高许多。

不失一般性，假设是G一个有向图，用d(i)记从s至i的距离，pred(i)记路由s→i的上一个顶点(回朔路由), A(i)记录从i出发的所有边的集合。算法如下：

begin

d(s):=0 and pred(s):=0; d(j):=∞ List:={s}; while List   do begin

从 List中去掉一个元素i ; 对每个边(i, j) ∈A(i) do

if d(j)> d(i)+Cij then

begin

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

for each j∈V-{s};

……………………………………………………………最新资料推荐…………………………………………………

d(j):= d(i)+ Cij pred(j):=i；

if jList, then 将j并入List; end;

end; end;

上面的算法中没有指明List的结构, 如果将List组织为一个队列, 算法效率会更高, 计算复杂度为O(nm), 大约为目前最快的算法, 上面两个算法的解决思路的比较是很有意义的。

值得注意的是，如果附加一些条件，那么问题便很复杂了。如果边有两个权,相应的算法就复杂的多, 并且很可能无多项式算法.

2、所有端间最短径算法

Floyd算法解决了图G中任意端间的最短距离和路由，并且也采用Label-correcting 的方法。

给定图G及其边 (i, j)的权dij(i，j=1，2，3，…，n); F0：初始化距离矩阵W(0)和路由矩阵R(0) ; W(0)=[ Wij(0)] nn 其元素：

Wij(0)

同时 R(0)=[ rij(0)] nn rij(0)dij　若eijE(有边)　若eijE(无边)0　　　　若ij(不同于邻接阵)

j　若Wij(0)

,　其它0　F1：已求得W(k-1) 和R(k-1)，求W(k) 和R(k) ; wij(k)=min[wij(k-1)，wik(k-1)+ wkj(k-1)] ri,j(k)(k)(k1)(k1)ri,k　若wi,jwi,j (k1)(k)(k1)r　若wwi,ji,ji,jF2：若k上面的路由方法为前向路由，容易更改算法使它的路由为回溯路由; 算法要执行n次迭代, 第k次迭代的目的为经过端k转接是否可以使各端之间距离缩短. 从本质上讲, Floyd算法的迭代过程就是保证满足下面的定理成立.

定理2.8 对于图G, 如果w(i, j)表示端i和j之间的可实现的距离, 那么w(i, j)表示端i和j之间的最短距离当且仅当对于任意i, k, j有:

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

w(i, j)  w(i, k) +w(k, j)

Floyd算法计算量 : wij(k)=min[wij(k-1)，wik(k-1)+ wkj(k-1)]中，每定一k值，求wij经1次加，1次比较，求一次迭代为n2次加，n2次比较，共n个迭代，所以其运算量为n3级; 显然比重复使用Dijkstra算法效率高，同时存储效率也要高。 对于Floyd算法, 同样提出若干问题如下: 1 如果端点有权如何处理?

2 如果边的权可正可负, 算法是否仍然有效? 3 算法是否对有向图也适用？

例2.7 给定一个无向图G, 求任意两端之间最少转接次数和路由. 例2.8图有六个端，端点之间的有向距离矩阵如下：

v1v2v3v4v5v6v1v20910267v3v413v5v6470150272805220

1. 用D算法求V1到所有其他端的最短径长及其路径。 2. 用F算法求最短径矩阵和路由矩阵，并找到V2至

V4和V1至V5的最短径长及路由。 3. 求图的中心和中点。

解：

1. D算法 V1 V2 0 ∞ 9 9 8 8 8 V3

∞ 1 V4 ∞ 3 3 3 V5 ∞ ∞ 2 V6 ∞ ∞ ∞ 7 7 指定 V1 V3 V5 V4 V3 V2 最短径长,路由 W1＝0, 1 W13＝1, 1 W15＝2, 3 W14＝3, 1 W16＝7, 5 W12＝8, 5

2. F算法

最短路径矩阵及最短路由阵为W5，R5 v2v1v4有向距离为4 v1v3v5有向距离为2

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

09131047201W05027628057220091310247211051W15027628057162102009131610247211051W25027762805716210200913210243211051W3716502746280541327200913210102431121105112W471650274627054132720081327102438270516W5684027462705482720 3.

011R0001011R1001011R2021011R3333011R4333011R5533505525201321200020201021201021310333330333310333310333411033400044411041411041335505055505055505255505000660000660000660201321310533310333411033411033335505335505000660444660555660

MaxWij5(8,8,7,8,7,8)

j中心为V3或V5

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

Wj5ij(21,18,21,27,24,23) 中点为V2

在实际问题中，除了求最短径外，如当主路由（最短径）上业务量溢出或故障时，需寻求次短径或可用径。次短径指备用径，可用径指一批满足某种条件的径（如限径长，限转接次数….）。但这些问题一般没有多项式算法, 可以根据实际情况采用某种贪心策略获得近似解.

3、网的中心与中点

如网络用图G=(V, E)表示, 根据Floyd算法的计算结果可以定义网络的中心和中点.

中心:

对每个端点i, 先求max(wi(,nj))

j此值最小的端称为网的中心，即满足下式的端i*：

n)(n) max(wi(*,=)min[max(wji,j)]

jij网的中心宜做维修中心和服务中心。 中点:

将“平均最短径长”最小的端，定义为中点，

先计算 si = [wi(,nj)], 然后求出si的最小值, 相应的端点为中点.

j 网的中点可用做全网的交换中心。

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

§2.3网络流量问题

网络的目的是把一定的业务流从源端送到宿端。流量分配的优劣将直接关系到网络的使用效率和相应的经济效益。网络的流量分配受限于网络的拓扑结构，边和端的容量以及路由规划。本节及下节中关于流量的内容均在有向图上考虑，并且均是单商品流问题，即网络中需要输出的只有一种商品或业务。通信网络的服务对象有随机性的特点, 关于通信业务随机性特点将在下一章中考虑, 本节中假设网络源和宿的流量为常量.

§2.3.1基本概念

给定一个有向图G=（V，E），C(e)是定义在E上一个非负函数，称为容量；对边eij，边容量为Cij ，表示每条边能通过的最大流量。设f={ fij }是上述网络的一个流，若能满足下述二条件，称为可行流。 a)非负有界性：0≤fij≤Cij； b)连续性: 对端vi有：

FfijfjiFvj'(vi)0vi为源端vi为宿端 其他vj(vi) v(f) = F为源宿间流{fij}的总流量.

式中 Γ（vi）={vj: ( vi， vj)∈E} 流出vi的边的末端集合; Γˊ(vi)={vj: ( vj， vi)∈E} 流入vi的边的始端集合;

有n个连续性条件，共有2m+n个条件，满足上述二条件的流称为可行流。

需要解决的问题分为两类: 1 最大流问题

在确定流的源和宿的情况下, 求一个可行流f, 使v(f) = F为最大; 2 最小费用流问题

如果边(i,j)的单位流费用为di,j , 流f的费用为: (i,j)Edfi,ji,j

所谓最小费用流问题:

在确定流的源和宿的情况下, 求一个可行流f, 使φ为最小.

下面介绍割量和可增流路的概念.

设X是V的真子集，且vs∈X，vt∈Xc，（X，Xc）表示起点和终点分别在X和Xc的边集合，这个集合当然为一个割集,割集的正方向为从vs到vt。 割量定义为这个割集中边容量的和:

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

C(X,Xc)对可行流{fij}:

viX,vjXcCij

f(X，Xc)表示前向边的流量（和）∑fij, 其中vi∈X，vj∈Xc f(Xc，X)表示反向边的流量 (和) ∑fji, 其中vi∈X，vj∈Xc 则源为vs宿为vt的任意流f有:

(1) v(f)=f(X,Xc)-f(Xc,X), 其中vs∈X，vt∈Xc 证明：

对任vi∈X :

F fijfjivjVvjV0vivsvivs

对所有vi∈X,求和上式：

viXvjVfijviXvjVfjiviXvjXcfijviXvjXcfji

f(X,Xc)f(Xc,X)Fv(f)vsv1v2v3v4v5vt

viXvjXcfij

viXcvjXfij

源端 s: fs1+fs2+fs3 中转端 1: f14 -(fs1+f21) 中转端 2: f21+f23 -(fs2) 中转端 3: f3t -(fs3+f23+f53)

viXvjXf-fijcij

viXvjXc= f14+f3t-f53= f(X,Xc)-f(Xc,X)=F (2) F≤C(X,Xc)

由（1）及f(X, Xc)非负，可得：

Ff(X,Xc)f(Xc,X)f(X,Xc)C(X,Xc)

下面讨论可增流路的概念。

从端s到端t的一个路，有一个自然的正方向，然后将路上的边分为两类：

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

前向边集合和反向边集合。对于某条流，若在某条路中，前向边均不饱和（fij若流{ fi,j }已达最大流，f则从源至宿端的每条路都不可能是可增流路，即每条路至少含一个饱和的前向边或流量为0的反向边。

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

§2.3.2 最大流问题

所谓最大流问题，在确定流的源端和宿端的情况下, 求一个可行流f, 使v(f) 为最大。对于一个网络，求最大流的方法采用可增流路的方法，下面的定理2.9为这种方法提供了保证.

如果网络为图G = (V, E),源端为vs, 宿端为vt. 定理2.9 (最大流-最小割定理)可行流f* = {在从vs 到vt的可增流路. 证明:

必要性: 设f*为最大流,如果G中存在关于f*的从vs 到vt的可增流路μ.

*令 0 <θ= min[min(Ci,jfi*,)(f,jmini,j)] ,θ是存在的.

(i,j)(i,j)f*i,j}为最大流当且仅当G中不存

构造一个新流f如下:

如果 (i,j), fi,jfi*,j 如果 (i,j), fi,jfi*,j

如果 (i,j), fi,jfi*,j,不难验证新流f为一个可行流,而且v(f)=v(

f*i,j)+θ,矛盾.

*

充分性: 设f为可行流, G中不存在关于这个流的可增流路. 令X* = {v|G中存在从vs到v的可增流路},从而vs X*, vt X*. 对于任意边 (i,j)(X*,X*c),有fi*,jci,j 对于任意边 (i,j)(X*c,X*),有fi*,j0

这样, v(f*)c(X*,X*c),那么流f*为最大流，(X*,X*c)为最小割。证毕。 网络处于最大流的情况下，每个割集的前向流量减反向流量均等于最大流量且总存在一个割集(X*,X*c)，其每条正向边都是饱和的，反向边都是零流量；其割量在诸割中达最小值，并等于最大流量。

推论：如果所有边的容量为整数，则必定存在整数最大流。

求最大流的基本思想是：在一个可行流的基础上，找vs→vt 的可增流路，然后在此路上增流，直至无可增流路时，停止。

具体方法(M算法)：从任一可行流开始，通常以零流{fi,j=0}开始。 （1）标志过程：从vs 开始给邻端加标志,加上标志的端称已标端; （2）选查过程：从vs 开始选查已标未查端

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

查某端，即标其可能增流的邻端; 所有邻端已标，则该端已查。

标志宿端，则找出一条可增流路到宿端，进入增流过程。 （3）增流过程：在已找到的可增流路上增流。 步骤：

M0：初始令fi,j=0

M1：标源端vs ：（+，s，∞）

M2：从vs 始，查已标为查端vi ，即标vi 的满足下列条件的邻端vj ， 若（vi ,vj ）∈E，且ci,j > fi,j ， 则标vj 为: (+，i，εj) 其中εj =min(ci,j-fi,j ，εi ) εi 为vi 已标值。

若（vj ,vi ）∈E，且 fj,i >0， 则标vj 为: (-，i，εj)， 其中εj =min（εi ，fj,i ）其它端vj 不标。 所有能加标的邻端vj 已标，则称vi已查。 倘若所有端已查且宿端未标，则算法终止。 M3：若宿端vi 已标，则沿该可增流路增流。 M4: 返回M1。

上面的算法是针对有向图且端无的情况。若是有无向边，端容量及多源多宿的情况，可以进行一些变换，化为上述标准情形。

若端i和端j之间为无向边，容量为Ci,j，那么将它们化为一对单向边 (i，j)和(j，i)，并且它们的容量均为Ci,j。

如果端i有转接容量Ci，那么将Vi 化为一对顶点Vi',Vi''，原终结于Vi的边全部终结于Vi'，原起始于Vi的边均起始于Vi''，且从Vi'至Vi''有一条边容量为Ci。

对多源多宿的情况，设原有源为Vs1,Vs2,...,Vsl，原有宿为Vt1,Vt2,...,Vtk，要求从源集到宿集的最大流量，可以虚拟一个新的源Vs和新的宿Vt，源Vs到

Vs1,Vs2,...,Vsl的各边容量均为无限大，Vt1,Vt2,...,Vtk到宿Vt的各边容量也为无

限大，这样多源多宿的问题就化为从Vs到Vt的最大流问题。见下图：

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

vs1vs

vs2vt2vt1vt

仔细考虑一下会发现，前面介绍的算法在任何网络中是否一定会收敛，也就是说会不会不断有增流路，但却不收敛于最大流呢？如果边的容量均为有理数，是不会出现这种情况，也就是说一定会收敛。但若边的容量为无理数，就不一定收敛。对于计算量的问题, Ford和Fulkerson曾给出下面的例子。

如图所示，一个四个节点的网络，求vs至vt的最大流量。假设按前述算法，并且按如下顺序从f=0开始增流： 例2.8

2nvs2np1q2n2nvt

vsqpvt增流1； vspqvt增流1;

显然，这样需要2n+1步增流才能找到vsvt的最大流，流量为2n+1。这个例子说明前述算法虽然能够达到最大流，但是由于没有指明增流方向，导致有可能象这个例子一样，效率很低，这个例的计算工作量与边容量有关。1972年，Edmonds和Karp 修改了上述算法, 在M2步骤时采用FIFO原则(在选哪个端查时), 从而解决了这个问题；新算法一方面收敛, 同时也为多项式算法. 后来，人们提出了许多改进的算法，如Dinits 算法和MPM算法，其主要思想是赋予网络一些新的结构可以使算法更有效率等等。有兴趣者可参阅[2]。

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

§2.3.3最小费用流问题

如果网络为图G = (V, E),源端为vs, 宿端为vt.边(i,j)的单位流费用为di,j 流f的费用为: (i,j)Edfi,ji,j

所谓最小费用流问题:

在确定流的源和宿的情况下, 求一个可行流f, 使φ为最小. 最小费用流问题是线性规划问题，但也可用图论方法求解, 效率更高。对于它的存在性可以这样理解，流量为F的可行流一般不是唯一的，这些不同的流的费用一般也不一样, 有一个流的费用最小.

寻找最小费用流，用负价环法(Klein, 1967) , 所谓负价环的意义如下: 负价环为有向环,同时环上费用的和为负。负价环算法的具体步骤如下： K0：在图 G上找任意流量为F的可行流f; K1：做流f的补图; 做补图的方法如下:

对于所有的边ei,j, 如果ci,jfi,j, 构造边ei1,j,

容量为:ci,jfi,j, 单位流费用为: di,j;

对于所有的边ei,j, 如果fi,j0, 构造边ei2,j,

容量为:fi,j, 单位流费用为: -di,j;

K2：在补图上找负价环C。若无负价环，算法终止。 K3：在负价环C上沿环方向使各边增流 增流数：

min(ci*,j)

(i,j)C K4： 修改原图的每边的流量，得新可行流。 K5： 返回k1。

例2.9：已知ci,j，di,j，要求F=9。求最小费用流。

6,1vs4,14,56,34,63,14,66,31,76,3vtvs63235vt最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

上面可行流安排总费用为: φ=102. 下面做补图, 寻找负价环, 调整可行流.

6,-36,-1vs1,53,-51,74,13,14,31,,-62,-31,35,-3vs63535=963,-6min(3,3,4)3C

6,-36,-1vs1,53,-51,74,13,-11,34,,-65,-35,-3此图已无负价环1,3零价环

零价环上增流: 得另一最小费用流

6vs3

66原4X6=24现3X6=18336原5X3=15现6X3=18

原5X3=15现6X3=18 24+15+15= 18+18+18=

前面负价环的算法中, 如何寻找负价环? 这个问题可以应用Floyd算法解决. 最小费用流问题是网络流问题中比较综合的问题，和线性规划问题的关系非常密切, 对于它的研究仍将继续进行。

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23

……………………………………………………………最新资料推荐…………………………………………………

参考文献：

1.Bondy,J.A.and U.S.R.Murtly, Graph theory with applications,The Macmillan Press Ltd,1976

2.图与网络流理论，田丰，马仲蕃，科学出版社，1987 3.通信网理论基础，周炯磐，人民邮电出版社，1991 4.RAVINDRA K.AHUJA THOMAS L. MAGNANTI NETWORK FLOWS. Prentice hall 1993

5.ORLIN,J.B.1988 A faster strongly polynomical minimum cost flow algorithm Procedings of the coth ACM Symposium on the Theory of Computing PP377-387 6.线性规划最新进展，马仲蕃，科学出版社，1994 7.《运筹学》，清华大学出版社，1990.1

JAMES B.ORLIN

最新精品资料整理推荐，更新于二〇二一年一月二十二日2021年1月22日星期五19:23:23