max-flow - 最大流量最小切割

Question

所以我计算出最大流量为 10，因此意味着最小切割也为 10，但是我如何在此图像上绘制最小切割 10？

Answer 1

让我假设：

1. S 顶部的顶点是 A (S -> A = 6)
2. S右边的顶点是C (S -> C = 6)
3. A 右边的顶点是 B (A -> B = 3)
4. C 右边的顶点是 F (C -> F = 3)
5. 图底部的顶点是 D (S -> D = 2 )

所以最终的最小切边是：

A -> B = 3

C -> F = 3

S -> D = 2

C -> D = 2

源顶点也是：S、A、C