Лекция 12. Потоки (Алгоритмы и структуры данных, часть 2)

Определения: сеть, поток, задача о макс. потоке; разрез: поток и проп. способность; остаточная сеть, дополняющий путь. Теорема Форда-Фалкерсона. Метод Форда-Фалкерсона, реализация за 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). Лекция №12 в курсе "Алгоритмы и структуры данных, часть 2", весна 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: https://bit.ly/2II8OsD Все видео курса по порядку: https://goo.gl/b8KQcs