Условие задачи
Для графа G, заданного матрицей пропускных способностей дуг, найти максимальный поток от вершины x1 до вершины x7 и указать минимальный разрез.
Ответ
Используем алгоритм Форда-Фалькерсона:
- выбираем один из путей от вершины 0 до вершины 7, выделяя элементы матрицы пропускных способностей для дуг этого пути;
- уменьшаем пропускные способности дуг этого пути на минимальную пропускную способность дуг этого пути;
- симметричные элементы относительно главной диагонали дуг этого пути увеличиваем на минимальную пропускную способность дуг этого пути;
- повторяем эти действия, пока есть пути из 0 до 7;
Путь 1-3-5-6-7, min(10;12;7;9)=7
Потяни
