Сеть задана матрицей весов, которая получена из матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки: Вершина с номером 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 ...