Сеть задана матрицей весов, которая получена из матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки: Вершина с номером 1 является источником, вершина с номером 6 - стоком. Чему равна величина максимального потока?

Найдем величину максимального потока в сети с источником 1 и стоком 6. Для этого применим метод Форда–Фалкерсона и рассмотрим последовательные поиски аугментирующих путей.

Исходная матрица задаёт следующие дуги и их пропускные способности:

• 1 → 2: 4 • 1 → 3: 2 • 1 → 4: 8 • 1 → 5: 3 • 2 → 5: 7 • 3 → 2: 4 • 3 → 5: 3 • 3 → 6: 4 • 4 → 3: 3 • 4 → 6: 6 • 5 → 6: 9

Наша цель – отправить максимальное количество потока из вершины 1 в вершину 6.

───────────────────────────── Шаг 1. Найдем первый аугментирующий путь.

Выберем путь: 1 → 4 → 6

Пропускные способности дуг на пути: 1 → 4: 8 ...