通信网理论基础(苏驷希)(北京邮电大学讲义)--第二章 通信网的拓扑结构

1、第2章 通信网拓扑结构第二章 通信网拓扑结构 通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。2.1图论基础图论是应用数学的一个分支，本节介绍它的一些概念和结论。其基本内容可参见（1）和（2）。2.1.1图的定义 例2.1 哥尼斯堡7桥问题;所谓一个图，是指给了一个集合v，以及v中元素的序对集合e，v和e中的元素分别称为图的端点和边。下面用集合论的术语给出图的定义：设有集合v和e，v=v1，v2，vn， e=e1，e2， e

2、m ，且则v和e组成图g，称v为端集，e为边集。下面给出图的一些概念: 当eij=(vi，vj)，称边eij和端vi与vj关联； 当virvj不等价于vjrvi 时，为有向图； 当virvj等价于vjrvi(eij=eji)时，为无向图；当v=(此时e必为空集) ，为空图；自环，孤立点图，重边；简单图: 不含自环和重边的图称为简单图. 当v，e均有限元 v，e时，称为有限图。我们一般讨论的都是有限图，考虑到实数集的不可数性，任何有限图都可以表示为三维空间的几何图形，使每两条边互不相交，而且边均可用直线来实现。但是若要在平面实现则不一定能办到，稍后我们会给出平面图的概念。 子图:若a的端集与边集

3、分别为g的端集与边集的子集，则a为g的子图。若ag，且ag，则a为g的真子图。特别地，当a的端集和g的端集相等，称a为g的支撑子图。由端点子集诱导生成的子图. 图的运算:g1g2, g1g2, gc等 图的几种表现形式: 集合论定义, 几何实现, 矩阵表示. 图的同构; 权图.2.1.2图的连通性 对无向图的端vi来说，与该端关联的边数定义为该端的度数：，记为：d(vi)。对有向图：d+(vi)表示离开vi的边数，d-(vi)表示进入vi的边数对图g=(v，e)，若|v|=n，|e|=m，则有如下基本性质： 1）若g是无向图 2）若g是有向图 下面定义图的边序列，链，道路，环和圈： 相邻二边有

4、公共端的边的串序排列（有限） (v1，v2)， (v2，v3)， (v3，v4)， (vi，vj)，称为边序列。边序列中，无重边的，成为链(link)；若边序列中没有重复端，称为道路(path)；若链的起点与终点重合，称之为环(ring)； 若道路的起点与终点重合,称之为圈(cycle)。 任何二端间至少存在一条径的图，为连通图。否则，就是非连通图。对非连通图来说，它被分为几个最大连通子图，即几个“部分”。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素，则此图成为非连通图，如下例: g=abc=a+b+c对于图的连通, 可以通过下面的方法给予准确的描述: 对于图g中的任意两个

5、端点u和v, 如果存在一条从u到v的链, 称u和v有关系, 容易知道这是一个等价关系; 从而可以将图g做一个等价分类, 每一个等价分类就是一个连通分支.连通分支只有一个的图为连通图.下面举一些图的例子:(1)完全图kn：任何二端间有且只有一条边（即直通路由），称为完全图， 其边、端数之间存在固定关系: 下面是一个n=5的完全图 (2)正则图：所有端度数都相同的连通图为正则图 d(vi)=常数（i=1，2，n） 正则图是连通性最均匀的图 (3)尤拉图(euler): 端度数均为偶数的连通图为尤拉图。 尤拉图的性质: 尤拉图存在一个含所有的边且每边仅含一次的环.(4) 两部图 两部图的端点集合分为

6、两个部分, 所有边的端点分别在这两个集合中. 完全两部图km,n(5)2.1.3树:树是图论中一个很简单，但是又很重要的概念，在图论中运用是十分重要的。图的定义有多种, 如下面的定义：1、 任何二端有径且只有一条径的图称为树。2、 无圈的连通图称为树.我们采用第2种关于图的定义方式, 也就是:树: 无圈的连通图称为树.树有以下性质: 1.树是最小连通图，树中去一边则成为非连通图。 2.树中一定无环。任何二端有径的图是连通图，而只有一条径就不能有环。 3.树的边数m和端数n满足m=n-1 此式可以用数学归纳法证明。 4.除单点树，至少有两个度数为1的端(悬挂点) 树上的边称为树枝 (branch

7、)定理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个树有个点，则，与q = p-1相矛盾；3）1），p=1时，显然。设，t连通，且q=p-1，首先易证t有悬挂点，不然，与q = p-1相矛盾；然后对点数进行归纳即可；定理2.2：若t是树，则：（1）t是连通图，去掉任何一条边，图便分成两个且仅仅两个分图；（2）t是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。同时，若无向图满足（1）和（2），则t是

8、树。定理2.3：设t是树，则任何两点之间恰好有一条道路；反之，如图t中任何两点之间恰好有一条道路，则t为树。 定理2.2和2.3刻画了树的两个重要特征，事实上定理2.3也为图提供了另一个等价定义。上述两个定理的证明请读者自行完成。支撑树(spanning tree)： 考虑树t是连通图g的子图，tg，且t包含g的所有端，称t是g的支撑树。 由定义可知，只有连通图才有支撑树；反之有支撑树的图必为连通图。一般支撑树不止一个， 连通图至少有一个支撑树。支撑树上任二端间添加一条树支以外的边，则形成环(circuit)。支撑树外任一边称支撑树的连枝，连枝的边集称为连枝集或树补(cotree)。不同支撑树

9、对应不同连枝集。 对非连通图来说，它可以分成k个最大连通子图，即k个“部分”，每部分各有支撑树。k个支撑树的集合形成图g的主林，其余的边为林补。主林的边数称为图的阶，用r表示。主林的连枝数称为空度，用m表示。有如下关系式： n=n1+n2+nk r=( n1-1)+ ( n2-1)+ + ( nk-1)=n-k m=m-n+k 例如： k=3； r=11-3=8； m=12-11+3=42.1.4割(cut) 割指的是某些子集(端集或边集)。对连通图，去掉此类子集，变为不连通。对非连通图，去掉此类子集，其部分数增加。 割分为割端集与割边集。1、割端与端集 设v是图g的一个端，去掉v和其关联边后

10、，g的部分数增加，则称v是图g的割端。去掉几个端后，g的部分数增加，这些端的集合称为割端集。有的连通图无割端，这种图称为不可分图。 对于连通图, 在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集，其任意真子集不为割集。 最小割端集的端数目，称为图的联结度。联结度越大，图的连通性愈不易被破坏。2、割边集与割集 连通图g的边子集s，去掉s使g为不连通，称s为割边集 在众多的割集中边数最少的割集，称为最小割边集。最小割边集的任一真子集不为割边集。最小割集的边数，称为结合度. 结合度同样表示图的连通程度，结合度越高，连通程度越好。3、基本割集与基本环（针对连通图讨论）1） 基本

11、割集设t为连通图g的一个支撑树，取支撑树的一边（枝）与某些连枝，定可构成一个极小边割集，此割集称为基本割集。即：基本割集是含支撑树t之一个树枝的割集。基本割集有n-1个.下面一个图来理解基本割集. 支撑树t= 连枝：， 则基本割集：（，）， (，)，(，)， (，)2）基本环t为连通图g的一个支撑树，g-t的边集为连枝集。取一连枝可与某些树枝构成环。这种包含唯一连枝的环称基本环。每个基本环只包含一个连枝-与连枝一一对应，其数目=连枝数，共m-n+1个。环和运算: 对于集合, 这个运算的意义为对称差运算.通过环和运算, 由基本割集和基本环可以生成新的环和割集或它们的并集,事实上可以生成所有的环和

12、割集. 例2.2 通过基本环和基本割集理解基尔霍夫定律. 下面的图理解基本环. 连枝集 ， ：， ：， ：， ：，2.1.5 图的平面性图g若可以在一个平面上实现，除端点以外，任何两条边均无其他交点，则称g是平面图。当平面图有一个平面实现后，它把全平面分成s个区域（含包含无穷远点的开区域）。注意一个图为平面图等效于能够在球面上有一个几何实现.设连通平面图有m边，n端，则s=m-n+2，此为著名的euler公式。这个性质可以用数学归纳法证明或树的性质证明。 m=4，n=4，s=2定理2.4：简单连通图为平面图的必要条件是:m=3)上述结论可以推广到有重边和自环的情形. 证：形成区域至少3边，区域

13、周线上的边数至少3s(不考虑区域共边)，实际每边均在二区域周线上，最多有2m边（周线上）。考虑区域共边，有2m3s，代入euler公式得m3n-6.此为平面图的必要，非充分条件。例2.3 讨论完全图k5和完全两部图k3,3的平面性.定理2.5连通两部图为平面图的必要条件是:m+4 =3)根据每个平面图g=（v，e），可以生成一个对偶图g。g的每个平面对应于g的每个顶点，g中相邻的两个面在g中有一些边与g中的两个面的每一条边界的边相交，如下图所示。但是简单平面图的对偶图可能不再是简单图。 定理2.6 图g为平面图当且仅当g不含k5和k3,3或它们的细分图为子图.2.1.6图的矩阵表示 很多时候，

14、需要将图表示在计算机中，这就有了图的矩阵表示。下面主要介绍关联阵和邻接阵。1 关联阵设图g有n个端，m条边，则全关联阵 ；端vi对应于矩阵的第 i行(共n行)；边ej对应于第j 列(共m列);其中: 下面是一个例子说明关联矩阵, 例2.4 由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， 再去掉任一行

15、，得到关联阵a，为n-1m阶。a中的每一个非奇异方阵对应一个支撑树。图g的支撑树数目可由以下方法得到：定理2.7(矩阵-树定理)用at表示a的转置, 无向图g的主树数目t(g) = det(aat)，注意上面的定理计算的主树数目为标号树的数目; 同时n-1阶矩阵det(aat)可以直接写出, 主对角线的元素为相应端点的度数, 其余位置为-1或0, 而这取决于相应的端点之间是否有边.例2.5 t(kn) = , t(kn,m) = mn-1nm-1.t(kn) = 的计算如下： 继续例2.4: 共有8种支撑树如下 2.邻接阵邻接阵是表征图的端与端关系的矩阵，其行和列都与端相对应。令g=（v，e）

16、是m端，n边的有向图，其邻接阵 其中， 如： 对于无向图 ，因此是邻接阵为对称阵。我们可以通过对c的一些计算，得到图g的性质。如：计算c的幂次可得到关于转接径长的一些信息。若cij(2)=1则存在k，使cik ckj =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的径，但是经过转接的端

17、可能重复。已知图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的一些结果。某些图论知识在以后应用是会在介绍。2.2 最短径问题 上节

18、中介绍的图只考虑了图顶点之间的关联性，本节将要对图的边和端赋予权值，讨论有权图。权值在各种各样实际问题中有不同的实际意义，如费用，几何距离，容量等等。本节将介绍一些算法，大部分算法可借助计算机实现。2.2.1 最短支撑树给定连通图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个边

19、（树枝）的权和最小，步骤如下： p0:任取一端v1，子图g1=v1，在g1到g-g1中取最小的dij 得子图g2= v1， v2p1:求g3 得子图g3= v1，v2，v3 pr-2:从gr-1求gr 得子图gr= v1，v2，vr pr-1:重复pr-2，直至得到gn为止例2.5: g1=v1g2=v1，v3g3=v1，v3，v6g4=v1，v3，v6，v7g5=v1，v3，v6，v7，v2g6=v1，v3，v6，v7，v2，v5g7=v1，v3，v6，v7，v2，v5，v4则w(t)=15 可以看出， prim算法第k步运算，是以gk作为整体寻找至g-gk的最短边，每次并入gk的边总是保持

20、余下m-k+1个中最短的，因此算法终止时，所得的支撑树为最短者(可用数学归纳法证明)。 从算法始至终止，共进行n-1步，每步从k个端与n-k个端比较，须经k(n-k)-1次，可得总计算量 约为n3量级。当n很大时，可借助计算机实现。另一个算法由kruskal在1956年提出:设g(k)是g的无圈支撑子图,开始g(0)=(v,f)。若g(k)是连通的,则它是最小支撑树；若g(k)不连通,取e(k)为这样的一边,它的两个端点分属g(k)的两个不同连通分图,并且权最小。令g(k+1)= g(k)+ e(k),重复上述过程。上面算法的实现过程需要排序算法；rosenstiehl和管梅谷提出了另一个算法

21、：设g(k)是g的连通支撑子图，开始g(0)=g，若g(k)中不含圈，则它是最小支撑树；若g(k)中包含圈，设m是g(k)中的一个圈，取m上的一条权最大的边e(k)，令g(k+1)= g(k)-e(k)，重复上述过程。上面算法的实现过程需要解决如小问题：对于一个无向图g, 如何寻找其中的圈?可以通过搜索图中度为1的顶点而逐步简化.上面算法的实施过程,都是一种贪心法原理的应用; 从局部最优的结果中寻找全局最优的结果.问题如果复杂, 这种方法一般只能找到准最优解.2) 有限制情况 在许多情况下，不但要求最短支撑树，还要求一些额外条件。有两种解决此类问题的方法穷举法和调整法。穷举法就是先把图中的支撑

22、树穷举出来，按条件逐个筛选，最后选出最短支撑树。这种方法较直观，但很烦琐。下面讨论调整法。以esau-william算法为例(解决一种特定的问题):问题:图g有n个站,其中已知v1是主机，已知各边间距离dij，以及各个端站的业务量fi（i，j=1，2，n），要求任端至v1的径边数k(即限转接次数 d(i)+cij then begind(j):= d(i)+ cijpred(j):=i；if jlist, then 将j并入list;end; end; end; 上面的算法中没有指明list的结构, 如果将list组织为一个队列, 算法效率会更高, 计算复杂度为o(nm), 大约为目前最快的算

23、法, 上面两个算法的解决思路的比较是很有意义的。值得注意的是，如果附加一些条件，那么问题便很复杂了。如果边有两个权,相应的算法就复杂的多, 并且很可能无多项式算法.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)=minwij(k-1)，wi

24、k(k-1)+ wkj(k-1) f2：若kn，重复；k=n终止。上面的路由方法为前向路由，容易更改算法使它的路由为回溯路由; 算法要执行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算法计算量 : wij(k)=minwij(k-1)，wik(k-1)+ wkj(k-1)中，每定一k值，求w

25、ij经1次加，1次比较，求一次迭代为n2次加，n2次比较，共n个迭代，所以其运算量为n3级; 显然比重复使用dijkstra算法效率高，同时存储效率也要高。对于floyd算法, 同样提出若干问题如下: 1 如果端点有权如何处理? 2 如果边的权可正可负, 算法是否仍然有效? 3 算法是否对有向图也适用？例2.7 给定一个无向图g, 求任意两端之间最少转接次数和路由.例2.8图有六个端，端点之间的有向距离矩阵如下：1. 用d算法求v1到所有其他端的最短径长及其路径。2. 用f算法求最短径矩阵和路由矩阵，并找到v2至v4和v1至v5的最短径长及路由。3. 求图的中心和中点。解：1. d算法v1v2

26、v3v4v5v6指定最短径长,路由0v1w10, 19 1 3v3w131, 193 2 v5w152, 38 3 7v4w143, 18 7 v3w167, 5 8 v2w128, 52. f算法最短路径矩阵及最短路由阵为w5，r5有向距离为4有向距离为23. 中心为v3或v5中点为v2 在实际问题中，除了求最短径外，如当主路由（最短径）上业务量溢出或故障时，需寻求次短径或可用径。次短径指备用径，可用径指一批满足某种限制条件的径（如限径长，限转接次数.）。但这些问题一般没有多项式算法, 可以根据实际情况采用某种贪心策略获得近似解.3、网的中心与中点如网络用图g=(v, e)表示, 根据flo

27、yd算法的计算结果可以定义网络的中心和中点.中心:对每个端点i, 先求 此值最小的端称为网的中心，即满足下式的端i*： =网的中心宜做维修中心和服务中心。中点:将“平均最短径长”最小的端，定义为中点，先计算 si = , 然后求出si的最小值, 相应的端点为中点. 网的中点可用做全网的交换中心。2.3网络流量问题 网络的目的是把一定的业务流从源端送到宿端。流量分配的优劣将直接关系到网络的使用效率和相应的经济效益。网络的流量分配受限于网络的拓扑结构，边和端的容量以及路由规划。本节及下节中关于流量的内容均在有向图上考虑，并且均是单商品流问题，即网络中需要输出的只有一种商品或业务。通信网络的服务对象

28、有随机性的特点, 关于通信业务随机性特点将在下一章中考虑, 本节中假设网络源和宿的流量为常量.2.3.1基本概念 给定一个有向图g=（v，e），c(e)是定义在e上一个非负函数，称为容量；对边eij，边容量为cij ，表示每条边能通过的最大流量。设f= fij 是上述网络的一个流，若能满足下述二限制条件，称为可行流。 a)非负有界性：0fijcij； b)连续性: 对端vi有： v(f) = f为源宿间流fij的总流量.式中 （vi）=vj: ( vi， vj)e 流出vi的边的末端集合; (vi)=vj: ( vj， vi)e 流入vi的边的始端集合; 有n个连续性条件，共有2m+n个限制条

29、件，满足上述二限制条件的流称为可行流。 需要解决的问题分为两类: 1 最大流问题 在确定流的源和宿的情况下, 求一个可行流f, 使v(f) = f为最大; 2 最小费用流问题 如果边(i,j)的单位流费用为di,j , 流f的费用为: 所谓最小费用流问题: 在确定流的源和宿的情况下, 求一个可行流f, 使为最小. 下面介绍割量和可增流路的概念. 设x是v的真子集，且vsx，vtxc，（x，xc）表示起点和终点分别在x和xc的边集合，这个集合当然为一个割集,割集的正方向为从vs到vt。割量定义为这个割集中边容量的和: 对可行流fij: f(x，xc)表示前向边的流量（和）fij, 其中vix，v

30、jxc f(xc，x)表示反向边的流量 (和) fji, 其中vix，vjxc则源为vs宿为vt的任意流f有:(1) v(f)=f(x,xc)-f(xc,x), 其中vsx，vtxc证明： 对任vix : 对所有vix,求和上式： 源端 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) fc(x,xc)由（1）及f(x, xc)非负，可得：下面讨论可增流路的概念。 从端s到端t的一个路，有一个自然的正方向，然

31、后将路上的边分为两类：前向边集合和反向边集合。对于某条流，若在某条路中，前向边均不饱和（fijcij），反向边均有非0流量（fij0），称这条路为可增流路径（或增广链）。在可增流路上增流不影响连续性条件，也不改变其它边上的流量，同时可以使从源端到宿端的流量增大。 若流 fi,j 已达最大流，f则从源至宿端的每条路都不可能是可增流路，即每条路至少含一个饱和的前向边或流量为0的反向边。2.3.2 最大流问题 所谓最大流问题，在确定流的源端和宿端的情况下, 求一个可行流f, 使v(f) 为最大。对于一个网络，求最大流的方法采用可增流路的方法，下面的定理2.9为这种方法提供了保证. 如果网络为图g =

32、 (v, e),源端为vs, 宿端为vt.定理2.9 (最大流-最小割定理)可行流f* = 为最大流当且仅当g中不存在从vs 到vt的可增流路.证明: 必要性: 设f*为最大流,如果g中存在关于f*的从vs 到vt的可增流路.令 0 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 已标，则沿该可增流路增流

33、。m4: 返回m1。 上面的算法是针对有向图且端无限制的情况。若是有无向边，端容量及多源多宿的情况，可以进行一些变换，化为上述标准情形。 若端i和端j之间为无向边，容量为ci,j，那么将它们化为一对单向边(i，j)和(j，i)，并且它们的容量均为ci,j。 如果端i有转接容量限制ci，那么将vi 化为一对顶点，原终结于vi的边全部终结于，原起始于vi的边均起始于，且从至有一条边容量为ci。 对多源多宿的情况，设原有源为，原有宿为，要求从源集到宿集的最大流量，可以虚拟一个新的源和新的宿，源到的各边容量均为无限大，到宿的各边容量也为无限大，这样多源多宿的问题就化为从到的最大流问题。见下图：仔细考虑

34、一下会发现，前面介绍的算法在任何网络中是否一定会收敛，也就是说会不会不断有增流路，但却不收敛于最大流呢？如果边的容量均为有理数，是不会出现这种情况，也就是说一定会收敛。但若边的容量为无理数，就不一定收敛。对于计算量的问题, ford和fulkerson曾给出下面的例子。如图所示，一个四个节点的网络，求至的最大流量。假设按前述算法，并且按如下顺序从f=0开始增流：例2.8；;显然，这样需要2n+1步增流才能找到的最大流，流量为2n+1。这个例子说明前述算法虽然能够达到最大流，但是由于没有指明增流方向，导致有可能象这个例子一样，效率很低，这个例的计算工作量与边容量有关。1972年，edmonds和karp 修改了上述算法, 在m2步骤时采用fifo原则(在选哪个端查时), 从而解决了这个问题；新算法一方面收敛, 同时也为多项式算法. 后来，人们提出了许多改进的算法，如dini