第二章 通信网的拓扑结构

第二章 通信网拓扑结构

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

§2.1图论基础

图论是应用数学的一个分支，本节介绍它的一些概念和结论。其基本内

容可参见（1）和（2）。

2.1.1图的定义

例2.1 哥尼斯堡7桥问题;

所谓一个图，是指给了一个集合V ，以及V 中元素的序对集合E ，V 和

E 中的元素分别称为图的端点和边。

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

R 设有集合V 和E ，V={v1，v 2，……，v n }， E={e1，e 2，…… em } ，且V ⨯V −−→E

则V 和E 组成图G ，称V 为端集，E 为边集。

下面给出图的一些概念:

当e ij =(vi ，v j ) ，称边e ij 和端v i 与v j 关联；

当v i Rv j 不等价于v j Rv i 时，为有向图；

当v i Rv j 等价于v j Rv i (eij =eji ) 时，为无向图；

当V=φ(此时E 必为空集) ，为空图；

自环，孤立点图，重边；

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

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

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

图的运算:

G1⋃G2, G1⋂G2, Gc 等

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

图的同构; 权图.

2.1.2图的连通性

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

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

n

1）若G 是无向图 ∑d (v

i =1

n i ) =2m (=2E ) 2）若G 是有向图 n

+∑d

i =1(v i ) =∑d i =1- (v i ) =m 　　　

下面定义图的边序列，链，道路，环和圈：

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

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

G=A⋃B ⋃C=A+B+C

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

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

下面举一些图的例子:

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

m =⎛ n ⎫n (n -1)

2⎪⎪=

⎝⎭2

下面是一个n=5的完全图

(2)正则图：所有端度数都相同的连通图为正则图

d(vi )=常数（i=1，2，⋯n ）

正则图是连通性最均匀的图

d (v ) =

2非正

则d (v ) =3

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

E u l e r 图

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

(4) 两部图

两部图的端点集合分为两个部分, 所有边的端点分别在这两个集合中.

完全两部图Km,n

(5)

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），每个都为

k

树，若第i 个树有p i 个点，则q =∑(p

i =1i -1) =p -k ≤p -2，与q = p-1相矛盾；

3）→1），p=1时，显然。设p ≥2，T 连通，且q=p-1，首先易证T 有悬挂点，不然，q =

定理2.2：若T 是树，则：

（1）T 是连通图，去掉任何一条边，图便分成两个且仅仅两个分图；

（2）T 是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。

同时，若无向图满足（1）和（2），则T 是树。

定理2.3：设T 是树，则任何两点之间恰好有一条道路；反之，如图T 中任何两点1p i d ∑2i =1≥1p 2=p ，与q = p-1相矛盾；然后对点数进行归纳即可； ∑2i =1

之间恰好有一条道路，则T 为树。

定理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 =11

m =12

k=3； ρ=11-3=8； μ=12-11+3=4

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个.

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

43

支撑树T={e 1e 6e 3e 4} 连枝：e 2，e 5

则基本割集：（e 1，e 5）， (e 6，e 2，e 5) ，(e 3，e 2) ， (e 4，e 5)

2）基本环

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

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

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

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

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

下面的图理解基本环.

e

连枝集 (e 6，e 7，e 8，e 9)

e 6：c 1={e 6，e 1，e 3，e 2}

e 7：c 2={e 7，e 3，e 4}

e 8：c 3={e 8，e 3，e 2}

e 9：c 4={e 9，e 4，e 5}

2.1.5 图的平面性

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

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

m=4，n=4，s=2

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

m=3)

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

.

重边

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

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

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

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

m+4 =3)

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

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

2.1.6图的矩阵表示

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

1．关联阵

设图G 有n 个端，m 条边，则全关联阵 A 0=[a ij ]n ⨯m ；

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

其中:

⎧a ij =1, 若e j 与v i 关联⎨

⎩a ij =0, 若e j 与v i 不关联 在无向图中

⎧a ij =+1, e j 与v i 关联, 离开v i 在有向图中⎪⎨a ij =-1, e j 与v i 关联, 指向v i

⎪a =0, e 与v 不关联j i ⎩ij

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

例2.4

⎡v 1⎤⎡1

⎢⎥⎢v 21⎢⎥⎢A 0=⎢v 3⎥⎢0⎢⎥⎢⎣v 4⎦⎣0

v 10110e 1001110011⎤⎥0⎥

1⎥⎥0⎦v 2

e 4e 2

v 4e 33

由A 0可以看出:

(1)第i 行非零元个数等于端v i 度数, 每列有两个1;

(2)若第i 行均为0元素，则v i 为孤立端， G为非连通图;

(3)若i 行只有一个非O 元，则v i 为悬挂端;

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

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

定理2.7(矩阵-树定理)

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

τ(G) = det(AAT ) ，

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

n ) = n

, τ(Kn-1m-1

n,m ) = mn .

τ(K-2

n ) = n

n 的计算如下：

⎡n -1-1... -1⎤

⎢AA

T

=⎢-1n -1... ...

⎥⎥

⎢-1-1... ... ⎥

⎢⎣-1

-1

...

n -1⎥

⎦(n -1) ⨯(n -1)

⎡10... 0⎤

⎢

=⎢1

n ... 0⎥⎥ ⎢... ... ... ... ⎥⎢⎣10

...

n ⎥⎦

=n n -2

继续例2.4:

v 1v 2v 3v 4v 1⎡3-1-1-1⎤v ⎢2⎢-12-10⎥⎥2-10v 3⎢-1-13-1⎥-13-1=8 v ⎢4⎣-1

-1

2⎥⎦

-1

2

共有8种支撑树如下

2. 邻接阵

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

=[C ij ]n ⨯n

其中，C ij =⎨

⎧1, 若v i 到v j 有边⎩0, 若v i 到v j 无边

10100

10000

01101

0⎤⎥0⎥1⎥⎥0⎥0⎥⎦

⎡0

⎢0⎢

如： C =⎢0

⎢0⎢⎢⎣0

对于无向图C ij =C ji ，因此是邻接阵为对称阵。

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

若C ij (2)=1则存在k ，使C ik ⋅ Ckj =1，即C ik = Ckj =1，i ，j 之间至少有径，径长为2；若C ij =a，则v i →v j 间有a 条径长为2的径，若C ij =0，则v i →v j 间无径长为2的径；所以， Cij (2)即为v i →v j 间径长为2即转接一次的径数。

n

(2)(2)

C

(3)

=

∑

k =1

c ik ⋅c kj

(2)

n n

=

∑∑

k =1s =1

c ik ⋅c ks ⋅c sj

同理，若C ij (3)=1， 则有v i →v k →v s →v j ，径长为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

§2. 2 最短径问题

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

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

§2.2.1 最短支撑树

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

∑W (e ) 。最短支撑

e ∈E T

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

1) 无限制条件的情况

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

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

v j ∈(G -G 1)

v i ∈G 1

Min

(d ij ) ≡d 12

*

得子图G 2={ v1， v2} P 1:求G 3

v i ∈G 2

v j ∈(G -G 2)

Min

(d ij ) ≡d i 3

*

得子图G 3={ v1，v 2，v 3} …

Pr-2:从G r-1求G r

v i ∈G r -1

v j ∈(G -G r -1)

Min

(d ij ) ≡d ir

*

得子图G r ={ v1，v 2，…，v r } Pr-1:重复P r-2，直至得到G n 为止 例2.5:

v v 1

4

5v 7

G 1={v1} G 2={v1，v 3}

G 3={v1，v 3，v 6} G 4={v1，v 3，v 6，v 7} G 5={v1，v 3，v 6，v 7，v 2} G 6={v1，v 3，v 6，v 7，v 2，v 5} G 7={v1，v 3，v 6，v 7，v 2，v 5，v 4} 则W(T)=15

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

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

k =1n -1

-1]=

16

(n -1)(n -2)(n -3)

约为n 3量级。当n 很大时，可借助计算机实现。

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

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

(k+1)

= G+ e, 重复上述过程。

(k)(k)

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

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

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

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

2) 有限制情况

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

问题:

图G 有n 个站, 其中已知v 1是主机，已知各边间距离d ij ，以及各个端站

(k)

(0)

(k)

的业务量F i （i ，j=1，2，…，n ），要求任端至v 1的径边数

算法主要思想:

从上图开始(星形树), 采用贪心法原则, 逐步用边e ij (2≤i , j ≤n ) 替换v i

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

步骤：

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

EW 1：计算到v 1各个部分的距离D 1i ，和不在同一个部分内的两端之间的边的转接损失t ij

D 1i =min (d 1i )

G v v i 是包含i 的部分

i ∈G i

t ij =d ij -D

1i

EW2：t i *j *=min (t i , j

ij )

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

EW3：考虑形成的新的部分，若部分数大于1，返回；等于1，终止； 说明：若t ij >0, ∀i , j , 则说明星形树已经是最好。

实例2.6(其中K=3, M=50)：

v v v 1

计算T 矩阵：

v 2⎡0⎢v 3-9⎢T =

v 4⎢-4⎢v 5⎣1

-10-55

-2-1103

4

5

-1⎤⎥-5⎥ -1⎥⎥0⎦

t 34=-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 算法得到的不是全局最优解.

§2.2.2、端间最短径

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

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

v v 2

由上图可以看出：

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

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

置定：某端置定即表示得到了至该端的最短径 标值：至该步时的暂时最短径，（置定端可供转接） w i 为v s →v i 暂时的的最短径长 w j*为v s →v i 的置定时的最短径长

Dijkstra 算法步骤：

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

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

w j :=min（w j ，w i +dij ）, 其中v i ∈V p v j ∈V- Vp D2 取最小值,

w j* = min wj 然后, 置定端v j*∈V p ; 当所有端置定，算法结束. 不然, 返

回D1.

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

例2.6：

v 2

v 4

D 算法计算量:当有个k 端已置定，需做(n-k)次加法，(n-k)次比较以更新各端的暂定值，(n-k-1)次比较求最小值，则总计算量约为

n

∑3(n -k ) =

k =1

3n (n -1)

2

→O (

32

n )

2

对于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

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)的权d ij (i，j=1，2，3，…，n); F0：初始化距离矩阵W (0)和路由矩阵R (0) ; W (0)=[ Wij (0)] n ⨯n 其元素：

W ij

(0)

同时 R (0)=[ rij (0)] n ⨯n

r ij

(0)

⎧d ij 　若e ij ∈E (有边) ⎪

=⎨∞　若e ij ∉E (无边) ⎪0　　　　若i =j ⎩

(不同于邻接阵)

⎧j 　若W ij (0) ≠∞=⎨

0　, 　其它⎩

F1：已求得W (k-1) 和R (k-1)，求W (k) 和R (k) ; w ij (k)=min[wij (k-1)，w ik (k-1)+ wkj (k-1)]

r i , j

(k )

(k ) (k -1) (k -1)

⎧

(k ) (k -1)

　若w i , j =w i , j ⎪⎩r i , j

F2：若k

上面的路由方法为前向路由，容易更改算法使它的路由为回溯路由; 算法要执行n 次迭代, 第k 次迭代的目的为经过端k 转接是否可以使各端之间距离缩短. 从本质上讲, Floyd算法的迭代过程就是保证满足下面的定理成立.

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

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

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

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

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

v 1v 1v 2v 3v 4v 5v 6

⎡0⎢1⎢⎢2⎢∞⎢⎢∞⎢⎣7

v 2

90∞∞6∞v 3140522

v 43∞∞08∞

v 5∞71202

v 6∞⎤⎥∞⎥∞⎥⎥7⎥5⎥⎥0⎦

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

V4和V1至V5的最短径长及路由。

3. 求图的中心和中点。

解：

10 2∞ 9 9 8 8 3∞ 1 4∞ 3 3 5∞ ∞ 6∞ ∞ ∞ 7 7 V 1 V 3 V 5 V 4 V 3 W 1＝0, 1 W 13＝1, 1 W 15＝2, 3 W 14＝3, 1 W 16＝7, 5

2. F 算法

最短路径矩阵及最短路由阵为W 5，R 5 v 2→v 1→v 4有向距离为4

v 1→v 3→v 5有向距离为2

⎡0913∞∞⎤⎡023400⎤⎢⎢104∞7∞⎥⎢⎥⎢103050⎥⎥W ⎢2∞0∞1∞⎥00050⎥0=⎢

⎢∞∞5027⎥R =⎢10⎢

⎥⎢003056⎥⎥⎢∞62805⎥⎢023406⎥⎢⎣7∞2∞20⎥⎦⎢⎣103450⎥⎦⎡0913∞∞⎤⎡023400⎤⎢⎢⎢10247∞⎥⎥⎢101150⎥⎥W =⎢211051∞⎥1⎢

R ⎢110150⎥1=⎢

⎢∞∞5027⎥⎥⎢003056⎥⎥⎢∞62805⎥⎢023406⎥⎢⎣71621020⎥⎦⎢⎣113150⎥⎦⎡091316∞⎤⎡023420⎤⎢⎢⎢10247∞⎥⎥⎢101150⎥⎥W ⎢211051∞⎥2=⎢

R =⎢110150⎥2⎢

⎢∞∞5027⎥⎥⎢003056⎥⎥⎢762805⎥⎢223406⎥⎢⎣71621020⎥⎦⎢⎣11315

0⎥⎦

⎡09132∞⎤⎡023430⎤⎢⎢⎢10243∞⎥⎥⎢101130⎥⎥W =⎢211051∞⎥3⎢

R ⎢110150⎥3=⎢

⎢7165027⎥⎥⎢333056⎥⎥⎢462805⎥⎢323306⎥⎢⎣4132720⎥⎦⎢⎣31

3

3

5

0⎥⎦⎡0913210⎤⎡023434⎤⎢⎢⎢1024311⎥⎥⎢101134⎥⎥W ⎢21105112⎥4=⎢

R =⎢110154⎥4⎢

⎢7165027⎥⎥⎢333056⎥⎥⎢462705⎥⎢323306⎥⎢⎣413272

0⎥⎦⎢⎣31335

0⎥⎦⎡081327⎤⎡053435⎤⎢⎢⎢102438⎥⎥⎢101135⎥⎥W ⎢270516⎥5=⎢

R ⎢150155⎥5=⎢

⎢684027⎥⎥⎢555056⎥⎥⎢462705⎥⎢323306⎥⎢⎣4

8

2

7

2

0⎥⎦

⎢⎣3

53

3

5

0⎥⎦

3.

Max W 5

ij =(8, 8, 7, 8, 7, 8)

中心为V j

3或V 5

∑W

5ij

=(21, 18, 21, 27, 24, 23) 中点为V 2

j

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

3、网的中心与中点

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

中心:

对每个端点i, 先求max (w (n ) i , j )

j

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

m a x (w (n ) (n )

j

i *,j

) =min i

[max j

(w i , j )] 网的中心宜做维修中心和服务中心。 中点:

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

先计算 s i = [∑w (n ) i , j ], 然后求出s i 的最小值, 相应的端点为中点.

j

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

§2.3网络流量问题

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

§2.3.1基本概念

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

∑

v j ∈Γ(vi )

f ij -

∑

f ji

v j ∈Γ' (vi )

⎧F

⎪=⎨-F ⎪0⎩

v i 为源端v i 为宿端 其他

v(f) = F为源宿间流{fij }的总流量.

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

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

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

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

如果边(i,j)的单位流费用为d i,j , 流f 的费用为: Φ=

(i , j ) ∈E

∑d

i , j

f

i , j

所谓最小费用流问题:

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

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

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

c

c

C (X , X c ) =∑C ij

v i ∈X , v j ∈X

c

对可行流{fij }:

f(X，X c ) 表示前向边的流量（和）∑f ij, 其中v i ∈X ，v j ∈X c f(Xc ，X) 表示反向边的流量 (和) ∑f ji, 其中v i ∈X ，v c j ∈X 则源为v s 宿为v t 的任意流f 有:

(1) v(f)=f(X,Xc )-f(Xc ,X), 其中v s ∈X ，v t ∈X c 证明：

对任v i ∈X : ∑f v i =v s ij -

∑

f ⎧F ji =⎨

v j ∈V

v j ∈V

⎩0

v i ≠v s

对所有v i ∈X, 求和上式：

∑∑

f ij -

∑∑

f ji =

∑∑

f ij -

∑∑

f ji

v i

∈X v

j

∈V

v i ∈X v j ∈V

v i ∈X v j ∈X

c

v i ∈X v c

j ∈X

=f (X , X c

) -f (X c

, X ) =F =v (f )

v t

∑∑

f ij

∑∑

f ij

v i ∈X v j ∈X

c

v c

i ∈X

v j ∈X

源端 s: fs1+fs2+fs3

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

∑∑

f ij

-∑∑

f ij

v c

i ∈X v j ∈X

v c

i ∈X

v j ∈X

= f14+f3t -f 53= f(X,Xc )-f(Xc ,X)=F (2) F≤C(X,Xc

)

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

F =f (X , X c

) -f (X c

, X ) ≤f (X , X c

) ≤C (X , X c

)

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

从端s 到端t 的一个路，有一个自然的正方向，然后将路上的边分为两类：前向边集合和反向边集合。对于某条流，若在某条路中，前向边均不饱和（f ij

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

§2.3.2 最大流问题

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

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

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

*令 0

(i , j ) ∈μ

+

f

*i , j

}为最大流当且仅当G 中不存

(i , j ) ∈μ

-

构造一个新流f 如下:

如果 (i , j ) ∈μ+, f i , j =f i *+θ , j

-θ 如果 (i , j ) ∈μ-, f i , j =f i *

, j

如果 (i , j ) ∉μ, f i , j =f i *, 不难验证新流f 为一个可行流, 而且, j

v(f)=v(

f

*i , j

)+θ, 矛盾.

充分性: 设f *为可行流, G中不存在关于这个流的可增流路. 令X * = {v|G中存在从v s 到v 的可增流路},从而v s ∈X *, vt ∉X *.

=c i , j 对于任意边 (i , j ) ∈(X *, X *c ) , 有f i *, j =0 对于任意边 (i , j ) ∈(X *c , X *) , 有f i *, j

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

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

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

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

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

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

M 0：初始令f i,j =0

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

M2：从v s 始，查已标为查端v i ，即标v i 的满足下列条件的邻端v j ， 若（v i ,vj ）∈E ，且c i,j > fi,j ， 则标v j 为: (+，i ，εj ) 其中εj

=min(ci,j -f i,j ，εi

) ε

i

为v i 已标值。

若（v j ,vi ）∈E ，且 fj,i >0， 则标v j 为: (-，i ，εj ) ，

其中ε

j

=min（ε

i

，f j,i ）其它端v j 不标。

所有能加标的邻端v j 已标，则称v i 已查。 倘若所有端已查且宿端未标，则算法终止。 M3：若宿端v i 已标，则沿该可增流路增流。 M4: 返回M1。

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

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

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

对多源多宿的情况，设原有源为V s 1, V s 2,..., V sl ，原有宿为V t 1, V t 2,..., V tk ，要求从源集到宿集的最大流量，可以虚拟一个新的源V s 和新的宿V t ，源V s 到

V s 1, V s 2,..., V sl 的各边容量均为无限大，V t 1, V t 2,..., V tk

到宿V t 的各边容量也为无

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

v s

v t

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

如图所示，一个四个节点的网络，求v s 至v 的最大流量。假设按前述算法，

t

并且按如下顺序从f=0开始增流： 例

2.8

v s

p v t

v s →q →p →v t 增流1； v s →p →q →v t 增流1;

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

§2.3.3最小费用流问题

如果网络为图G = (V, E), 源端为v s , 宿端为v t . 边(i,j)的单位流费用为d i,j 流f 的费用为: Φ=

(i , j ) ∈E

∑d

i , j

f

i , j

所谓最小费用流问题:

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

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

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

对于所有的边e i , j , 如果c i , j >f i , j , 构造边e i 1, j ,

容量为:c i , j -f i , j , 单位流费用为: d i,j ;

对于所有的边e i , j , 如果f i , j >0, 构造边e i 2, j ,

容量为:f i , j , 单位流费用为: -d i,j ;

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

δ=min (c i *, j )

(i , j ) ∈C

-

K4： 修改原图的每边的流量，得新可行流。 K5： 返回k1。

例2.9：已知c i,j ，d i,j ，要求F=9。求最小费用流。

v s

4, 6

v t

v s

t

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

v

Φ=96

δ

=min -

(3, 3, 4) =3

C

v 已无负价环

价环

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

4X 6=243X 6=18v s

原53=155X 3=15现6X 3=18

现6X 3=18

24+15+15=54 18+18+18=54

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

第2章 通信网拓扑结构

参考文献：

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 JAMES B.ORLIN Procedings of the coth ACM Symposium on the Theory of Computing

6. 线性规划最新进展，马仲蕃，科学出版社，1994

7. 《运筹学》，清华大学出版社，1990.1

PP377-387 36