最大流问题给定一个有向图G＝(V,E)，其中仅有一个点的入次为零称为发点（源），记为vs，仅有一个点的出次为零称为收点（汇），记为vt，其余点称为中间点。网络上的流，是指定义在边集E上的函数f＝{f(vi,vj)}，并称f(vi,vj)为边(vi,vj)上的流量，简记为fij。可行流、可行流的流量、最大流。可行流总是存在的，例如f={0}就是一个流量为0的可行流。所谓最大流问题就是在容量网络中寻找流量最大的可行流。一个流f={fij}，当fij=cij，则称f对边(vi,vj)是饱和的，否则称f对边(vi,vj)不饱和。对于不饱和的，其间隙为δij=cij-fij最大流问题实际上是一个线性规划问题。但利用它与图的密切关系，可以利用图直观简便地求解。给定容量网络G＝(V,E,C)，若点集V被剖分为两个非空集合V1和V2，使vs∈V1，vt∈V2，则把边集(V1,V2)称为（分离vs和vt的）割集。vs割集的容量(简称割量)最小割集对于可行流f＝{fij}，我们把网络中使fij＝cij的边称为饱和边，使fij<cij的边称为非饱和边；把使fij＝0的边称为零流边，使fij>0的边称为非零流边。对最大流问题有下列定理：定理1容量网络中任一可行流的流量不超过其任一割集的容量。定理2（最大流-最小割定理）任一容量网络中，最大流的流量等于最小割集的割量。推论1可行流f*＝{fij*}是最大流，当且仅当G中不存在关于f*的增广链。求最大流的标号法标号过程:(1)给vs标号(,+∞)，vs成为已标号未检查的点，其余都是未标号点。(2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和边(vi,vj)，则vj标号(vi,l(vj))，其中l(vj)＝min[l(vi),cij–fij]，vj成为已标号未检查的点；若有非零边(vj,vi)，则vj标号(-vi,l(vj))，其中l(vj)＝min[l(vi),fji]，vj成为已标号未检查的点。vi成为已标号已检查的点。(3)重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号点，表明得到一条vs到vt的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。调整过程：在增广链上，前向边流量增加l(vt)，后向边流量减少l(vt)。下面用实例说明具体的操作方法：例下图中已经标示出了一个可行流，求最大流调整后的可行流如下图：调整后的可行流如下图：具有实际背景的例子用图来描述就是利用标号法（经5次迭代）可以得到从成都发送旅客到北京的最大流量如图所示x1