（通信企业管理）第二章
通信网的拓扑结构
第二章通信网拓扑结构
通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和
设计的第壹层次问题。通信网的拓扑结构能够用图论的模型来代表，主要的
问题为最短径和网络流量问题。本章仍介绍了线性规划问题的基本概念和方
法及网络优化结构模型。
§图论基础
图论是应用数学的壹个分支，本节介绍它的壹些概念和结论。其基本内
容可参见（1）和（2）。
图的定义
例 哥尼斯堡 7桥问题;
所谓壹个图，是指给了壹个集合 V，以及 V中元素的序对集合 E，V和 E
中的元素分别称为图的端点和边。
下面用集合论的术语给出图的定义：
设有集合 V 和 E，V={v1，v2，……，vn}，E={e1，e2，……em}，且则 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 的子图。若
AG，且 AG，则 A 为 G 的真子图。特别地，当 A 的端集和 G 的端集相等，称 A
为 G的支撑子图。由端点子集诱导生成的子图.
图的运算:
G1G2,G1G2,Gc等
图的几种表现形式:集合论定义,几何实现,矩阵表示.
图的同构;权图.
图的连通性
对无向图的端 vi 来说，和该端关联的边数定义为该端的度数：，记为：
d(vi)。对有向图：d+(vi)表示离开 vi的边数，d-(vi)表示进入 vi的边数
对图 G=(V，E)，若|V|=n，|E|=m，则有如下基本性质：
1）若 G是无向图
2）若 G是有向图
下面定义图的边序列，链，道路，环和圈：
相邻二边有公共端的边的串序排列（有限）(v1，v2)，(v2，v3)，(v3，v4)，
(vi，vj)，称为边序列。边序列中，无重边的，成为链(link)；若边序
列中没有重复端，称为道路(path)；若链的起点和终点重合，称之为环
(ring)；若道路的起点和终点重合,称之为圈(cycle)。
任何二端间至少存于壹条径的图，为连通图。否则，就是非连通图。对非连
通图来说，它被分为几个最大连通子图，即几个“部分”。“最大连通图”指
的是于此图上再加任意壹个属于原图而不属此图的元素，则此图成为非连通
图，如下例:
G=ABC=A+B+C
对于图的连通,能够通过下面的方法给予准确的描述:
对于图 G 中的任意俩个端点 u 和 v,如果存于壹条从 u 到 v 的链,称 u 和 v 有关系,
容易知道这是壹个等价关系;从而能够将图 G 做壹个等价分类,每壹个等价分类
就是壹个连通分支.连通分支只有壹个的图为连通图.
下面举壹些图的例子:
(1)完全图 Kn：任何二端间有且只有壹条边（即直通路由），称为完全图，
其边、端数之间存于固定关系:
下面是壹个 n=5的完全图
(2)正则图：所有端度数均相同的连通图为正则图
d(vi)=常数（i=1，2，n）
正则图是连通性最均匀的图
(3)尤拉图(Euler):端度数均为偶数的连通图为尤拉图。
尤拉图的性质:尤拉图存于壹个含所有的边且每边仅含壹次的环.
(4)俩部图
俩部图的端点集合分为俩个部分,所有边的端点分别于这俩个集合中.
完全俩部图 Km,n
(5)
树:
树是图论中壹个很简单，可是又很重要的概念，于图论中运用是十分重要的。
图的定义有多种,如下面的定义：
1、任何二端有径且只有壹条径的图称为树。
2、无圈的连通图称为树.
我们采用第 2种关于图的定义方式,也就是:
树:无圈的连通图称为树.
树有以下性质:
1.树是最小连通图，树中去壹边则成为非连通图。
2.树中壹定无环。任何二端有径的图是连通图，而只有壹条径就不能有环。
3.树的边数 m和端数 n满足 m=n-1
此式能够用数学归纳法证明。
4.除单点树，至少有俩个度数为 1的端(悬挂点)
树上的边称为树枝(branch)
定理 ：给定壹个图 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个树有个点，则，和 q=p-1相矛盾；
3）1），p=1 时，显然。设，T 连通，且 q=p-1，首先易证 T 有悬挂点，不
然，，和 q=p-1相矛盾；然后对点数进行归纳即可；
定理 ：若 T是树，则：
（1）T是连通图，去掉任何壹条边，图便分成俩个且仅仅俩个分图；
（2）T是无圈图，但添加任何壹条边，图便会包含壹个且仅仅壹个圈。
同时，若无向图满足（1）和（2），则 T是树。
定理 ：设 T 是树，则任何俩点之间恰好有壹条道路；反之，如图 T 中任何俩
点之间恰好有壹条道路，则 T为树。
定理 和 刻画了树的俩个重要特征，事实上定理 也为图提供了另壹个
等价定义。上述俩个定理的证明请读者自行完成。
支撑树(SpanningTree)：
考虑树 T是连通图 G的子图，TG，且 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
例如：
k=3；=11-3=8；=12-11+3=4
割(cut)
割指的是某些子集(端集或边集)。对连通图，去掉此类子集，变为不连通。对非
连通图，去掉此类子集，其部分数增加。
割分为割端集和割边集。
1、割端和端集
设 V 是图 G 的壹个端，去掉 V 和其关联边后，G 的部分数增加，则称 V 是图 G 的
割端。去掉几个端后，G 的部分数增加，这些端的集合称为割端集。有的连通图
无割端，这种图称为不可分图。
对于连通图,于众多的割端集中至少存于壹个端数最少的割端集，称为最小割端
集。最小割端集，其任意真子集不为割集。
最小割端集的端数目，称为图的联结度。联结度越大，图的连通性愈不易被破坏。
2、割边集和割集
连通图 G的边子集 S，去掉 S使 G为不连通，称 S为割边集
于众多的割集中边数最少的割集，称为最小割边集。最小割边集的任壹真子集不
为割边集。最小割集的边数，称为结合度.结合度同样表示图的连通程度，结合
度越高，连通程度越好。
3、基本割集和基本环（针对连通图讨论）
1）基本割集
设 T为连通图 G的壹个支撑树，取支撑树的壹边（枝）和某些连枝，定可构
成壹个极小边割集，此割集称为基本割集。即：基本割集是含支撑树 T之壹个树
枝的割集。基本割集有 n-1个.
下面壹个图来理解基本割集.
支撑树 T={}连枝：，
则基本割集：（，），(，，)，(，)，(，)
2）基本环
T为连通图 G的壹个支撑树，G-T的边集为连枝集。取壹连枝可和某些树枝构
成环。这种包含唯壹连枝的环称基本环。
每个基本环只包含壹个连枝---和连枝壹壹对应，其数目=连枝数，共 m-n+1
个。
环和运算:对于集合,这个运算的意义为对称差运算.
通过环和运算,由基本割集和基本环能够生成新的环和割集或它们的且集,
事实上能够生成所有的环和割集.
例 通过基本环和基本割集理解基尔霍夫定律.
下面的图理解基本环.
连枝集，，，
：，，，
：，，
：，，
：，，
图的平面性
图 G若能够于壹个平面上实现，除端点以外，任何俩条边均无其他交点，则
称 G是平面图。当平面图有壹个平面实现后，它把全平面分成 s个区域（含包含
无穷远点的开区域）。注意壹个图为平面图等效于能够于球面上有壹个几何实现.
设连通平面图有 m 边，n 端，则 s=m-n+2，此为著名的 Euler 公式。这个性
质能够用数学归纳法证明或树的性质证明。
m=4，n=4，s=2
定理 ：简单连通图为平面图的必要条件是:
m<=3n-6(n>=3)
上述结论能够推广到有重边和自环的情形.
证：形成区域至少 3边，区域周线上的边数至少 3s(不考虑区域共边)，实际
每边均于二区域周线上，最多有 2m边（周线上）。考虑区域共边，有 2m3s，代入
Euler公式得 m3n-6.
此为平面图的必要，非充分条件。
例 讨论完全图 K5和完全俩部图 K3,3的平面性.
定理 连通俩部图为平面图的必要条件是:
m+4<=2n(n>=3)
根据每个平面图 G=（V，E），能够生成壹个对偶图 G'。G的每个平面对应于 G'
的每个顶点，G中相邻的俩个面于 G'中有壹些边和 G中的俩个面的每壹条边界的
边相交，如下图所示。可是简单平面图的对偶图可能不再是简单图。
定理 图 G为平面图当且仅当 G不含 K5和 K3,3或它们的细分图为子图.
图的矩阵表示
很多时候，需要将图表示于计算机中，这就有了图的矩阵表示。下面主要介绍关
联阵和邻接阵。
1．关联阵
设图 G有 n个端，m条边，则全关联阵；
端 vi对应于矩阵的第 I行(共 n行)；边 ej对应于第 j列(共 m列);
其中:
下面是壹个例子说明关联矩阵,
例
由 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-1m 阶。A 中的每壹个非奇异方阵对应壹个支撑树。图 G 的支撑树数目
可由以下方法得到：
定理 (矩阵-树定理)
用 AT表示 A的转置,无向图 G的主树数目
(G)=det(AAT)，
注意上面的定理计算的主树数目为标号树的数目;同时 n-1 阶矩阵 det(AAT)
能够直接写出,主对角线的元素为相应端点的度数,其余位置为-1 或 0,而这取决
于相应的端点之间是否有边.
例 (Kn)=,(Kn,m)=mn-1nm-1.
(Kn)=的计算如下：
继续例 :
共有 8种支撑树如下
2.邻接阵
邻接阵是表征图的端和端关系的矩阵，其行和列均和端相对应。
令 G=（V，E）是 m端，n边的有向图，其邻接阵
其中，
如：
对于无向图，因此是邻接阵为对称阵。
我们能够通过对 C的壹些计算，得到图 G的性质。如：计算 C的幂次可得到
关于转接径长的壹些信息。
若 Cij(2)=1 则存于 k，使 CikCkj=1，即 Cik=Ckj=1，i，j 之间至少有径，径长
为 2；若 Cij(2)=a，则 vivj间有 a 条径长为 2 的径，若 Cij(2)=0，则 vivj间无
径长为 2的径；所以，Cij(2)即为 vivj间径长为 2即转接壹次的径数。
同理，若 Cij(3)=1，则有 vivkvsvj，径长为 3，即经过二次转接。
由此可得下面结论:邻接阵幂之元素表示了二端间转接次数不超过 b-1的
径，可是经过转接的端可能重复。
已知图 G 的邻接阵 C,需要解决图 G 是否连通的问题?当然通过计算邻接阵 C
和 C的幂能够解决这个问题,考虑下面的小算法,它解决同样的问题,但效率很高.
Warshall1962
(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)如 ni转向步骤(3),否则停止.
本节介绍了图论的简要知识，[1]和[2]介绍了很好的基础知识。[4]介绍了
网络优化算法的详尽的和较新的进展。本节内容同时也借鉴[3]的壹些结果。某
些图论知识于以后应用是会于介绍。
§最短径问题
上节中介绍的图只考虑了图顶点之间的关联性，本节将要对图的边和端赋予
权值，讨论有权图。权值于各种各样实际问题中有不同的实际意义，如费用，
几何距离，容量等等。本节将介绍壹些算法，大部分算法可借助计算机实现。
§最短支撑树
给定连通图 G=(V，E)，W(e)是定义于 E 上的非负函数，称 W(e)为 e 的
权。T=(V，)为 G 的壹个支撑树。定义树 T 的权为。最短支撑树问题就是求
支撑树，使 W()最小。下面介绍求最短支撑树的方法。
1)无限制条件的情况
Prim于 1957年提出壹个方法，简称 P算法。
图 G有 n端，端间“距离”dij(i，j=1，2，3，….n)已给定(若无边则 dij=)，
找壹个支撑树，使其 n-1个边（树枝）的权和最小，步骤如下：
P0:任取壹端 v1，子图 G1={v1}，于 G1到 G-G1中取最小的 dij
得子图 G2={v1，v2}
P1:求 G3
得子图 G3={v1，v2，v3}
…
Pr-2:从 Gr-1求 Gr
得子图 Gr={v1，v2，…，vr}
Pr-1:重复 Pr-2，直至得到 Gn为止
例 :
G1={v1}
G2={v1，v3}
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次，可得总计算量
约为 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(即限转接
次数<K-1)，且径上总业务量M，(其中 K 为给定的整数,M 为给定的实数),
求最短支撑树
算法主要思想:
从上图开始(星形树),采用贪心法原则,逐步用边替换 vi至 v1的边,为
此需要计算转接损失矩阵,每次选用壹条边使新树的长度减少最多,但每次
要注意新树是否满足限制条件。实质上，每次均和上次得到的树做比较，见
见能否有进展。
步骤：
EW0：起始，n个端为 n个部分，邻接阵为全零阵；
EW1：计算到 v1各个部分的距离 D1i，和不于同壹个部分内的俩端之间的
边的转接损失 tij
EW2：
测试增加边(i*,j*)边后是否仍满足条件，若满足，于邻接阵置
；若不满足，则重复 EW2；
EW3：考虑形成的新的部分，若部分数大于 1，返回；等于 1，终止；
说明：若
实例 (其中 K=3,M=50)：
计算 T矩阵：
t34=-11最小，
取边（3,4）最替换边(3,1)；
如此反复，最后得树为:{(3,4),(4,1),(2,5),(5,1)}
树长=12
上面的例中,如果将边(3,2),(2,1)和(4,5)的权改为 2, 和 ,容易得到
壹个简单的反例,存于壹个树长为 11 的支撑树,也满足问题中要求的限制条件，
说明上述 EW算法得到的不是全局最优解.
§、端间最短径
当网络结构已定，我们需要寻找端间的最短距离和路由。分俩种情况：
寻找指定端至其它端的最短径和路由，我们采用 Dijkstra算法；
寻找任意二端最短径和路由,用 Floyd算法。
1)指定端至其它端最短径和路由算法:
已知图 G=(V，E)及 dij，求端 vs至其它端的最短径和路由，用 Dijkstra算法：
由上图能够见出：
直边不壹定是最短径，如 ds2，其实 vs和 v2间最短径长为 3(经 v3转接)。但
可肯定，和 vs相连的直边最小的壹个必定为最短径(如 es3)，其它转接至 vs
必不短。因此，算法从始找邻近端，从 vs最邻近端找起，每次得壹个最短
径。
下面我们介绍 Dijkstra 算法，暂时不考虑端有权,对于端有权的情况稍后处理;
首先我们会用到下列计算中的名词：
置定：某端置定即表示得到了至该端的最短径
标值：至该步时的暂时最短径，（置定端可供转接）
wi为 vsvi暂时的的最短径长
wj*为 vsvi的置定时的最短径长
Dijkstra算法步骤：
端点集合 Vp表示置定的端点集合,V-Vp为没有置定的端点集合;
D0开始置定 vs，ws*=0（vsvs），其它端暂置 wj=(如果边(s,j)存于,wj=ds,j)
D1计算未置定端 vj的标值的公式
wj:=min（wj，wi+dij）,其中 viVpvjV-Vp
D2取最小值,
wj*=minwj然后,置定端 vj*Vp;当所有端置定，算法结束.不然,返回 D1.
上面的算法没有给出取得最短径的路由,不过对于路由能够很简单处理.路
由的给出方法能够有许多种,如前向路由和回溯路由等.对于 Dijkstra 算法,能
够给出回溯路由,即给出最短径的前壹个端点的标号,而这个端点标号能够于算
法 D1 的更新计算中获得;每个端点的标号能够由俩部分组成,即距离和前壹个端
点标号.
例 ：
VsV1V2V3V4 置定端距离路由
0
8426
835
65
6
Vs0s
V32s
V233
V453
V162
D 算法计算量:当有个 k 端已置定，需做(n-k)次加法，(n-k)次比较以更新
各端的暂定值，(n-k-1)次比较求最小值，则总计算量约为
对于 Dijkstra算法,提出若干问题如下:
1如果端点有权如何处理?
2如果边的权可正可负,算法是否仍然有效?
3算法是否对有向图也适用？
上面 Dijkstra 算法中使用的为 Label-setting 的方法 ,下面介绍壹个用
Label-correcting技术的方法,效率要高许多。
不失壹般性，假设是 G壹个有向图，用 d(i)记从 s至 i的距离，pred(i)
记路由 s→i的上壹个顶点(回朔路由),A(i)记录从 i出发的所有边的集合。
算法如下：
begin
d(s):=0andpred(s):=0;
d(j):=∞foreachj∈V-{s};
List:={s};
whileListdo
begin
从 List中去掉壹个元素 i;
对每个边(i,j)∈A(i)do
ifd(j)>d(i)+Cijthen
begin
d(j):=d(i)+Cij
pred(j):=i；
ifjList,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)]nn
其元素：
同时 R(0)=[rij(0)]nn
F1：已求得 W(k-1)和 R(k-1)，求 W(k)和 R(k);
wij(k)=min[wij(k-1)，wik(k-1)+wkj(k-1)]
F2：若 k<n，重复；k=n终止。
上面的路由方法为前向路由，容易更改算法使它的路由为回溯路由;算法要执行
n 次迭代,第 k 次迭代的目的为经过端 k 转接是否能够使各端之间距离缩短.从本
质上讲,Floyd算法的迭代过程就是保证满足下面的定理成立.
定理 对于图 G,如果 w(i,j)表示端 i 和 j 之间的可实现的距离,那么 w(i,j)
表示端 i和 j之间的最短距离当且仅当对于任意 i,k,j有:
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算法是否对有向图也适用？
例 给定壹个无向图 G,求任意俩端之间最少转接次数和路由.
例 图有六个端，端点之间的有向距离矩阵如下：
解：
1. D算法
V1 V2 V3 V4 V5 V6 指定 最短径长,路
由
0 ∞ ∞ ∞ ∞ ∞ V1 W1＝0,1
9 1 3 ∞ ∞ V3 W13＝1,1
9 3 2 ∞ V5 W15＝2,3
8 3 7 V4 W14＝3,1
8 7 V3 W16＝7,5
8 V2 W12＝8,5
2. F算法
最短路径矩阵及最短路由阵为 W5，R5
有向距离为 4
有向距离为 2
3. 中心为 V3或 V5
中点为 V2
于实际问题中，除了求最短径外，如当主路由（最短径）上业务量溢出或
故障时，需寻求次短径或可用径。次短径指备用径，可用径指壹批满足某种
限制条件的径（如限径长，限转接次数….）。但这些问题壹般没有多项式算
法,能够根据实际情况采用某种贪心策略获得近似解.
3、网的中心和中点
1. 用 D算法求 V1到所有其他端的最短径长及其路径。
2. 用 F算法求最短径矩阵和路由矩阵，且找到 V2至 V4
和 V1至 V5的最短径长及路由。
3. 求图的中心和中点。
如网络用图 G=(V,E)表示,根据 Floyd 算法的计算结果能够定义网络的
中心和中点.
中心:
对每个端点 i,先求
此值最小的端称为网的中心，即满足下式的端 i*：
=
网的中心宜做维修中心和服务中心。
中点:
将“平均最短径长”最小的端，定义为中点，
先计算 si=,然后求出 si的最小值,相应的端点为中点.
网的中点可用做全网的交换中心。
§网络流量问题
网络的目的是把壹定的业务流从源端送到宿端。流量分配的优劣将直接关
系到网络的使用效率和相应的经济效益。网络的流量分配受限于网络的拓
扑结构，边和端的容量以及路由规划。本节及下节中关于流量的内容均于
有向图上考虑，且且均是单商品流问题，即网络中需要输出的只有壹种商
品或业务。通信网络的服务对象有随机性的特点,关于通信业务随机性特点
将于下壹章中考虑,本节中假设网络源和宿的流量为常量.
§基本概念
给定壹个有向图 G=（V，E），C(e)是定义于 E上壹个非负函数，称为容量；
对边 eij，边容量为 Cij，表示每条边能通过的最大流量。设 f={fij}是上述
网络的壹个流，若能满足下述二限制条件，称为可行流。
a)非负有界性：0≤fij≤Cij；
b)连续性:对端 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的费用为:
所谓最小费用流问题:
于确定流的源和宿的情况下,求壹个可行流 f,使φ为最小.
下面介绍割量和可增流路的概念.
设 X 是 V 的真子集，且 vs∈X，vt∈Xc，（X，Xc）表示起点和终点分别于 X
和 Xc的边集合，这个集合当然为壹个割集,割集的正方向为从 vs到 vt。
割量定义为这个割集中边容量的和:
对可行流{fij}:
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:
对所有 vi∈X,求和上式：
源端 s:fs1+fs2+fs3
中转端 1:f14-(fs1+f21)
中转端 2:f21+f23-(fs2)
中转端 3:f3t-(fs3+f23+f53)
-
=f14+f3t-f53=f(X,Xc)-f(Xc,X)=F
(2)F≤C(X,Xc)
由（1）及 f(X,Xc)非负，可得：
下面讨论可增流路的概念。
从端 s 到端 t 的壹个路，有壹个自然的正方向，然后将路上的边分为俩类：前
向边集合和反向边集合。对于某条流，若于某条路中，前向边均不饱和
（fij<cij），反向边均有非 0 流量（fij≠0），称这条路为可增流路径（或增广
链）。于可增流路上增流不影响连续性条件，也不改变其它边上的流量，同时能
够使从源端到宿端的流量增大。
若流{fi,j}已达最大流，f则从源至宿端的每条路均不可能是可增流路，即每条
路至少含壹个饱和的前向边或流量为 0的反向边。
§最大流问题
所谓最大流问题，于确定流的源端和宿端的情况下,求壹个可行流 f,使 v(f)为
最大。对于壹个网络，求最大流的方法采用可增流路的方法，下面的定理
为这种方法提供了保证.
如果网络为图 G=(V,E),源端为 vs,宿端为 vt.
定理 (最大流-最小割定理)可行流 f*={}为最大流当且仅当 G 中不存于从 vs
到 vt的可增流路.
证明:
必要性:设 f*为最大流,如果 G中存于关于 f*的从 vs到 vt的可增流路μ.
令 0<θ=min[,],θ是存于的.
构造壹个新流 f如下:
如果,
如果,
如果,,不难验证新流 f为壹个可行流,而且 v(f)=v()+θ,矛盾.
充分性:设 f*为可行流,G中不存于关于这个流的可增流路.
令 X*={v|G中存于从 vs到 v的可增流路},从而 vsX*,vtX*.
对于任意边,有
对于任意边,有
这样,,那么流 f*为最大流，为最小割。证毕。
网络处于最大流的情况下，每个割集的前向流量减反向流量均等于最大流量且
总存于壹个割集，其每条正向边均是饱和的，反向边均是零流量；其割量于诸
割中达最小值，且等于最大流量。
推论：如果所有边的容量为整数，则必定存于整数最大流。
求最大流的基本思想是：于壹个可行流的基础上，找 vs→vt的可增流路，
然后于此路上增流，直至无可增流路时，停止。
具体方法(M算法)：从任壹可行流开始，通常以零流{fi,j=0}开始。
（1）标志过程：从 vs开始给邻端加标志,加上标志的端称已标端;
（2）选查过程：从 vs开始选查已标未查端
查某端，即标其可能增流的邻端;
所有邻端已标，则该端已查。
标志宿端，则找出壹条可增流路到宿端，进入增流过程。
（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的边均起始于，且从至有壹条边容量为 Ci。
对多源多宿的情况，设原有源为，原有宿为，要求从源集到宿集的最大流
量，能够虚拟壹个新的源和新的宿，源到的各边容量均为无限大，到宿的各
边容量也为无限大，这样多源多宿的问题就化为从到的最大流问题。见下图：
仔细考虑壹下会发现，前面介绍的算法于任何网络中是否壹定会收敛，也
就是说会不会不断有增流路，但却不收敛于最大流呢？如果边的容量均为有理
数，是不会出现这种情况，也就是说壹定会收敛。但若边的容量为无理数，就
不壹定收敛。对于计算量的问题,Ford和 Fulkerson曾给出下面的例子。
如图所示，壹个四个节点的网络，求至的最大流量。假设按前述算法，且
且按如下顺序从 f=0开始增流：
例
；
;
显然，这样需要 2n+1步增流才能找到的最大流，流量为 2n+1。这个例子说明
前述算法虽然能够达到最大流，可是由于没有指明增流方向，导致有可能象这
个例子壹样，效率很低，这个例的计算工作量和边容量有关。1972年，Edmonds
和 Karp 修改了上述算法,于 M2 步骤时采用 FIFO 原则(于选哪个端查时),从而
解决了这个问题；新算法壹方面收敛,同时也为多项式算法.后来，人们提出了
许多改进的算法，如 Dinits算法和 MPM算法，其主要思想是赋予网络壹些新的
结构能够使算法更有效率等等。有兴趣者可参阅[2]。
§最小费用流问题
如果网络为图 G=(V,E),源端为 vs,宿端为 vt.边(i,j)的单位流费用为 di,j流 f
的费用为:
所谓最小费用流问题:
于确定流的源和宿的情况下,求壹个可行流 f,使φ为最小.
最小费用流问题是线性规划问题，但也可用图论方法求解,效率更高。对于
它的存于性能够这样理解，流量为 F 的可行流壹般不是唯壹的，这些不同
的流的费用壹般也不壹样,有壹个流的费用最小.
寻找最小费用流，用负价环法(Klein,1967),所谓负价环的意义如下:负价环为
有向环,同时环上费用的和为负。负价环算法的具体步骤如下：
K0：于图 G上找任意流量为 F的可行流 f;
K1：做流 f的补图;做补图的方法如下:
对于所有的边,如果,构造边,
容量为:,单位流费用为:di,j;
对于所有的边,如果,构造边,
容量为:,单位流费用为:-di,j;
K2：于补图上找负价环。若无负价环，算法终止。
K3：于负价环上沿环方向使各边增流
增流数：
K4：修改原图的每边的流量，得新可行流。
K5：返回 k1。
例 ：已知 ci,j，di,j，要求 F=9。求最小费用流。
上面可行流安排总费用为:φ=102.下面做补图,寻找负价环,调整可行流.
零价环上增流:得另壹最小费用流
24+15+15=54
18+18+18=54
前面负价环的算法中,如何寻找负价环?这个问题能够应用 Floyd算法解决.
最小费用流问题是网络流问题中比较综合的问题，和线性规划问题的关系非
常密切,对于它的研究仍将继续进行。
参考文献：
1. Bondy,,Graphtheorywithapplications,TheMacmillan
PressLtd,1976
2. 图和网络流理论，田丰，马仲蕃，科学出版社，1987
3. 通信网理论基础，周炯磐，人民邮电出版社，1991
4.
5. ORLIN,
ocedingsofthecothACMSymposiumontheTheoryofComputingPP377-387
6. 线性规划最新进展，马仲蕃，科学出版社，1994
7. 《运筹学》，清华大学出版社，
