(毕业设计论文)最大流问题及应用18045.pdf

《(毕业设计论文)最大流问题及应用18045.pdf》由会员分享，可在线阅读，更多相关《(毕业设计论文)最大流问题及应用18045.pdf（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.1/44 山 东 科 技 大 学 本科毕业设计（论文）题 目 最大流问题以与应用 学 院 名 称 数学与系统科学学院 专 业 班 级 信息与计算科学 2011 级 2 班 学 生 吕永强 学 号 201101051416 .2/44 摘要 网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据Ford-Fulkerson 最大流最小割定理；综述解决最大流问题的 几种算

2、法 Ford-Fulkerson 标号法、Edmonds-Karp 修正算法、Dinic 算法，并比较各算法在解决不同问题中的优劣。为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每 辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和 Ford-Fulkerson 标号法的算法依据，最终解决了问题。本文采用理论与 实例相结合，重在应用理论依据解决实际问题，具有较

3、强的实践性，突出的是应用。Abstract The network flow problem is an important operational research subject.The maximum flow problem is an important content of network flow problem,which has widely applications.The research of maximum flow problem and its applications to industry,engineering，commerce,.3/44 agricult

4、ure,transportation and other areas can bring us great convenience.The paper discusses the maximum flow problem,and summarizes the historical background of graph theory,basic concepts,basic knowledge and describes the basic concept of the network.The core basis of the maximum flow problem-Ford-Fulker

5、son maximum flow minimum cut theorem is introduced.Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm,Edmonds-Karp correct algorithm,Dinic algorithm are summarized in this paper.It also compares various algorithms to solve different problems in the pros and co

6、ns.In order to more clearly show the application of the maximum flow problem in the production life,the paper illustrates a real-life problem-The optimal scheduling of railway freight train to highlight the importance of maximum flow.This instance is to be solved under certain constraints,to design

7、the most freight train numbers through the railway in a day and night and to list out the schedules for each train.In this instance,by abstracting the network diagram from the real problems,transform the actual problem into the maximum flow problem,and use the properties of graph and Ford-Fulkerson

8、labeling algorithm,and ultimately solve the problem.In this paper,the combination of theory and examples focus on solving practical problems by applying theoretical basis.It has strong practicality and highlights the applications.4/44 Keywords：Graph Network flow Maximum flow 目录 第一章 绪论1 1.1 最大流问题的研究容

9、与背景1 1.2 最大流问题的发展状况1 1.3 选题的意义2 第二章 预备知识4 2.1 图论4 2.2 网络的基本概念5 2.3 最大流问题核心依据Ford-Fulkerson 最大流最小割定理7 第三章 最大流问题的几种算法9 3.1 标号法(Ford-Fulkerson 算法)9 3.2 Edmonds-Karp 修正算法12 3.3 Dinic 算法15.5/44 第四章 最大流问题的应用18 4.1 铁路货运列车的最优调度19 第五章 结论29 参 考 文 献30 致辞31 附录 1 英文原文32 附录 2 中文译文.37.1/44 第一章 绪论 1.1 最大流问题的研究容与背景

10、最大流问题也就是是指网络分析问题的一类，它是在指定的条件下,要求通过网络的物流、能量流、信息流等流量为最大的问题。比如交通运输网络中的人流、车流、物流,供水网络中的水流、金融系统中的现金流通信系统中的信息流等等，都属于最大流问题。图论是组合数 学的个分支与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系而且其应用十分广泛，是近年来较为活跃的数学分支之一。它的产生和 发展历经了二百多年的历史，瑞士数学家欧拉(LEuler)在 1736 年解决了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人。早期的图论与数学游戏有密切的联系，如哈密尔顿 的周

11、游世界问题、迷宫问题、博奕问题以与棋盘上马的行走路线之类的难题等吸引了许多学者。20 世纪后，图论的应用渗透到许多其他学科领域，如物理、化学、信息学、运筹学、博奕论、计算机网络、社会学以与集合论、矩阵论等。从 20 世纪 50 年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之一，也成为现代研究最大流问题的一个重要工具。1.2 最大流问题的发展状况 最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克（Hitchcock），1941 年他在研究生产组织和铁路运.2/44 输方面的线性规划问题时提出运输问题的基本模 型；后来柯

12、普曼（Koopmans）在 1947 年独立地提出运输问题并详细地对此问题加以讨论；从上世纪 40 年代早期开始，康脱洛维奇（Kantorovich）围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与 一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的发展。最大流问题就是就是在一个有向连通图中，指

13、定一点为发点，另一点 为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。1.3 选题的意义 在日常生活和生产中我们时常遇到一些网络图。如交通图、旅游线路图、管道系统图等。在优化理论 中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以与这些对象之间的相

14、互联系。例如旅游管理、网络通信、交通运输、金融系统等问题都可以用网络图来描述。最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点.3/44 为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。.4/44 第二章 预备知识 2.1 图论 所谓“图论”，顾名思

15、义也就是是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点与点与点之间的连线构成，它可以反映一些对象之间的关系。图形中的点表示对象(如工序、选手、通讯站等)，两点之间的有向或无向连线表示对象之间具有某种特定的关系(如先后关系、胜负关系、传递关系、连接关系等)。物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连 接起来的图进行模拟。这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的jivv,相对位置如何，都是无关紧要的。定义 1：两点之间不带箭头的连线称为边，一条连接jivv,的边

16、记为sv(或,jivv)，表示边的集合。定义 2：两点之间带箭头的连线称为,21meeeE弧，一条以iv为始点jv 为终点的弧记为,),(21mjiiaaaAvva表示弧的集合。定义 3：由点和边构成的图为无向图，记为),(EVG；由点和弧构成的图为有向图，记为),(AVD.定 义4：在 无 向 图G中，若 存 在 一 个 点 边 交 错 序 列),(112211kkkiiiiiiivevevev，满足.5/44)1,2,1(,1ktvvetttiii，则称之为一条联结1iv和kiv的链，记为),(21kiiivvv,若kiivv 1，则称之为圈。定 义5：在 有 向 图D中，若 存 在 一

17、个 点 弧 交 错 序 列),(112211kkiiiiiiavavav，弧tia的 始 点 为tiv，终 点 为1tiv，记 为),(1tttiiivva，则称这条点弧的交错序列为从1iv到kiv的一条路，记为),(21kiiivvv。若路的第一点和最后一点相同，则称之为回路。链与路中的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。定义 6：如果对于一个无向图G的每一条边，相应有一个权数ijw，则称这样的图为赋权图，记为),(CEVG。定义 7：如果对于一个有向图D的每一条弧，相应有一个权数ijc，称这样的图为网络,记为),(CAVD。一般在网络图中，每条弧的权，不是表示

18、弧的长度、而是表示弧的宽度，即代表距离、费用、通过能力(容量)等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络（参见文献17）。定义 8：在图G中，若任何两个点之间至少有一条链（或一条路），则称G是连通图，否则，称为不连通图。2.2 网络的基本概念 假设要把起点的一批流转物运送到终点去，在每一弧上通过流转物的总量不能超过这条弧上的容量，问题是应该怎样安排运送，才能使从起点.6/44 运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究容（参见文献15），以

19、下讨论的网络均为只有一个发点sv和一个收点tv的容量网络(,)DV A C。定义 9：对任意容量网络),(CAVD 中的弧(,)ijv v有流量ijf，称集合ijff为网络D上的一个流，称满足以下条件的流f为可行流：(1)容量限制条件：对D中每条弧(,)ijv v，有ijijcf 0；(2)平衡条件：对中间点iv，有ijkijkff(即中间点iv的物资的输入量与输出量相等)。对收、发点,tsv v有sijtijffW(即从sv点发出的物资总量等于tv点入的量)，W为网络流的总流量。在容量网络(,)DV A C中ijc表示弧(,)ijv v的容量，令ijx为通过弧(,)ijv v的流量，显然有0

20、ijijxc，流ijx应遵守点守恒规则，即：0,ijjiWisxxis tWit 称为守恒方程。定义 10：对任意容量网络(,)DV A C，寻求一可行流f使得流量W取得 极大值，这个可行流f便称为最大流。定义 11：在容量网络(,)DV A C中，若为网络中从发点sv到收点tv的一条路，给定向为从sv到tv，上的弧凡与同向称为前向弧。凡与反.7/44 向称为后向弧，其集合分别用和表示，f是一个可行流，如果满足 0(,)0(,)ijijijijijijfcv vcfv v 则称为从sv到tv的(关于f的)增广链。定义 12：在容量网络),(CAVG 中，若有弧集A为A的子集，将D分为两个子图1

21、2,D D，其顶点集合分别记,S S，,SSV SS，,stv v分别属于,S S，满足：(,)D V AA不连通；A为A的真子集，而(,)D V AA仍连通，则称A为D的割集，记(,)AS S。割集(,)S S中所有始点在S，终点在S的边的容量之和，称为(,)S S的割集容量，记为(,)C S S。2.3 最大流问题核心依据Ford-Fulkerson 最大流最小割定理 Ford-Fulkerson最大流最小割定理是由Ford 和 Fulkerson在 1956年提出的，是图论的核心定理。定理 1：（Ford-Fulkerson 最大流最小割定理）任一容量网络D中，从sv到tv 的最大流ij

22、f的流量等于分离,stv v的最小割的容量。证明：设在D中从sv到tv的任一可行流ijx的流量为W，最小割集为.8/44(,)S S，最小割集的容量为(,)C S S。这个定理的证明分两步：我们先证明(,)WC S S：由守恒方程可得：()()()()(3.1)ijjii Sjjijjiijjii S j Si S j Sijjii S j SWxxxxxxxx 因此有：()(,)ijjiijiji S j Si S j Si S j SWxxxcC S S。下面我们证明一个可行流是最大流，当且仅当不存在关于它的从sv到tv的增广路径：必然性：显然，因为如果存在增广路径，还可以继续增广，流就不

23、是最大流。充分性：假设可行流ijx是一个不存在关于它的增广路径的流，对于最小割集(,)S S，有对任意,i jS，存在从iv到jv的增广路径，而对任意,iS jS，不存在从iv到jv的增广路径，由定义可知对任意,iS jS有：,0ijijjixcx 由公式(3.1)可知：(,)iji S j SWcC S S。即流的值等于割集的容量，定理得证。.9/44 第三章 最大流问题的几种算法 最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大流问题。下面用数学语言来说明

24、最大流问题：1.设有一个有向连通图 G(V,A)，在 V 中指定一点称为发点 s,和另外一点为收点 t，其余的称为中间点，弧（arc）集 A 中每条弧（i，j）上有非负数ijc称为这弧的容量，记容量集为c=ijc，称这样的图为一个网络，记为 G(V,A,c)（注：当（i，j）不是弧时ijc=0）。2.在弧集 A 上的弧（i，j）定义一非负数ijf，称为弧（i，j）上的流量，流量的集合 f=ijf称为网络的一个流，满足以下条件的称为可行流：1）容量限制条件，所有的弧的流量ijf不大于弧的容量ijc；2）平衡条件，对所有的中间点，流入的流量和等于流出的流量和，发点流出的流量F 等于流进收点的总流量

25、F.最大流问题就是求总流量最大达可行流。求解最大流问题存在许多算法，这一节将介绍几种常用算法。3.1 标号法(Ford-Fulkerson 算法)3.1.1 标号法(Ford-Fulkerson 算法)思想 Ford-Fulkerson 标号法是一种找最大流f的算法。它是由 Ford 和Fulkerson 于 1957 年最早提出的，其基本思想是从任意一个可行流出发寻 找条增广路径，并在这条增广路径上增加流量，于是便得到一个新.10/44 的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量，继续这个过程，一直到找不到新的增广路径为止（参见文献2）。采用 Ford-Fulker

26、son 标号法求解最大流问题时，在标号过程中，一个点仅有以下三种状态之一：标号已检查(有标号且所有相邻点都标号了)；标号未检查(有标号，但某些相邻点未标号)；未标号（参见文献6）。Ford-Fulkerson 标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献18）。现在我们考虑只有一个发点sv和一个收点tv的容量网络，应用 Ford-Fulkerson 标号算法求解它的最大流 3.1.2 Ford-Fulkerson 标号法的具体步骤 A:标号过程 步骤 0 确定一初始可行流ijf，可以是零流。步骤 1 给发点sv以标号

27、,sv。步骤 2 选择一个已标号但未检查的点iv，并作如下检查：对每一弧(,)ijv v，若jv未给标号，而且ijijcf时，即流出未饱和弧,给jv以标号,jiv；对每一弧(,)jiv v，若jv未给标号，而且0jif时，即流入非零流弧，给jv以标号,jiv；其中：(,)min,(,)ijijijjijijicfv vfv v 若为流出未饱和弧若为流入非零流弧 步骤 3 重复步骤 2 直到收点tv被标号，或不再有顶点可以标号为止。.11/44 如果点给了标号说明存在一条增广路径，故转向增广过程 B。如若点tv不能获得标号，而且不存在其它可标号的顶点时，算法完毕，所得到的流便是最大流。B：增广过

28、程 由终点tv开始，使用标号的第二个元素构造一条增广路径(点tv的标号的第二个元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等)，在上作调整得新的可行流ijf，(标号的第二个元素的正负号表示通过增加或减少弧流来增大流值)。令为tv标号的第一个元素的值，作(,)(,)ijijijijjiijfv vffv vf是 上前向弧是 上后向弧其它 以新的可行流ijf代替原来的可行流，去掉所有标号，转标号过程的步骤1。采用 Ford-Fulkerson 标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能

29、力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献14）。.12/44 1 m m m m m m m m f e d c a b t s 图 3.2.1 3.2 Edmonds-Karp 修正算法 Ford-Fulkerson 标号算法理论上存在着严重的弱点，以以下图 3.2.1为例各边上的权是它们的容量，其最大流流量为2m，若增广路径选择得不好,即交替地采用sabeft和sdebct作为增广路径，则每次增广只能使总

30、的流量增加 1,当初始流选为零流，无疑需作21m次的增加流量才能使之达到最大，可见 Ford-Fulkerson 算法的时间复杂度不仅依赖于网络的规模(即依赖于网络点数和边数)，还和各边的容量有关,而容量可以是任意的正整数。如图 3.2.1 中，当sabeft和sdebct交替作为增广路径时，be弧交替地以前向弧和后向弧出现。利用 Ford-Fulkerson 算法求解就很麻烦了（参见文献8）。对于 Ford-Fulkerson算法,由于增广路径选取的任意性造成了该算法不是好算法，Edmonds 和 Karp 对 Ford-Fulkerson 算法作修正，可概括为一句话：“先给标号的先扫描”。

31、它的意思是对已给标号的顶点v进行扫描时，先对所有和v邻接的未给标号的顶点给予标号。具体的说图 3.2.1的例子，顶点s先标记，所以应该先扫描，因此避免了 Ford-Fulkerson 算法那样交替地出现,sabeft sdebct的情况，也就避免了be弧交替地以前向弧和后向弧来回摇摆的局面。所以 Edmonds-Karp的修正实质是对顶点给标记过程采用了“宽度优先”策略。使得流量增加总是沿着一条长度最短的路径从s流向t的（参见文献3）。.13/44 现在我们仍考虑只有一个发点sv和一个收点tv的网络图，Edmonds-Karp修正算法的主要步骤是：确定一初始可行流ijf，其流量)(fW。检验当

32、前所确定可行流是否是网络中的最大流，若不是，需进一步调整(检验一个可行流是否为最大流。只要检查一下当前可行流是否还存在增广路径，若存在，则说明当前可行流还不是最大流，否则是最大流)。将当前的可行流调整成一个流量更大的新可行流，再由检验。同样地，我们通常用观察法确定网络的个初始可行流。对于较为复杂的网络，至少能把初始可行流取为零流。通过在网络上标号的方法能系统地寻找出当前可行流的增广路径，它的基本思想是：从起点sv起，逐步寻找sv至各点iv间的增广路径，若能找到sv至iv的一条增广路径，则给点iv标号,ii（其中第一个标号i即为sv至iv这条增广路径上的最大可调整量，第二个标号i则表示这条可行流

33、上点iv的前一点是i点）。根据标号可反向追踪而写出这条增广路径。在逐步扩大已标号的过程中，一旦终点tv标上号，表示已找到一条由sv至tv的增广路径。反之，如果标号过程进行至某一步中止了，而tv尚未标号，则说明对当前的可行流，网络中不存在任何增广路径。当前可行流即为最大流。Edmonds-Karp 修正算法的具体步骤如下：给发点sv标号,sv，含义为sv至sv的增广路径已找到，前一点为sv，.14/44 这条增广路径上的调整量为。选与sv关联的从sv流出的未饱和弧(,)siv v或流入sv的非零流弧(,)isv v，给iv标号,isv(对于流出弧)或,isv(对于流入弧)。其中：(,)(,)si

34、sisiisiiscfv vfv v若为流出未饱和弧若为流入非零弧 将顶点集分为互补的二个点集S、S，其中S为已标号点集，S为未标号点集；考虑所有这样的弧(,)ijv v或(,)jiv v，其中,ijvS vS。若弧(,)ijv v为从iv流出的未饱和弧，则给jv标号,jiv。其中min,jiijijcf；若 弧(,)jiv v为 流 入iv的非 零 流弧，则给jv标号,jiv。其中min,jiijf。依此进行，得到的结果是：(a)S ，说明网络中存在增广路径，则由标号点反向追踪找出，转第步；(b)S ，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得

35、到最小割集(,)S S。调整过程：取minjjv，令(,)(,)ijijijijjiijfv vffv vf是 上前向弧是 上后向弧其它 得到新可行流ijf，流量()()W fW f，即比原可行流流量增加了，再转步。用 Edmonds-Karp 修正算法求解最大流问题时，也可以得到一个最小.15/44 割集。最小割集的意义同 Ford-Fulkerson 算法得到的最小割集的意义相同。3.3 Dinic 算法 Dinic 于 1970 年提出了 Ford-Fulkerson 算法的改进算法，Dinic 算法的特点是将顶点按其与发点的最短距离分层。Edmonds-Karp 修正算法的实质也是一种

36、分层，如果说 Ford-Fulkerson 算法是采用了深度优先策略。Edmonds-Karp 修正算法则是用宽度优先取代了深度优先，Dinic 算法则是兼取这两种方法。在分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略（参见文献3）。3.3.1 增量网络与分层增量网络 定义 13：给定一个带发点sv和收点tv的容量网络(,)DV A C与D上的可行流ijf后，我们定义()(,)|(,),()(,)|(,),0ijijijijijjijiAfv vv vA fcAfv vv vA f，因为D中任何一 对 顶 点 之 间 至 多 有 一 条 弧，所 以()()AfAf，记()()()A

37、fAfAf，并且对一切(,)()ijv vA f令,(,)()(,)()ijijijijjiijcfv vAfcfv vAf若，若，于是得一个带发点sv和收点tv的容量网络()(,(),)D fV A fC，称之为D的关于可行流ijf的增量网络。为了介绍分层增量网络，我们先来介绍关于网络的一个算法分层算法，它的基本思想是：步骤 0：把发点sv标为“已标号未检查”，sv的层数()0h s。步骤 1：在已标号未检查顶点中选取最早得到标号的顶点iv，转步骤 2；如.16/44 果所有标号顶点都已检查，转步骤 3。步骤 2：考察顶点iv的一切出弧(,)ijv v，若jv已标号，什么也不做；否则将 jv

38、标为“已标号未检查”，并令()()1h jh i。当iv的所有出弧都考察完毕，把iv改为已检查，转步骤1。步骤 3：如果有些顶点没有标号，则从sv到这些顶点不存在路；否则iv为 D的根，()h i为D中最短(,)siv v路的长。在增量网络()D f中应用分层算法，可以求出从发点sv到其余各顶点iv的最短路的长()h i，()h i就是顶点iv（关于发点sv）的层数。即iv就是()D f的第()h i层顶点。()D f的第 0 层只有一个顶点，把顶点分层后，()D f中 的弧又可以分为三类：第一类为从第i层顶点到第1i层顶点的弧；第二类为从第i层顶点到同一层顶点的弧；第三类为从第i层顶点到第j

39、层顶点的弧()ji（参见文献5）。定义 14：对于带发点sv和收点tv的容量网络(,)DV A C，设关于可行流ijf的 增 量 网 络()(,(),)D fV A fC，我 们 定 义()D f的 子 网 络()(),(),)AD fVfA fC如下：()|()()()(,)|()()1(),(,)()(,)|()()1,(,)()tiijijititVfvvh ih tA fv vh jh ih tv vA fv vh ih tv vA f 则()AD f称为D的关于可行流ijf的分层增量网络。其中第0 层和第()h t.17/44 层分别只有一个顶点sv和tv，()AD f的所有弧都是由

40、第i层顶点指向第1i层顶点()ih t。3.2 Dinic 算法的基本思想与具体步骤 Dinic 算法的基本思想是：从带发点sv和收点tv的容量网络D的任一可行流0f(例如零流)开始，构造D的关于0f的分层增量网络0()AD f，在0()AD f中找一条从sv到tv的增广路径，对0f沿进行增广得到可行流10f，在0()AD f中删去上容量最小的弧，并相应修改10()AD f上弧的容量，得到网络10()AD f，然后可以在10()AD f中再找一条从sv到tv的增广路径，对10f沿进行增广得到可行流20f，重复上述步骤依次得到D的可行流120001,pffff，因为0()AD f只有有限条弧，每

41、次至少删去一条弧，所以在有限步后必然使余下的网络不再存在增广路径，tv在1()AD f中的层数一定大于它在0()AD f中的层数；针对1()AD f重复上面的做法，在有限次增广后一定会得到D的可行流2f，使tv在2()AD f中的层数更大。由于tv的层数最多为1n（n是网络D的顶点数）。因此经过有限步后得到D的可行流kf，D中不再有kf的增广链，这时kf就是D的最大流。Dinic 算法的具体步骤如下：步骤 0：在网络D中任意取个可行流0f作为初始可行流，令00,0,pqpqff。步骤 1：(作分层增量网络)根据pqf作D的增量网络()pqD f，再利用分层算.18/44 法构造分层增量网络()

42、pqAD f，如果在作分层增量网络时tv得不到标号，则 算法完毕，pqf就是D的最大流；否则转步骤 2。步骤 2：(寻找增广路径)给发点sv标号为,sv，令is。如iv在()pqAD f没有出弧，转；否则在()pqAD f中任取iv的一条出弧(,)ijv v，转。设iv的标号为,ii，其中i为iv前面的节点，令min,jiijc，jv获得标号 ,jiv。如果jt，转步骤 3；否则令ij，转。设iv的标号为,ii，如果isv，在()pqAD f中删去iv的所有入弧，所 得的网络仍记为()pqAD f，转；否则置1qq，转步骤 1。步骤 3：（增广）从顶点tv的标号中的第二个元素反向追踪，求出()

43、pqAD f的增广路径，在()pqAD f中把上的每条弧的容量ijc改为ijtc，删去容量为 0 的弧，同时把流pqf增广为流1pqf，把()pqAD f中修改容量和删去弧后的网络记为1()pqAD f，置1pp，去掉网络()pqAD f中所有顶点的标号，转步骤 2。第四章 最大流问题的应用.19/44 4.1 铁路货运列车的最优调度 4.1.1 问题表达 某地区A、B两市之间要修建一铁路，依据地势、环境、需求等因素，修建铁路的预定方案如下：（1）铁路的运行方式为客车与货运兼营的双轨铁路（单向单轨），在其运行的列车有旅客快车和货运列车，由于客车的运行时间是国家铁路部门早已排定的，不可更改，且规

44、定客运优于货运，即货车在每站开出前应先明确在其到达前方车站前不会被客车赶上，否则在该站等候不能开车。又若货车的前方到达站如无停车岔道，则货车从本站开出前应明确在其前面两站的行程中不会被客车赶上否则在本站等候不能开车，余类推。（2）铁路线有A、B、C、D四个站，各站的岔道数为119,7,5DCBAnnnn及.这些岔道可供调车用，亦可供停车卸货与洗刷车辆用。（3）按早已排定的旅客快车时刻表，客车每天凌晨 2:00从A站开出，以后每隔5小时开出一列，一昼夜共开出 5列，当天最后一列的开车时间与翌晨第一列的开车时间相隔 4小时。客车的行车时间在 A、B站之间为3小时；在B、C站之间为2小时；在C、D站

45、之间为5小时。（4）在不干扰客车运行的条件下，关于货运列车的初步安排为：每天0:00从A站发出一列，以后每隔2小时发出一列，货车的行车时间在A、B站之间为5小时；在B、C站之间为4小时；在C、D站之间为7小时。为了充分发挥该铁路线的货运能力，需要排定一最优的货车运行时刻表，即要求每天发出最多的货运列车且不干扰已排定的客运列车。4.1.2 问题分析.20/44 求解这个问题较为复杂，但可将其转化为网络最大流问题。（1）设A、B两市与其间的车站共P个。每个车站有nk条岔道（k=1,2,3P）,可停放nk列列车。从第k站到第k+1站的行车时间货车为tk个小时，客车为tk个小时。设k为火车到达第k站并

46、从第k站开出的时刻 设k为客车到达第k站并从第k站开出的时刻 设1k为货车到达第k+1站并从第k+1站开出的时刻 设1k为客车到达第k+1站并从第k+1站开出的时刻 于是显然有kkkt11kkkt（2）若11,kkk与有公共部分，则称11,kkk与是相交的，否则成为不相交的。显然有当只11,kkk与相交情况下客车才有可能（并非必然）在第k站与地k+1站间追上货车。（3）在11,kkk与相交情况下，k，1k，k，1k间的相交关系可由图4.1.1 所示：.21/44 图 4.11 情况为途中货车追上了客车故不符合题意。情况与情况中在第k站与第k+1站间不发生在途中追上货车。而在情况中必发生在第k站

47、与第k+1.22/44 站间客车在途中追上货车。于是有以下结论：若 11,kkkk在，即11kkkk及，则在第k站与第k+1站必发生客车追上货车情况。否则在第k站与第k+1站之间不发生客车追上货车情况。（4）绘制网络图 用（k，k）表示第k站处于时刻k的状态，如在k=2.3在（k，2.6），（k，6.6）状态开出的货车不会再途中被客车追上，则在图中表现为（k，2.6）与（k，6.6）两节点为起点的两条水平方向的直线弧，而在（k，4.6）状态下开出的货车会在途中被客车追上，则不能从该点引出水平方向的直线弧（图4.1.2），垂直方向的直线弧并联着同一车站的相邻状态。.23/44 图 4.1.2 上

48、图中各弧旁的数字为容量，因铁路线是单向单轨的，故水平方向的弧容量为1，垂直方向的弧的容量为各站的岔道数量，在列出全部状态的网络图中求最大流，此最大流即为允许开出的最多货运列车数。4.1.3 问题求解 以货运列车的运行时间为基础绘制网络图。（1）令DCBA,为火车从某站开出或到达某站的时刻。依题意，若不受客车干扰则：.24/44 A=0:00,2:00,4:00 B=5:00,7:00,9:00 C=9:00,11:00,13:00 D=16:00,18:00,20:00 于是货车在相邻两站的运行时间为（若不受客车干扰）：27,22,15,20,23,18,21,16,19,14,17,12,1

49、5,10,13,8,11,6,9,4,7,2,5,0:,BA(25点即翌日1点，余类推)31,27,29,25,27,23,25,21,23,19,21,17,19,15,17,13,15,11,13,9,11,7,9,5:,CB 31,36,29,34,27,32,25,30,23,28,21,26,19,24,17,22,15,20,13,18,11,6,9:,DC(2)令,DCBA为客车从某站开出或到达某站的时刻，依题意：A=2:00,7:00,12:00,17:00,22:00 B=5:00,10:00,15:00,20:00,25:00(即1:00)C=7:00,12:00,17:0

50、0,22:00,27:00（即3:00）D=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）于是客车在相邻两站之间的运行时间为：00:25,00:22,00:20,00:17,00:15,00:12,00:10,00:7,00:5,00:2:,BA 00:27,00:25,00:22,00:20,00:17,00:15,00:12,00:10,00:7,00:5:,CB.25/44,DC00:32,00:27,00:27,00:22,00:22,00:17,00:17,00:12,00:12,00:7:图 4.1.3 （3）比较;00:1,100:600: