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