1。4 图与网络流相关知识

1。4。1 图的概念

   定义 1。4。1。1 一个图定义为一个偶对，记作，其中

   （1）是一个非空集合，其中的元素称为顶点；

   （2）是无序积中的一个子集合，其中的元素称为边或弧；

注：集合中的元素可以在子集合中出现不止一次。

    我们分别用和表示图的顶点集合与边的集合。如果和都是有限集合，则称为有限图；否则称为无限图。

定义 1。4。1。2 一个有向图定义为一个偶对，其中

   （1）是个非空集合，其元素称为顶点；

   （2）是有序积的一个子集合，其中的元素称为边或弧。

 根据有向图的定义可以得出，在有向图中与一条弧相连的两个端点（即图的顶点）存在次序关系，即弧是顶点和的有序对。我们称为弧的起点，为终点。如果对有向图的每一条弧表示从起点到终点作一条矢线，方向是从指向，即有向图的每一条弧都有确定的方向。因此，有向图就是每条边都有一定方向的图。

1。4。2 网络与流

    定义 1。4。2。1  给定一个有向图，在中指定了一点为发点（记为），而另外一点为收点（记为），其余的点都称为中间点。对于有向图中的每一条弧，都会相对应跟着一个（或简写为），我们称其为弧的容量。通常我们就把这样的叫做一个网络。记作

所谓图论网络上的流，就是定义在弧集合上的一个函数，我们称为弧上的流量（有时也简记作）。

1。4。3可行流与最大流

    观察交通运输网络中不同类型的实际问题，我们可以发现对于流的特性有两个明显且必须的要求：一是网络中每条弧上的流量都不能大于该弧的容量；二是所有中间点的流量必须为零。因为对于每一个点，进入该点的流量与离开该点的流量之差，就是该点的净输出量，简称为该点的流量；但是由于中间点的作用只是传送，显然每个中间点的流量必为零。由此可以总结出，发点的净流出量必需等于收点的净流入量，也是该网络中此方案的总输送量。因此有：

   定义 1。4。3。1  满足下述条件所诉的流可称之为可行流：

  （1）容量限制条件：对每一弧

  （2）平衡条件：

    对于中间点：流入量和流出量相等，即对每一个有

    对于发点，记

    对于收点，记

    式中，称为该网络可行流的流量，其流量值为发点的净输出量（即收点的净输入量）。

    可行流总是存在的。比如最简单地，我们令所有弧的流量都为零，即，就可以得到一个可行流，称为零流。其流量。

    然而本文我们研究的最大流是什么呢，其实最大流问题就是寻求一个流使其流量达到最大，并且满足下列条件：

                                                   ①

                                       ②

可以看出，最大流问题本质上是一个特殊的线性规划问题。即求一组，在满足条件①和②下使达到极大。在第二章的第二节中将会看到，我们采取了图论的优势，解决这个问题的方法较之线性规划的一般方法要简单、直观得多。

  （3）增广链

若给定一个可行流，我们可将网络中的弧分为两类。