最大流问题的典型例子有物流配送、输水管路等。比如:某地区的自来水供应是由地下的水管网路组成，两个地点之间由粗细不一的水管连接，粗水管的输水能力大，细水管的输水能力小，请规划一个合理的水量和管路组合，使得从水源地到目的地能够获得最大的水量。

可行流

$ (C{ij},X{ij}) $中$C{ij}{\geq}0$表示容量，$X{ij}$表示流量，也可以记作$f_{ij}$

通过弧$(Vi,V_j)$流的数量称为流量，记作$X{ij}$

所有弧上流量的集合${X_{ij}}$称为网络$D$的一个流，$X$标注了流量和容量的有向图称为流量图

发点$V_s$：仅有出弧而无入弧

收点$V_t$：仅有入弧而无出弧

条件

满足条件的流为可行流

  1. 容量条件

  2. 平衡条件

    平衡条件

    发出点$V_s$的净输出量：$3+2+4=9$

    收点处$V_t$的净输入量：$6+3=9$

增广链

可行流$X$（有的用$f$表示）是最大流的充分必要条件是不存在从$V_s$到$V_t$的关于流$X$（或用$f$表示）的一条增广链。

最大流求解（已给可行流）

求解最大流就是争取将收点处的入流调整到最大值，但是不能随意的调整入流，因为每一个点进行调整时就会关系到其他点，所以需要可行的办法来进行求解，下面我们将使用Ford-Fulkerson方法进行求解最大流

如图，

最大流求解示意图

我们起点是$V_s$，我们将点$V_s$设置为$(0,+{\infty})$，然后随意找一个与之相连的点，我们选取$V_1$，比较$4-3$和$+{\infty}$的大小，选取小的，于是${\delta}$就取最小的那个，在这里我们取$1$，接下俩再取与之连着的点，发现连着$V_2$的那条前向弧是饱和的，不能选中，所以我们选中连着$V_3$的前向弧，比较$3-2$和${\delta}$的大小，发现一样大，我们就可以保持不变，后面都是这样选择，最后发现选出来的是$V_s \to V_1 \to V_3 \to V_2 \to V_t $这条链，而${\delta}$取的是$1$，此时我们发现可以增加$1$。

接下来更新流量，再次重复上述的步骤，直至最后无法进行更新操作，最终求得的就是最大流。