许多系统存在流的问题.例如，运输系统中有物资流，公交系统中有车辆流，供水系统中有水流等等.我们用网络图来描述系统，研究网络中流的问题.

例6－27　若发点A1及A2处分别有物资12吨及24吨，而收点B1及B2处分别需要物资16吨及20吨.运输线路如图6－54所示，其中F1，F2和F3为转运点，边旁数字为该运输线路运送该物资所允许的最大输送量.问如何调运物资，使从A1及A2处有最多的物资输送到B1及B2处？

图6－54

现作图6－54的同构图——图6－55.以顶点x1及x2（称为源）分别表示发点A1和A2；以顶点y1及y2（称为汇）分别表示收点B1和B2；而v1，v2和v3（称为中间顶点）表示转运点F1，F2和F3.把发点A1和A2处需要输送的物资数写在顶点x1和x2旁，数字前加上“＋”号；把B1和B2处需要的物资数写在顶点y1和y2旁，数字前加上“－”号.图6－55中边旁数字（称为容量）为图6－54相应边运送该物资所允许的最大输送量.我们称图6－55这样的网络为运输网络.

图6－55

图6－56

如果对这个运输问题指定了一个具体的运输方案，如表6－25所示.

如果我们将表6－25所给的点与点之间的运量写在运输网络图6－55相应边的旁边（如图6－56所示），并将运输网络中从顶点u至顶点v的运量视为边（u，v）的函数f（u，v），则该运输方案就可以视为运输网络的一个流f.

表6－25

下面我们给出运输网络和流的数学定义.

运输网络——给有向图N＝（V，E），若对任一边e∈E，有相应的一个非负整数C（e），且已取定V的两个非空子集X及Y，X∩Y＝∅，则称N＝（V，E，C，X，Y）为一个运输网络.X中顶点x称为N的源，Y中顶点y称为N的汇，I＝V－（X∪Y）中顶点称为中间顶点，C（e）称为边e的容量.

设f（e）为一个以E为定义域、取值为非负整数的函数，又记f＋（v）为以v点（v∈V）为起点的所有有向边（v点的输出边）的相应函数值之和，f－（v）为以v点为终点的所有有向边（v点的输入边）的相应函数值之和.

网络流——若对于网络N，其上非负整数函数f（e）满足以下两条件：

则称f为N上一个网络流，简称流.并称f（e）为流f在边e上的流量.条件（6－17）称为容量约束条件，条件（6－18）称为守恒条件（直观上说，在每一个中间点v上，v的流入量之和等于v的流出量之和，中间点的流量是守恒的）.

显然，任一个运输网络N，至少存在一个流：f（e）≡0，e∈E.我们称它为零流.

图6－57

例如图6－57所示为一个石油管道输送系统图，它是一个运输网络，其中源x1和x2为油井，汇y1和y2为油库，中间点v1，v2，v3和v4为泵油站.有向边为石油输送管道，边e旁第一参数为管道e在单位时间内允许的最大输送量C（e），第二参数为管道e在单位时间内具体的流量f（e）.

为了方便算法的使用，我们用下列方法将多源和多汇的运输网络N化成单源和单汇的运输网络N′：

①在N中添加两个新的顶点x和y，分别成为N′中的源和汇，N的顶点集V成为N′的中间顶点集；(www.daowen.com)

②对x′∈X，用有向边（x，x′）连接顶点x和x′，边（x，x′）的容量C（x，x′）视具体问题为＋∞或某一数值；

③对y′∈Y，用有向边（y′，y）连接顶点y′和y，边（y′，y）的容量C（y′，y）视具体问题为＋∞或某一数值.

若f是N上一个流，定义N′上函数f′：

可知，f′是N′上的一个流（反之，若在N′上有一个流f′，把它限制到N上，即得N上一个流f）.

例6－28　将图6－55所给运输网络N化成单源和单汇的运输网络N′，且由图6－56中的流f给出N′上相应流f′.

解　对N添加顶点x和y.

由于x1及x2的发量分别为12和24，故在N′中（x，x1）的容量为12，（x，x2）的容量为24.由图6－56知，f′在（x，x1）上流量为12，在（x，x2）上流量为23.

由于y1及y2的收量分别为16和20，故在N′中（y1，y）的容量为16，（y2，y）的容量为20.由图6－56知，f′在（y1，y）上流量为15，在（y2，y）上流量为20.

N′和其上流f′由图6－58给出.边e旁参数为（C（e），f（e））（以后都如此，不再说明）.

图6－58

例6－29　将图6－57所给运输网络N化成单源和单汇运输网络N′，并由N上流f给出N′上流f′.

解　对图6－57添加顶点x和y.

由于油井x1和x2处石油输出量未加限制，故在N′中，容量

图6－59

今后我们讨论的运输网络N都为具有单源x和单汇y的网络：N＝（V，E，C，x，y）.

流值Valf——称f＋（x）为流f在N上的流值，记为Valf.

显然，有

例如，在图6－58中，流f的流值Valf＝35，该运输方案为：从发点x1输出物资12吨，从发点x2输出物资23吨.

对于图6－59来说，Valf＝40，油井x1在单位时间内输出石油25个单位，油井x2在单位时间内输出石油15个单位.