计算题
求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。
【正确答案】
（1）通过标号法求得第一条增广链，Vs、V2、V4、V3、Vt，调整量为1，如下图
（2）通过第二次标号法得增广链，Vs、V1、V4、Vt，调整量为2，如下图
【答案解析】
求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。
（1）通过标号法求得第一条增广链，Vs、V2、V4、V3、Vt，调整量为1，如下图
（2）通过第二次标号法得增广链，Vs、V1、V4、Vt，调整量为2，如下图