定义20设有向连通图的每条边上有非负数称为边容量，仅有一个人次为0的点称为发点（源），一个出次为0的点称为收点（汇），其余点为中间点，这样的网络G称为容量网络，常记做。对任一G中的边有流量，称集合为G的一个流。称满足下列条件的流为可行流：（1）容量限制条件：对G中每条边，有（2）平衡条件：对中间点，有（即中间点的物资的输入量与输出量相等）对收、发点有（即从点发出的物资总量等于点输入量）W为网络流的总流量。可行流总是纯在的，例如就是一个流量为0的可行流。所谓最大流问题就是在容量网络中，寻找流量最大的可行流。一个流，当则称流对边是饱和的，否则称对不饱和。最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。定义21容量网络为发、收点，若有边集为E的子集，将G分为两个子图其顶点集合分别记分属，满足：①不连通；②为的真子集，而仍连通，则称为G的割集，记。割集中所有始点在S，终点在的边的容量之和，称为的割集容量，记为。如图5-41中，边集和边集都是G的割集，它们割集容量分别为9和11。容量网络G的割集有多个，其中割集容量最小者称为网络G的最小割集容量（简称最小割）。二、最大流-最小割定理由割集的定义不难看出，在容量网络中割集是由到的必经之路，无论拿掉哪个割集，到便不再相通，所以任何一个可行流的流量不会超过任一割集的容量，也即网络的最大流与最小割容量（最小割）满足下面定理。定理10设f为网络G=(V,E,C)的任一可行流，流量为是分离的任一割集，则有由此可知，若能找到一个可行流一个割集，使得的流量，则一定是最大流，而就是所有割集中容量最小的一个。下面证明最大流-最小割定理，定理的证明实际上就是给出了寻找最大流的方法。定理11（最大流-最小割定理）任一网络G中，从到的最大流的流量等于分高的最小割的容量。证明设是一个最大流，流量为W，用下面的方法定义点集令若点且则令若点且则令在这种定义下，一定不属于，若否，,则得到一条从到的链，规定到为链的方向，链上与方向一致的边叫前向边，与方向相反的边称为后向边，即如图5-42中为前向边为后向边。根据的定义，中的前向边上必有，后向边上必有令当为前向边当为后向边取，显然。我们把修改为：为上前向边为后向边其余不难验证仍为可行流（即满足容量限制条件与平衡条件），但是的总流量等于的流加，这与为最大流矛盾，所以不属于。令，则。于是得到一个割集，对割集中的边显然有但流量W又满足所以最大流的流量等于最小割的容量，定理得到证明。定义22容量网络G，若为网络中从到的一条链，给定向为从到,上的边凡与同向称为前向边，凡与反向称为后向边，其集合分别用和表示，f是一个可行流，如果满足则称为从到的（关于f的）可增广链。推论可行流f是最大流的充要条件是不存在从到的（关于f的）可增广链。可增广链的实际意义是：沿着这条链从到输送流，还有潜力可挖，只需按照定理证明中的调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。这样就得到了一个寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。三、求最大流的标号算法设已有一个可行流f，标号的方法可分为两步：第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。1.标号过程（1）给发点以标号（2）选择一个已标号的顶点，对于的所有未标号的邻接点按下列规则处理：a)若边，且则令，并给以标号。b)若边，且时，令并给以标号（3）重复（2）直到收点被标号或不再有顶点可标号时为止。如若得到标号，说明存在一条可增广链，转（第2步）调整过程。若未获得标号，标号过程已无法进行时，说明f已是最大流。2.调整过程若是可增广链上的前向边（1）令若是可增广链上的后向边若不存在可增广链上（2）去掉所有标号，回到第1步，对可行流重新标号。例5.17图5-43表明一个网络及初始可行流，每条边上的有序数表示，求这个网络的最大流。先给标以。检查的邻接点发现点满足且令，给以标号。同理给点以标号。检查点的尚未标号的邻接点发现满足且令给以标号。检查与点邻接的未标号点有，发现点满足且，令则给点以标号。点未标号，与邻接，边且所以令给以标号。类似前面的步骤，可由得到标号。由于已得到标号，说明存在增广链，所以标号过程结束，见图5-44。转入调整过程，令为调整量，从点开始，由逆增广链方向按标号找到点，令。再由点标号找到前一个点，并令。按点标号找到点。由于标号为为反向边