求图5-12所示的网络最大流。
求图5-12所示的网络最大流。
发布时间：2025-06-04 13:37:23
请在 下方输入 要搜索的题目：
推荐参考答案 (
由 快搜搜题库 官方老师解答 )
答案：图5-11中已有一个值为4的可行流。先用标号法找增广链：s标号：(0， ∞)；1标号：(s，4)；2标号：(-1，1)；3标号：(-2，1)；t标号：(3，1)。 反向追踪得增广链：P={s，(s，1)，1，(2，1)，2，(3，2)，3，(3，t)，t}，θ=1，调整后得图5-12，可行流的值为5。 再找增广链：s标号：(0， ∞)；1标号：(s，3)。s已检查，再检查点1，后向弧(2，1)上f(2，1)=0，前向弧(1，3)上f(1，3)=b(1，3)=2，标号进行不下去，故已得最大流，其流值为5。 对应最小截集(W， )，W={s，1}， ={2，3，4，t}。其截集容量为：C(W， )=b(s，2) b(1，3)=3 2=5。 说明：Ford-Fulkerson方法是有缺点的。曾有人举出一个例子，当网络的容量是无理数时，用Ford-Fulkerson方法可能找不到最大流。1972年Edmonds和Karp提出了一种改进方法，克服了上述缺点。
