第七章 图与网络规划

1、第七章第七章 图与网络分析图与网络分析图论（Theory of Graphs 或 Graph Theory ）是决策科学，特别是运筹学中应用十分广泛的一个分支，它已广泛的应用在经济学、管理学、物理学、化学、控制论、信息论和电子计算机等领域。在现实生活、生产和科学研究中，很多问题可以用图论的理论和方法来解决。图论的起源最早可追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。近年来，随着科学技术的进步和电子计算机的蓬勃发展，图论得到了进一步发展。特别是，图论被应用于网络分析中所产生的最小树问题、最短路问题、最大流问题、运输问题、分配问题以及旅行售货员和中国邮路等问题。解决了

2、很多庞大而复杂的工程系统设计和管理决策的最优化问题，受到了数学、工程技术及经营管理等各个领域越来越广泛的重视。网络模型就是一种应用图论的理论和方法解决具有网络性质的管理决策问题的数学模型。由于它具有图形直观、方法简便、容易掌握的特点，一次得到迅速的发展，且广泛地应用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等。第七章第七章 图与网络规划图与网络规划7.1. 图的基本概念图的基本概念7.2. 最小树问题最小树问题7.3. 最短路问题最短路问题7.4. 最大流问题最大流问题本本章章内内容容学习目的：1、理解图及相关的概念。2、掌握树、最短路、最大流的特点及功能

3、。3、熟练掌握以上问题的求解方法，并能对求解结果做简单分析。引引 言言 图论是应用十分广泛的运筹学分图论是应用十分广泛的运筹学分支，它已广泛地应用在物理学、化学、支，它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产算机等各个领域。在实际生活、生产科学研究中，有很多问题可以用图论科学研究中，有很多问题可以用图论的理论和方法来解决。图论的概念和的理论和方法来解决。图论的概念和结果来源非常广泛，既有来自生产实结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。践的问题，也有来自理论研究的问题。我们把图论在系统

4、管理决策中卓有成我们把图论在系统管理决策中卓有成效的一些理论和方法称之为效的一些理论和方法称之为网络规划。网络规划。 在哥尼斯堡城中有一条河叫普雷格尔河，在哥尼斯堡城中有一条河叫普雷格尔河，河上有七座桥连接两岸及河中的两个岛（如河上有七座桥连接两岸及河中的两个岛（如图图1所示）。所示）。 图图 1 图图 2 例：七桥问题问题：一个散步者能否走过七座桥，且每座桥只走问题：一个散步者能否走过七座桥，且每座桥只走 过一次，最后回到出发点。过一次，最后回到出发点。当问题被提到的数学教授当问题被提到的数学教授Euler面前，它把每块地面前，它把每块地用一个点代替，把每座桥用连接对应点的一条边用一个点代替

5、，把每座桥用连接对应点的一条边代替，把问题抽象为代替，把问题抽象为 图图 2中的图。提出了判断一中的图。提出了判断一般图存在这种走法的充要条件，并给出了必要性般图存在这种走法的充要条件，并给出了必要性的证明。的证明。问题：能否从某一点开始一笔画出这个图形，最后问题：能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。回到原点，而不重复。Leonhard Euler (1707-1783) 例：中国邮路问题例：中国邮路问题 一个邮递员送信，要走完他所负责的全部街道分送一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的信件，最后返回邮局。邮递员都会本

6、能地以尽可能少的行程完成送信任务。行程完成送信任务。问题：问题：他如何走？他如何走？点：路口；点：路口；边：两路口之间道路，第边：两路口之间道路，第 i 条道路长条道路长 ei。问题：求一个圈，过每边至少一次，并使圈的长度最问题：求一个圈，过每边至少一次，并使圈的长度最 短。短。 第一节第一节 图的基本概念图的基本概念点：研究对象（陆地、路口、国家、球队）；点：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路口点间连线：对象之间的特定关系（陆地间有桥、路口 之间道路、两国边界、两球队比赛及结果之间道路、两国边界、两球队比赛及结果)。对称关系：桥、道路、边界；对称

7、关系：桥、道路、边界；用不带箭头的连线表示，称为边。用不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示，非对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。称为弧。 如果用如果用 V 点表示研究对象，用点表示研究对象，用 E 边表示这些边表示这些对象之间的联系，则图对象之间的联系，则图 G 可以定义为点和边可以定义为点和边的集合，记作的集合，记作 G=V，E其中其中 V= vi 称为点集，称为点集，vi为点为点 。 E=ek称为边集，称为边集， ek为边（或弧）。为边（或弧）。 当当V，E为有限集时，称为有限集时，称G为有限图。否则称为为有限图。否则称为 无无限图。限图

8、。 边：边：两点之间的不带箭头的连线；两点之间的不带箭头的连线； 弧：弧：两点之间带箭头的连线；两点之间带箭头的连线； 无向图：无向图：由点和边构成；由点和边构成； 有向图：有向图：由点和弧构成；由点和弧构成； 混合图混合图：既有边又有弧的图；：既有边又有弧的图；下面通过图7.2让我们对图有一个感性的认识 图图G中点集中点集V的顶点个数，记为的顶点个数，记为p (G) ，边数记为，边数记为q(G),简记简记p，q。无向图无向图有向图有向图图7.2图中，图中，V=v1、v2、v3、v4、 v5、v6；E=e1、e2、e3、e4、e5、e6、e7。 我们记：我们记：p=|V|表示图表示图G的顶点数

9、，的顶点数，q=|E|表示图表示图G的边数，其中的边数，其中p0，q0，且均为整数。，且均为整数。 图中图中p=6，q =7。端点，关联边，相邻端点，关联边，相邻 若边若边e=vi，vjE，称，称vi ， vj 是是e的端点，也称的端点，也称vi ， vj是相邻的。称是相邻的。称 e是点是点 vi （及点（及点vj ）的关联边。）的关联边。 若两条边有一个公共的端点，则称这两条边相邻接。若两条边有一个公共的端点，则称这两条边相邻接。vivjevi，vj相邻相邻 e 与与vi，vj关联关联点与点点与点相邻相邻点与边关联点与边关联vie1e1 与与e2相邻相邻vjvke2边与边相邻接边与边相邻接两

10、点之间恰有一条边相关联，则两点之间恰有一条边相关联，则称图称图G为完备图。为完备图。次，奇点，偶点，孤立点次，奇点，偶点，孤立点 与某一个点相关联的边的条数称为点的次（也叫做度或线与某一个点相关联的边的条数称为点的次（也叫做度或线度），记做度），记做d（vi）。图中）。图中 d(v1)=3, d(v2)=4。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数的点称作次为偶数的点称作偶点偶点，次为次为 0 的点称作的点称作孤立点孤立点。定理定理1 图图G=（V，E）中，所有点的次之和为边数）中，所有点的次之和为边数的两倍，的两倍， 即即Vv2qd(v) 环，多重边，简单图环，多重边，简单图 若边

11、若边 e 的两个端点相同，则称的两个端点相同，则称e为环，为环，图图6.3中，中，e2 环。环。若两个端点有多于一条的边，则称这些边为多重边，图若两个端点有多于一条的边，则称这些边为多重边，图6.3中，中，e3和和 e4是端点是端点v1 和和v3的多重边。的多重边。一个无环、无多重边的图称为一个无环、无多重边的图称为简单图简单图，一个无环但有多重边的图称为一个无环但有多重边的图称为多重图。多重图。链（闭链，开链），圈，路，回路，连通图链（闭链，开链），圈，路，回路，连通图 图中有些点和边的交替序列图中有些点和边的交替序列若其中各边若其中各边 互不相同，且任意互不相同，且任意 和和 （2tk）均

12、相邻，称）均相邻，称 为为链链。若若k0，且，且v0vk，则称，则称 为为闭链闭链，当当v0不等于不等于 vk 时，称为时，称为 开链开链。如果链中所有的顶点也不相同，这样的链称为如果链中所有的顶点也不相同，这样的链称为路路011,kkv e ve v12,ke ee1itv，itv初等链：链中点都不同。初等链：链中点都不同。简单链：链中边都不同。简单链：链中边都不同。对起点与终点相重合的链称做对起点与终点相重合的链称做圈圈，起点与终点重合的路称做，起点与终点重合的路称做回路回路。若在一个图中，如果每一对顶点之间至少存在一条链，称这样的若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图

13、为图为连通图连通图，否则称该图为不连通图。，否则称该图为不连通图。若若G是不连通图，它的每个连通的部分称为是不连通图，它的每个连通的部分称为G的一个连通分图。的一个连通分图。如图如图 6.3 是个不连通图，它有两个连通分图。是个不连通图，它有两个连通分图。链和路的区别7-2子图、部分图（支撑子图）子图、部分图（支撑子图）定义定义2 给定图给定图G=（V，E），若图），若图G=（V，E），其），其 中中V V， E E，则称，则称 G 是是 G 的子图。的子图。 定义定义3 给定图给定图G=（V，E），若图），若图 G=（V，E），）， 其其中中 E E，则称，则称 G 是是 G的一个（部分图）

14、支撑子图。的一个（部分图）支撑子图。 （a）（b）（c）子图子图支撑子图支撑子图点全部保留点全部保留注意：注意：部分图也是子图，但子图不一定是部分图部分图也是子图，但子图不一定是部分图 网络图网络图 给点和边（弧）赋以具体的含义和权数给点和边（弧）赋以具体的含义和权数的图的图 第二节第二节 最小树问题最小树问题 在各式各样的图中，有一类图是极其简单在各式各样的图中，有一类图是极其简单然而却是很有用的，这就是树图。然而却是很有用的，这就是树图。树图的定义树图的定义是无圈的连通图。是无圈的连通图。这类图与大自然中树的特征这类图与大自然中树的特征相似，因而得名树图。管理组织机构、学科分相似，因而得名

15、树图。管理组织机构、学科分类和一些决策过程往往都可以用树图的形式表类和一些决策过程往往都可以用树图的形式表示。示。 举一个现实生活中的例子，五个城市，要举一个现实生活中的例子，五个城市，要在它们之间架设电话线，要求任何两个城市都在它们之间架设电话线，要求任何两个城市都可以互相通话，并且电话线的根数最少。可以互相通话，并且电话线的根数最少。 用五个点代表五个城市，如果在某两个城用五个点代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话线网就可以用间连一条边，这样一个电话线网就可以用一个图来表示了。为了使任何两个城市都一个图

16、来表示了。为了使任何两个城市都可以通话，这样的图必须是连通的。其次，可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一条余下的图仍是连通的，这样可以省去一条电话线。因而，满足要求的电话线网所对电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图应的图必定是不含圈的连通图。图 6.8 代表代表了满足要求的一个电话线网。了满足要求的一个电话线网。 图图7-4 基本概念基本概念 树树无回路且连通的无向图无回路且连通的无向图 G 称为树，树称为树，树中的边称为枝。中的边称为枝。 生成树生成树

17、若若 T 是无向图是无向图 G 的生成子图，且的生成子图，且 T 又是树，则称又是树，则称 T 是是 G 的生成树。的生成树。 根树根树给树给树T，若顶点，若顶点 x 至至 T 中其他顶点中其他顶点u都恰有一条初等链，则称都恰有一条初等链，则称 T 为以为以 x 为根的根为根的根树。树。（无圈的连通图称为树。树一般用无圈的连通图称为树。树一般用T表示表示）定理定理2 图图T=（V，E），）， p=n， q=m，则下列关于，则下列关于 树的说法是等价的。树的说法是等价的。（1）T是一个树。（连通且无回路）是一个树。（连通且无回路） （2）T无回路，且无回路，且m=n-1。 （3）T连通，且连通，

18、且m=n-1。边数边数=点数点数-1 （4）T无圈，但每加一条新边即得唯一一个圈。无圈，但每加一条新边即得唯一一个圈。 （5）T连通，但每丢掉一条边就不连通。连通，但每丢掉一条边就不连通。 （6）T中任意两点，有唯一链相连。中任意两点，有唯一链相连。证明：略证明：略最小支撑树最小支撑树 如果如果 G1 是是 G2 的部分图，又是树图，则称的部分图，又是树图，则称G1是是G2的支撑树。图的支撑树。图7-5（b）是（）是（a ）的一个支撑）的一个支撑树。树图的各条边称为树枝（假定各边都有权树。树图的各条边称为树枝（假定各边都有权重），一般图含有多个支撑树，设重），一般图含有多个支撑树，设 T 是是

19、 G 的一的一棵支撑子树，称棵支撑子树，称 T 中所有边的权之和为支撑树中所有边的权之和为支撑树 T 的权，记为的权，记为w(T)，如果支撑树，如果支撑树 T* 权权 W(T*) 是是 G 所有支撑树的权中最小的，则所有支撑树的权中最小的，则 T* 称为称为 G 的最的最小支撑树小支撑树(简称为最小树简称为最小树minimum spanning tree）。）。图图7-5（b）是（）是（a）的一个支撑树。）的一个支撑树。 （a） （b） 图7-5定理定理3 图图 G 有支撑树的充分必要条件是图有支撑树的充分必要条件是图G是连通的。是连通的。求一个赋权连通图求一个赋权连通图 G 的最小支撑树问题

20、称为的最小支撑树问题称为最小树问题最小树问题。求。求最小树的方法有两种：最小树的方法有两种：破圈法破圈法 在图在图G中任取一个圈中任取一个圈,去掉圈上权最大的一条边去掉圈上权最大的一条边,反复反复进行进行,直到没有圈为止。直到没有圈为止。避圈法避圈法下面分别给出两种方法的具体步骤避圈法避圈法-步骤步骤. 从图中任选一点从图中任选一点vi ，让让 vi V, 图中其余的点属于V；. 从从V与V中的连线中找出最小边，这条边一定包含在最小支撑树内，不妨设最小边为(vi ,vj ), 将(vi ,vj )加粗，以标记是最小部分树内的边；. 令令V vj V ， V vj V ；. 重复重复 、 两步，

21、一直两步，一直到图中所有点均包含在V中为止。例例7.2 如图如图7-6，S,A,B,C,D,E,T代表村镇，它们之间连线表明各代表村镇，它们之间连线表明各村镇间现有道路交通情况，连线旁数字代表道路的长度。现要村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使每个村庄都通上电，应如何架设使求沿图中道路架设电线，使每个村庄都通上电，应如何架设使总的线路长度为最短。总的线路长度为最短。图 7-6V破圈法破圈法aVbVcVdV图 f 中加粗的边即为该网络的最小支撑树破圈法破圈法详细过程看图 (a) (f) 。eVfVBSDTAEC272541431557BSDTAEC272

22、54143155(a)N1BSDTAEC2725414315(b)N2BSDTAEC225414315(c)N3BSDTAEC22541315(d)N4BSDTAEC2241315(e)N5BSDTAEC221315(f)N6作业：P225， 3 第三节第三节 最短路问题最短路问题有一批货物要从有一批货物要从 v1运到运到 v6。这两点间的路线如图所示，每条。这两点间的路线如图所示，每条弧旁边的数字表示该弧的长度。总路径最短，那么运输费用弧旁边的数字表示该弧的长度。总路径最短，那么运输费用也就越小。为节省运输费用，应该怎样选择运输路线呢？也就越小。为节省运输费用，应该怎样选择运输路线呢？ 引例

23、最短路问题在实际中具有广泛的应用，如管道铺设、线路选择最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题路问题 最短路问题是对一个赋权的有向图最短路问题是对一个赋权的有向图 D, 若若 D 的每条弧都对应的每条弧都对应一个实数一个实数 w(e)（称为（称为e的权）的权）,求出图中的指定的两个点求出图中的指定的两个点 Vs和和 Vt，找到一条从，找到一条从 Vs 到到 Vt 的路，使得这条路上所有弧的的路，使得这条路上所有弧的权数权数 w(e) 的和最小，这条路被称为的和最小，这

24、条路被称为 Vs 到到 Vt 的的最短路最短路，这，这条路上所有弧的权数的和被称之为条路上所有弧的权数的和被称之为从从 Vs 到到 Vt 的距离的距离。求最短路有两种算法： 一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra) 算法 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。6.3.1 Dijkstra算法算法 当所有当所有 wij 0 时，时，本算法是用来本算法是用来求给定点求给定点 vs到任到任一个点一个点 vt 最短路最短路的公认的最好方法。的公认的最好方法。事实：如果事实：如果 P 是是D 中从中从 vs 到到 vt 的最短路，的最短路，vi

25、是是P中中的一个点，那么，从的一个点，那么，从 vs 沿沿 P到到 vi 的路是从的路是从 vs 到到 vi 的的最短路。最短路。 最短路的子路也是最短路。最短路的子路也是最短路。 若用若用 dij 表示图中两相邻点表示图中两相邻点 i 与与 j 的距离，若的距离，若 i与与 j不相邻，不相邻，令令 dij=，显然，显然 dii=0，若用，若用 Lsi 表示从表示从 s 点到点到 i 点的最短距点的最短距离，现要求从离，现要求从 s 点到某一点点到某一点 t 的最短路，用的最短路，用 Dijkstra 算法算法的步骤如下的步骤如下:狄克斯屈拉(Dijkstra)算法步骤 （1）从点）从点 s

26、出发，因出发，因 Lss=0，将此值标注在，将此值标注在 s 旁的小方框旁的小方框内，表示内，表示 s 点已标号；点已标号； （2）从）从 s 点出发，点出发，找出与找出与 s 相邻的点中距离最小相邻的点中距离最小的一个，的一个，设为设为 r。将。将 Lsr= Lss+dsr 的值标注在的值标注在 r 旁的小方框内，表明旁的小方框内，表明点点 r 也已标号；也已标号； （3）从已标号的点出发，找出与这些点相邻的所有未标）从已标号的点出发，找出与这些点相邻的所有未标号点号点 p。若有。若有 Lsp=min Lss+dsp; Lsr+ drp , 则对则对 p 点标号，点标号，并将并将 Lsp 的

27、值标注在的值标注在 p 点旁的小方框内；点旁的小方框内； （4）重复第重复第 3 步，一直到步，一直到 t 点得到标号为止。点得到标号为止。例7-2 下图是一段高速公路网络，求该图中v1 到v7的最短路。图7-100a02b025cd5026e502677f50267107Dijkstra 算法提供了从网络图中某一点到其他点的算法提供了从网络图中某一点到其他点的最短距离。但实际问题中往往要求网络任意两点之最短距离。但实际问题中往往要求网络任意两点之间的最短距离，如果仍采用间的最短距离，如果仍采用 Dijkstra 算法对各点分算法对各点分别计算，就显得很麻烦。别计算，就显得很麻烦。Floyed

28、 算法还有判断和寻算法还有判断和寻找图中负回路的功能找图中负回路的功能6.3.2 求任意两点间最短距离的矩阵算法求任意两点间最短距离的矩阵算法Floyed (弗洛伊德)算法步骤算法步骤 (自学自学) 下面用例下面用例7.3介绍矩阵算法的具体步骤：介绍矩阵算法的具体步骤： 定义图中相邻两点的距离，若定义图中相邻两点的距离，若 i 与与 j 不相邻，不相邻，令令dij=，根据图，根据图7.15可以得到：可以得到： d11 d12 d13 d14 d15 d16 d17 0 5 2 d21 d22 d23 d24 d25 d26 d27 5 0 2 7 d31 d32 d33 d34 d35 d36

29、 d37 2 0 7 4 d41 d42 d43 d44 d45 d46 d47 = 2 7 0 6 2 d51 d52 d53 d54 d55 d56 d57 7 6 0 1 3d61 d62 d63 d64 d65 d66 d67 4 2 1 0 6d71 d72 d73 d74 d75 d76 d77 3 6 0 以上矩阵表明从点到点的直接最短距离。但从以上矩阵表明从点到点的直接最短距离。但从点点i到点到点j的最短路不一定是的最短路不一定是ij，可能是，可能是ilj，ilkj，或，或ilkj。先考虑。先考虑i与与j之之间有一个中间点的情况。间有一个中间点的情况。 如图如图6.16中中v1

30、v2的最短距离应为的最短距离应为mind11+d12, d12+d22, d13+d32, d14+ d42, d15+d52, d16+d62, d17+d72,也就是也就是 mind1r+dr2,为此可以构造一为此可以构造一个新的矩阵个新的矩阵D(1)，令，令D(1)中每个元素中每个元素 dij(1)= mindir+drj， 则矩阵则矩阵 D(1) 给出了网络中任意两点之间直接到给出了网络中任意两点之间直接到达和包括经一个中间点时的最短距离。达和包括经一个中间点时的最短距离。 再构造矩阵再构造矩阵D (2)，令，令dij (2) =dir (1) +drj (1) ，则则 D (2) 给

31、出网络中任意两点直接到达，经过一个、给出网络中任意两点直接到达，经过一个、两个、两个、到（、到（2k-1）个中间点时比较得到的）个中间点时比较得到的最短距离。最短距离。 设网络有设网络有 p个点，则一般计算到不超过个点，则一般计算到不超过D (k)， k的值按以上得到的矩阵计算：的值按以上得到的矩阵计算： 即即 (1)21221kkplg(1)1lg2pkk 如果计算中出现如果计算中出现 D(m+1) = D(m) 时，计算也可时，计算也可以结束，矩阵中以结束，矩阵中 D(m) 的各个元素值即为各的各个元素值即为各点之间最短距离。点之间最短距离。本例中本例中6 . 22lg6lg2lg) 1l

32、g(p，所以最多计算到，所以最多计算到 D(3)，计算过程如下：，计算过程如下：5 5 2 7 12 6 5 0 7 2 7 4 10 2 7 0 6 5 4 10 D (1) = 7 2 6 0 3 2 8 12 7 5 3 0 1 3 6 4 4 2 1 0 4 10 10 8 3 4 0 5 5 2 7 7 6 12 5 0 7 2 5 4 10 2 7 0 6 5 4 8 D (2) = 7 2 6 0 3 2 6 7 5 5 3 0 1 3 6 4 4 2 1 0 4 12 10 8 6 3 4 0 作业：作业：P225, 4 5 5 2 7 7 6 10 5 0 7 2 5 4 8

33、 2 7 0 6 5 4 8 D (3) = 7 2 6 0 3 2 6 7 5 5 3 0 1 3 6 4 4 2 1 0 4 10 8 8 6 3 4 0 (3)D中的元素 dij(3)表明网络中从 i 点 j 的最短距离(3)(4)DD 第四节第四节 最大流问题最大流问题许多系统中包含了流量问题，例如公路系统中有辆许多系统中包含了流量问题，例如公路系统中有辆流，控制系统中有信息流，供水系统中有水流，金流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流等等。融系统中有现金流等等。所谓的最大流问题就是：所谓的最大流问题就是：给了一个给了一个带收发点带收发点的网络，其每条弧的赋权称之

34、为的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。点到收点的最大流量。7.4.1基本概念和定理基本概念和定理（1）网络与流）网络与流 定义定义1 .给一个有向图给一个有向图 D=, 在在V中指定了中指定了一点，称为发点（记为一点，称为发点（记为 vs），和另一点，称为），和另一点，称为收点（记为收点（记为 vt），其余的点叫中间点。对于每），其余的点叫中间点。对于每一个弧一个弧 ,对应有一个对应有一个 （或简写为（或简写为 cij），称为弧的容量。通常我们），称为弧的容量。通常我们就把这样的就把这样的D 叫

35、作一个网络。记作叫作一个网络。记作D=（V，A，C）。）。 (,)ijAv v( ,) 0ijcv v 所谓所谓网络上的流网络上的流，是指定义在弧集合，是指定义在弧集合 A 上上的一个函数的一个函数 ,并称并称 为弧为弧 上的流量。上的流量。 (,)ijffv v(,)ijfv v(,)ijv v图7-18（2）可行流与最大流）可行流与最大流在运输网络的实际问题中，我们可以看出，在运输网络的实际问题中，我们可以看出，对于流有两个明显的要求：对于流有两个明显的要求：一一 是每个弧上的流量不能超过该弧的最大通是每个弧上的流量不能超过该弧的最大通过能力（即弧的容量）过能力（即弧的容量）；二二 是中间

36、点的流量为零。是中间点的流量为零。定义定义2. 满足下述条件的流满足下述条件的流 f 称称为可行流为可行流： （1） 容量限制条件：容量限制条件：对每一弧对每一弧 （2）平衡条件：）平衡条件： 对于中间点：流出量对于中间点：流出量=流入量，即对每个流入量，即对每个 i（i s , t）有）有 (,)ijAv v0ijijfc(,)(,)0ijjiijjivvAvvAff对于发点对于发点 vs，记记 于是对于收点于是对于收点 vt，(,)(,)( )sjjsvs vjAvj vsAv fff(,)(,)( )tjjtvt vjAvj vtAv fff 式中式中 v(f) 称为这个可行流的流量，即

37、发点的净输称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。出量（或收点的净输入量）。 对于一个网络，可行流总是存在的。（零流）对于一个网络，可行流总是存在的。（零流） 最大流问题就是求一个流最大流问题就是求一个流 fij 使其流量使其流量 v(f) 达到最大，并且满足：达到最大，并且满足： (1) (2)0ijijfc( ,)ijAv v( )()0( )ijjiv fisv fff（i s,t）i=t（3）割）割对于网络对于网络 ，若，若 S为为 V的一个的一个子集，子集， ， ，则称，则称边集边集为网络为网络 N 的一个割。的一个割。( , ,)NV E C x ySVS,xS

38、 yS( , ) |( , ),KS Se eu v u S v S（4）增广链）增广链若给一个可行流若给一个可行流 f=( fij )，给出下面的定义，给出下面的定义饱和弧饱和弧： fij= cij 的弧的弧 非饱和弧非饱和弧： fij cij 的弧的弧 零流弧零流弧： fij= 0 的弧的弧 非零流弧非零流弧： fij 0的弧的弧 定义定义3 设设 f 是一个可行流，是一个可行流， 是从是从 vs 到到 vt 的一的一条链，若条链，若 满足下列条件，称之为（关于可满足下列条件，称之为（关于可行流行流 f 的）一条的）一条增广链增广链。在弧在弧 上，上， ，即，即 中每中每一弧是非饱和弧。一

39、弧是非饱和弧。在弧在弧 上，上， ，即，即 中每中每一弧是非零流弧。一弧是非零流弧。 ( ,)ijv v( ,)ijv v0ijijfc 正向弧集合负向弧集合 0ijijfc（5）截集与截量）截集与截量定义定义4 给网络给网络 D=（V，A，G），若点集），若点集 V 被被割分为两个非空集合割分为两个非空集合 和和 ，使，使得得 ， ，则把弧集，则把弧集 称为称为是（分离是（分离 vs 和和 vt 的）截集。的）截集。 1V1V1tv V1svV11(, )V V定义定义5 给一截集给一截集 把截集把截集 中所有弧的中所有弧的容容量量之和成为这个截集的容量之和成为这个截集的容量 （简称为截量）

40、。（简称为截量）。记为记为 ，即，即11(,)V V11(,)V V11(,)CV V11(,) (V,V)(,)ijijv vCcV V可以证明，任何一个可行流的流量可以证明，任何一个可行流的流量 v(f) 都不都不会超过任一截集的容量，即会超过任一截集的容量，即11( )(,)v fCV V显然，若对于一个可行流显然，若对于一个可行流 f*, 网络中有一个网络中有一个截集截集 使使 ，则，则 f* 必是最大流，而且必是最大流，而且 必必是是 D 的所有截集中，容量最小的一个，即的所有截集中，容量最小的一个，即最小截集。最小截集。 *(,)V V*()(,)v fC V V*(,)V V若若

41、 f 为网络上的可行流，则有：为网络上的可行流，则有： （1）流）流 f 为网络上最大流的充要条件为网络上最大流的充要条件是网络中不存在是网络中不存在 f 的增广链。的增广链。 （2）若）若 f 为最大流，则其流量等于最为最大流，则其流量等于最小截集的容量。小截集的容量。关于最大流，有下面重要的结论：任何一个网络都有可行流，例如零流7.4.2 寻求最大流的标号（寻求最大流的标号（Ford,Fulkerson） 从一个可行流出发（从一个可行流出发（若网络中没有给定若网络中没有给定 f，则可以设则可以设 f 是零流是零流），经过标号过程与调整），经过标号过程与调整过程，就能求得最大流。过程，就能求

42、得最大流。(1) 标号过程标号过程（标号过程的目的是什么？标号过程的目的是什么？） 在这个过程中，网络中的点或者是标号点（又分在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点，为已检查和未检查两种），或者是未标号点，每个每个标号点的标号包含两个部分：第一个标号表明它的标号点的标号包含两个部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。标号是为确定增广链的调整量用的。 先给 vs 标上 (0, +), 这时vs 是标号的点，其余都是未标号的点。一般地，取一个标号而未检查

43、的点vi， 对其他没有标号且与 vi 相邻的点按下面规则进行标号：（1）若在弧 (vi , vj) 上， fijcij ， 则给vj 标号(vi , l(vj)。这里 l(vj)=minl(vi), cij - fij, 这时 vj 成为标号而未检查的点。（2）若在弧 (vj , vi) 上， fji0 ， 则给vj 标号(-vi , l(vj)。这里 l(vj)=minl(vi), fji, 这时 vj 成为标号而未检查的点。注：不满足上面两个条件之一的点，不标号(2) 调整过程调整过程去掉所有的标号，对新的可行流 , 重新进入标号过程, ( ,), ( ,), ( ,)ijijijijijijijfv vffv vfv v先按 vt 及其他点的第一个标号，利用“反向追踪” 的办法，找出增广链。例如 vt 的第一个标号是vk (或-vk)，则弧(vk, vt ) (或相应地(vt, vk ) )是 上的弧，接下来检查 vk 的第一个标号， 以此下去，直到 vs为止。这时被找出的弧就