Максимальный поток Min Cut

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