Условие задачи
Найти максимальный поток и минимальный разрез:
Ответ
Нарисуем заданную транспортную цепь.
В кружках - номера вершин, на дугах проставлены их пропускные способности.
Находим максимальный поток в сети методом Форда-Фалкерсона и соответствующий минимальный разрез.
Зададим нулевой поток (его будем писать в скобках за пропускными способностями ребер):
Потяни
