Лекция 12. Потоки

Определения: сеть, поток, задача о макс. потоке; разрез: поток и проп. способность; остаточная сеть, дополняющий путь. Теорема Форда-Фалкерсона. Метод Форда-Фалкерсона, реализация за O(F E). Поиск мин. разреза через поток. Проблемы мет. Ф.-Ф.: большое F в малом графе, зависание в вещественном случае. Алгоритм Эдмонса-Карпа: проталкивание вдоль кратчайшего пути (BFS). Лемма о неубывании расстояний, оценка количества насыщений, общее время O(V E^2). Алгоритм масштабирования Габова. Лемма: после delta-фазы остаётся менее (delta |E|) потока. Общее время O(E^2 log C). Метод Диница: сеть кратчайших путей и слои, блокирующий поток. Не более O(V) фаз. Поиск блокирующего потока за O(V E) с удалением рёбер, общее время работы O(V^2 E).