Для графа G, заданного матрицей пропускных способностей дуг, найти максимальный поток от вершины x1 до вершины x7 и указать минимальный разрез.

Используем алгоритм Форда-Фалькерсона:

- выбираем один из путей от вершины 0 до вершины 7, выделяя элементы матрицы пропускных способностей для дуг этого пути;

- уменьшаем пропускные способности дуг этого пути на минимальную пропускную способность дуг этого пути;

- симметричные элементы относительно главной диагонали дуг этого пути увеличиваем на минимальную пропускную способность дуг этого пути;

- повторяем эти действия, пока есть пути из 0 до 7;

Путь 1-3-5-6-7, min(10;12;7;9)=7