最大流问题
最大流问题的典型例子有物流配送、输水管路等。比如:某地区的自来水供应是由地下的水管网路组成,两个地点之间由粗细不一的水管连接,粗水管的输水能力大,细水管的输水能力小,请规划一个合理的水量和管路组合,使得从水源地到目的地能够获得最大的水量。
可行流
$ (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$:仅有入弧而无出弧
条件
满足条件的流为可行流
容量条件
平衡条件
发出点$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$。
接下来更新流量,再次重复上述的步骤,直至最后无法进行更新操作,最终求得的就是最大流。
- 感谢你赐予我前进的力量