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

《(毕业设计论文)最大流问题及应用.doc》由会员分享，可在线阅读，更多相关《(毕业设计论文)最大流问题及应用.doc（48页珍藏版）》请在三一办公上搜索。

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

2、rd-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, agriculture, trans

4、portation 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-Fulkerso

5、n 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

6、cons.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 , t

7、o design 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 Fo

8、rd-Fulkerson 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. 字典Keywords： Graph Network flow Maximum flow 目录第一章 绪论0

9、1.1 最大流问题的研究内容及背景01.2 最大流问题的发展状况01.3 选题的意义1第二章 预备知识32.1 图论32.2 网络的基本概念42.3 最大流问题核心依据Ford-Fulkerson最大流最小割定理6第三章 最大流问题的几种算法83.1 标号法(Ford-Fulkerson算法)83.2 Edmonds-Karp修正算法113.3 Dinic算法14第四章 最大流问题的应用184.1 铁路货运列车的最优调度18第五章 结论29参 考 文 献30致谢辞31附录1英文原文32附录2中文译文37第一章 绪论 1.1 最大流问题的研究内容及背景 最大流问题也就是是指网络分析问题的一类，它

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

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

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

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

14、问题就是就是在一个有向连通图中，指定一点为发点，另一点为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。第二章 预备知识2.1 图论所谓“图论”，顾名思义也就是是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映

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

16、图，记为；由点和弧构成的图为有向图，记为.定义4：在无向图中，若存在一个点边交错序列，满足，则称之为一条联结和的链，记为,若，则称之为圈。定义5：在有向图中，若存在一个点弧交错序列，弧的始点为，终点为，记为，则称这条点弧的交错序列为从到的一条路，记为。若路的第一点和最后一点相同，则称之为回路。链与路中的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。定义6：如果对于一个无向图的每一条边，相应有一个权数，则称这样的图为赋权图，记为。定义7：如果对于一个有向图的每一条弧，相应有一个权数，称这样的图为网络,记为。一般在网络图中，每条弧的权，不是表示弧的长度、而是表示弧的宽度，即代表

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

18、定义9：对任意容量网络中的弧有流量，称集合为网络上的一个流，称满足下列条件的流为可行流：(1)容量限制条件：对中每条弧，有；(2)平衡条件：对中间点，有(即中间点的物资的输入量与输出量相等)。对收、发点有(即从点发出的物资总量等于点入的量) ，为网络流的总流量。在容量网络中表示弧的容量，令为通过弧的流量，显然有，流应遵守点守恒规则，即：称为守恒方程。定义10：对任意容量网络，寻求一可行流使得流量取得极大值，这个可行流便称为最大流。定义11：在容量网络中，若为网络中从发点到收点的一条路，给定向为从到，上的弧凡与同向称为前向弧。凡与反向称为后向弧，其集合分别用和表示，是一个可行流，如果满足则称为从

19、到的(关于的)增广链。定义12：在容量网络中，若有弧集为的子集，将分为两个子图，其顶点集合分别记，分别属于，满足：不连通；为的真子集，而仍连通，则称为的割集，记。割集中所有始点在，终点在的边的容量之和，称为的割集容量，记为。2.3 最大流问题核心依据Ford-Fulkerson最大流最小割定理Ford-Fulkerson最大流最小割定理是由Ford和Fulkerson在1956年提出的，是图论的核心定理。定理1：（Ford-Fulkerson最大流最小割定理）任一容量网络中，从到的最大流的流量等于分离的最小割的容量。证明：设在中从到的任一可行流的流量为，最小割集为，最小割集的容量为。这个定理的

20、证明分两步： 我们先证明：由守恒方程可得：因此有：。 下面我们证明一个可行流是最大流，当且仅当不存在关于它的从到的增广路径：必然性：显然，因为如果存在增广路径，还可以继续增广，流就不是最大流。充分性：假设可行流是一个不存在关于它的增广路径的流，对于最小割集，有对任意，存在从到的增广路径，而对任意，不存在从到的增广路径，由定义可知对任意有：由公式可知：。即流的值等于割集的容量，定理得证。第三章 最大流问题的几种算法最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大

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

22、。求解最大流问题存在许多算法，这一节将介绍几种常用算法。3.1 标号法(Ford-Fulkerson算法)3.1.1标号法(Ford-Fulkerson算法)思想 Ford-Fulkerson标号法是一种找最大流的算法。它是由Ford和Fulkerson于1957年最早提出的，其基本思想是从任意一个可行流出发寻找条增广路径，并在这条增广路径上增加流量，于是便得到一个新的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量，继续这个过程，一直到找不到新的增广路径为止（参见文献2）。采用Ford-Fulkerson标号法求解最大流问题时，在标号过程中，一个点仅有下列三种状态之一：标号

23、已检查(有标号且所有相邻点都标号了)；标号未检查(有标号，但某些相邻点未标号)；未标号（参见文献6）。Ford-Fulkerson标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献18）。现在我们考虑只有一个发点和一个收点的容量网络，应用Ford-Fulkerson标号算法求解它的最大流3.1.2 Ford-Fulkerson标号法的具体步骤A:标号过程步骤0 确定一初始可行流，可以是零流。步骤1 给发点以标号。步骤2 选择一个已标号但未检查的点，并作如下检查： 对每一弧，若未给标号，而且时，即流出未饱和弧,给以标号； 对

24、每一弧，若未给标号，而且时，即流入非零流弧，给以标号；其中：步骤3 重复步骤2直到收点被标号，或不再有顶点可以标号为止。 如果点给了标号说明存在一条增广路径，故转向增广过程B。如若点不能获得标号，而且不存在其它可标号的顶点时，算法结束，所得到的流便是最大流。B：增广过程由终点开始，使用标号的第二个元素构造一条增广路径(点的标号的第二个元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等)，在上作调整得新的可行流，(标号的第二个元素的正负号表示通过增加或减少弧流来增大流值)。令为标号的第一个元素的值，作以新的可行流代替原来的可行流，去掉所有标号，转标号过程的

25、步骤1。采用Ford-Fulkerson标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献14）。3.2 Edmonds-Karp修正算法Ford-Fulkerson标号算法理论上存在着严重的弱点，以下图3.2.1为例各边上的权是它们的容量，其最大流流量为，若增广路径选择得不好,即交替地采用和作为增广路径，则

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

27、有和邻接的未给标号的顶点给予标号。具体的说图3.2.1的例子，顶点先标记，所以应该先扫描，因此避免了Ford-Fulkerson算法那样交替地出现的情况，也就避免了弧交替地以前向弧和后向弧来回摇摆的局面。所以Edmonds-Karp的修正实质是对顶点给标记过程采用了“宽度优先”策略。使得流量增加总是沿着一条长度最短的路径从流向的（参见文献3）。1mmmmmmmmfedcabts图3.2.1现在我们仍考虑只有一个发点和一个收点的网络图，Edmonds-Karp修正算法的主要步骤是： 确定一初始可行流，其流量。 检验当前所确定可行流是否是网络中的最大流，若不是，需进一步调整(检验一个可行流是否为最

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

29、增广路径。反之，如果标号过程进行至某一步中止了，而尚未标号，则表明对当前的可行流，网络中不存在任何增广路径。当前可行流即为最大流。Edmonds-Karp修正算法的具体步骤如下： 给发点标号，含义为至的增广路径已找到，前一点为，这条增广路径上的调整量为。选与关联的从流出的未饱和弧或流入的非零流弧，给标号 (对于流出弧)或 (对于流入弧)。其中： 将顶点集分为互补的二个点集、，其中为已标号点集，为未标号点集； 考虑所有这样的弧或，其中。若弧为从流出的未饱和弧，则给标号。其中；若弧为流入的非零流弧，则给标号。其中。依此进行，得到的结果是： (a)，说明网络中存在增广路径，则由标号点反向追踪找出，转

30、第步；(b)，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得到最小割集。 调整过程：取，令得到新可行流，流量，即比原可行流流量增加了，再转步。用Edmonds-Karp修正算法求解最大流问题时，也可以得到一个最小割集。最小割集的意义同Ford-Fulkerson算法得到的最小割集的意义相同。3.3 Dinic算法Dinic于1970年提出了Ford-Fulkerson算法的改进算法，Dinic算法的特点是将顶点按其与发点的最短距离分层。Edmonds-Karp修正算法的实质也是一种分层，如果说Ford-Fulkerson算法是采用了深度优先策略。Ed

31、monds-Karp修正算法则是用宽度优先取代了深度优先，Dinic算法则是兼取这两种方法。在分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略（参见文献3）。3.3.1 增量网络与分层增量网络 定义13：给定一个带发点和收点的容量网络及上的可行流后，我们定义，因为中任何一对顶点之间至多有一条弧，所以，记，并且对一切令，于是得一个带发点和收点的容量网络，称之为的关于可行流的增量网络。为了介绍分层增量网络，我们先来介绍关于网络的一个算法分层算法，它的基本思想是：步骤0：把发点标为“已标号未检查”，的层数。步骤1：在已标号未检查顶点中选取最早得到标号的顶点，转步骤2；如果所有标号顶点都已检查

32、，转步骤3。步骤2：考察顶点的一切出弧，若已标号，什么也不做；否则将标为“已标号未检查”，并令。当的所有出弧都考察完毕，把改为已检查，转步骤1。步骤3：如果有些顶点没有标号，则从到这些顶点不存在路；否则为的根，为中最短路的长。在增量网络中应用分层算法，可以求出从发点到其余各顶点的最短路的长，就是顶点（关于发点）的层数。即就是的第层顶点。的第0层只有一个顶点，把顶点分层后，中的弧又可以分为三类：第一类为从第层顶点到第层顶点的弧；第二类为从第层顶点到同一层顶点的弧；第三类为从第层顶点到第层顶点的弧（参见文献5）。定义14：对于带发点和收点的容量网络，设关于可行流的增量网络，我们定义的子网络如下：则

33、称为的关于可行流的分层增量网络。其中第0层和第层分别只有一个顶点和，的所有弧都是由第层顶点指向第层顶点。3.2 Dinic算法的基本思想及具体步骤Dinic算法的基本思想是：从带发点和收点的容量网络的任一可行流 (例如零流)开始，构造的关于的分层增量网络，在中找一条从到的增广路径，对沿进行增广得到可行流，在中删去上容量最小的弧，并相应修改上弧的容量，得到网络，然后可以在中再找一条从到的增广路径，对沿进行增广得到可行流，重复上述步骤依次得到的可行流，因为只有有限条弧，每次至少删去一条弧，所以在有限步后必然使余下的网络不再存在增广路径，在中的层数一定大于它在中的层数；针对重复上面的做法，在有限次增

34、广后一定会得到的可行流，使在中的层数更大。由于的层数最多为（是网络的顶点数）。因此经过有限步后得到的可行流，中不再有的增广链，这时就是的最大流。Dinic算法的具体步骤如下：步骤0：在网络中任意取个可行流作为初始可行流，令。步骤1：(作分层增量网络)根据作的增量网络，再利用分层算法构造分层增量网络，如果在作分层增量网络时得不到标号，则算法结束，就是的最大流；否则转步骤2。步骤2：(寻找增广路径)给发点标号为，令。如在没有出弧，转；否则在中任取的一条出弧，转。设的标号为，其中为前面的节点，令，获得标号 。如果，转步骤3；否则令，转。设的标号为，如果，在中删去的所有入弧，所得的网络仍记为，转；否则

35、置，转步骤1。步骤3：（增广）从顶点的标号中的第二个元素反向追踪，求出的增广路径，在中把上的每条弧的容量改为，删去容量为0的弧，同时把流增广为流，把中修改容量和删去弧后的网络记为，置，去掉网络中所有顶点的标号，转步骤2。第四章 最大流问题的应用4.1 铁路货运列车的最优调度4.1.1 问题叙述某地区A、B两市之间要修建一铁路，依据地势、环境、需求等因素，修建铁路的预定方案如下：（1）铁路的运行方式为客车与货运兼营的双轨铁路（单向单轨），在其运行的列车有旅客快车和货运列车，由于客车的运行时间是国家铁路部门早已排定的，不可更改，且规定客运优于货运，即货车在每站开出前应先明确在其到达前方车站前不会被

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

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

38、第k+1站并从第k+1站开出的时刻于是显然有 （2）若有公共部分，则称是相交的，否则成为不相交的。显然有当只相交情况下客车才有可能（并非必然）在第k站与地k+1站间追上货车。（3）在相交情况下，间的相交关系可由图4.1.1所示：图4.11情况为途中货车追上了客车故不符合题意。情况与情况中在第k站与第k+1站间不发生在途中追上货车。而在情况中必发生在第k站与第k+1站间客车在途中追上货车。 于是有下列结论：若内，即，则在第k站与第k+1站必发生客车追上货车情况。否则在第k站与第k+1站之间不发生客车追上货车情况。（4）绘制网络图用（k，）表示第k站处于时刻的状态，如在=2.3在（k，2.6），（

39、k，6.6）状态开出的货车不会再途中被客车追上，则在图中表现为（k，2.6）及（k，6.6）两节点为起点的两条水平方向的直线弧，而在（k，4.6）状态下开出的货车会在途中被客车追上，则不能从该点引出水平方向的直线弧（图4.1.2），垂直方向的直线弧并联着同一车站的相邻状态。 图4.1.2上图中各弧旁的数字为容量，因铁路线是单向单轨的，故水平方向的弧容量为1，垂直方向的弧的容量为各站的岔道数量，在列出全部状态的网络图中求最大流，此最大流即为允许开出的最多货运列车数。4.1.3 问题求解以货运列车的运行时间为基础绘制网络图。（1）令为火车从某站开出或到达某站的时刻。依题意，若不受客车干扰则：=0:

40、00,2:00,4:00=5:00,7:00,9:00=9:00,11:00,13:00=16:00,18:00,20:00于是货车在相邻两站的运行时间为（若不受客车干扰）：(25点即翌日1点，余类推)(2)令为客车从某站开出或到达某站的时刻，依题意：=2:00,7:00,12:00,17:00,22:00=5:00,10:00,15:00,20:00,25:00(即1:00)=7:00,12:00,17:00,22:00,27:00（即3:00）=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）于是客车在相邻两站之间的运行时间为： 图4.1.3（3）比较

41、之内。这说明若A站在6:00及16:00开出两列货车，则该两列货车在到达B站前，必会被客车撞上。故这两次货运列车是不可行的。这表示在以货运列车的运行时刻为基础的网络图（图4.1.3）中为（A,6:00）及（A，16:00）两节点前未引出水平方向的直线弧。该图的各个节点中仅注明货运列车从该站开出或到达该站的时刻，站名省略了。比较,我们发现之内；之内，其在图4.1.3中的表示同前。比较,我们发现之内；之内，其在图3中的表示同前。（4）图4.1.3中各水平方向的直线弧的容量均为1。如前所述，它表示在该时间内，货车在相邻两站的行程中不会被客车追上，故可顺利地到达前方车站。垂直方向的直线弧的通量表示各站

42、的岔道数。（5）做网络的发点，并从向A站的各状态节点作辅助弧，辅助弧的容量等于以A站的各状态节点为起点的各弧的容量的总和。作网络的收点，并从D站的各状态节点向作辅助弧。辅助弧的容量等于以D站个状态节点为终点的各弧的容量总和。（6）求图4.1.3所示容量网络的最大流）以零流f=0,0,0为初始流，但图4.1.3的各弧旁省略了零流量。）以表示图3中第i行第j列的节点。用Ford-Fulkerson标号法求得以下增广链并按值进行调整。 以上10条增广链的调整量均为。用它对初始流（零流）进行调整后，结果如图4.1.3所示。若对现行流继续标号，则只有A站的12个状态节点获得标号，即标号中断，不能延伸达。

43、故现行流即为最大流，其流量结论 在本问题所给条件下各车站一昼夜中能开出的最多货运列车数位10列。现由图4.1.3将A站以昼夜中能开出的10列货车的运行时刻及调度情况阐述如（货车一昼夜中在其他各站点的运行及调度情况可由同图作类似阐述）在0:00,8:00,10:00,18:00,20:00,22:00时刻所开出的货车在各站点均畅通。在2:00开出的货车，11:00到达C站时须在岔道内停留到13:00方可继续前行。在4:00开出的货车，9:00到达B站时，须在岔道内停留到11:00方可继续前行。在12:00开出的货车，21:00到达C站时，须在岔道内停留到23:00方可继续前行。在14:00开出的

44、货车，19:00到达B站时，须在岔道内停留到21:00方可继续前行。至此已求得一昼夜中从A站开出的10次货运列车的最优调度及最优运行时刻表。仿此，由图4.1.3可求得从其他各站点开出货车的最优调度及最优运行时刻表。4.1.4 问题总结本问题看似简单，是个追赶问题，只要计算出货车与客车在两站之间的运行时间即可控制货车的开出时间，其实不然，此问题是在追赶问题的基础上求最多可开出的货车辆数，我们把该问题转化成为最大流问题，应用Ford-Fulkerson标号法解决了这一问题。通过对算法的分析求解制定出了货车运行的最大数量并列出货车运行时间表，可见最大流算法的有效性和实用性。第五章 结论本课题主要以图论的知识为理论基础，来讨论最大流问题。最大流问题是一类应用极为广泛的问题，20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。最大流问题的核心依据是Ford-Fulkerson最大流最小割定理，在这个定理的基础上，解决最大流问题的几种算法有Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法等本论文分别介绍了这几种算法，并举实例说明各个算法具体的解题过程，各算法的优劣各不相