第一类是按照流量与容量的大小关系来划分：若，则称之为饱和弧；若，则称之为非饱和弧。

第二类是按照是否存在流量来划分：

若，则称之为零流弧；若，则称之为非零流弧。

介绍增广链之前，我们要引入链的概念:

设是一个给定的图，若图的一些点和边可以按照如下交错序列排列，使得，则称为中连接和的一条链，简称为链，点和称为链的端点，其他点称为的内点。我们把这条链简记为。若链中的所有点都不相同 ，则称之为初等链。若边都是不相同的，则称之为简单链。文献综述

本文所指的链都是简单链。若链连接着网络中的发点和收点，则规定链的方向是由到。这里我们按照方向又可以将链上的弧被分为两类：若弧的方向与链的方向相同，则称之为前向弧。前向弧的全体记为；若弧的方向与链的方向相反，则称之为后向弧。后向弧的全体记为。

定义 1。4。3。2  设是一个可行流，是从到的一条链，若满足下列两个条件，则称之为关于可行流的增广链。

若对任意的弧，有，即中每一条弧都是非饱和弧。

若对任意的弧，有，即中每一条弧都是非零流弧。

  （4）截集与截量

    设，我们把始点在集合中，终点在集合中的所有弧构成的集合称为弧集，记为。

定义 1。4。3。3  给定一个网络图，若顶点集合被分割为两个非空的集合和，使得，则我们把弧集称为是（分离和的）截集。

显而易见，若把一个网络图中的截集删去，那么便不存在从到的路。所以，直观上说，截集是从到的必经之道。

定义 1。4。3。4  给定一个截集，我们把截集中所有弧的容量之和称为这个截集的容量（简称为截量），记为，即

容易证明，任意一个可行流的流量都小于等于任一截量，即

显然，如果对于任意一个可行流，网络中存在一个截集，使得，那么必定是最大流，同时截集的容量也一定是的所有截集中最小的一个，即最小截集。

定理 1。4。3。1  可行流是最大流，当且仅当不存在关于的增广链。

于是有如下重要定理：

定理 1。4。3。2  最大流量最小截定理：任意一个网络图中，从发点到收点的最大流的流量等于分割和两点的最小截集的容量。

第二章 交通运输网络的图论模型建立与最大流问题

2。1 交通运输网络的图论模型的建立

2。1。1交通运输模型问题的引入 来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

  交通运输最优化要求在满足各个地区物资需求的前提下,以最少的运输费用将尽量多的物资从一个地区输送到另一个地区,要满足该要求，我们必须从三个方面考虑问题: 

   （1）满足各地区的最低物资需求； 

   （2）将尽量多的物资从一个地区输送到另一个地区； 

   （3）总运输费用最小。 

为了更好地从这三个方面处理该问题,我们先用数学语言描述它。

已知有个物资仓库。可供应某种物资，其供应量（库存量）分别为，有个销售地区，其需求量分别为。从到运输单位物资的运价（单价）为，从到道路运输能力为，从到的运量为。 

由此，我们以总运输费用最少为目标函数,以各地区物资需求量、各仓库物资库存量和道路运输能力为约束条件构建模型如下