Теория потоков, без сомнения, представляет собой один из наиболее хорошо изученных разделов комбинаторной оптимизации, имеющий разнообразные приложения, как теоретические, так и практические.

Курс начнется с краткого введения в предмет, в котором мы разберем базовые алгоритмы для задачи о максимальном потоке, а затем быстро перейдем к более современным темам: проталкиванию предпотока и параметрическим потоковым задачам. В заключительной части курса коснемся обобщений понятия потока: изучим простейшие виды мультипотоковых задач, а также поговорим о потоках в кососиметрических и двунаправленных графах.

От слушателей предполагается знакомство с базовыми понятиями алгоритмической теории графов.

Предполагаемые темы, которые будут затронуты на занятиях:

1. Задача о максимальном потоке и простейшие способы ее решения: алгоритмы Форда-Фалксерсона, Эдмондса-Карпа и Диница

2. Оценки Карзанова для количества фаз алгоритма Диница

3. Масштабирование пропускных способностей

4. Проталкивание предпотока: общая схема, разгрузка вершин

5. Стратегии разгрузки предпотока

6. Быстрая декомпозиция мультитерминальных потоков

7. Двухфазные алгоритмы проталкивания предпотока

8. Эвристики, ускоряющие работу алгоритмов проталкивания предпотока

9. Параметрический максимальный поток

10. Задача о подграфе максимальной плотности

11. Динамические деревья в задачах о максимальном потоке

12. Алгоритм Гольдберга-Рао

13. Свободные мультипотоки: теорема Ловаса-Черкасского, алгоритм Ибараки-Карзанова-Нагамочи

14. Бипотоки и биразрезы в неориентированных графах: теорема Ротшильда-Винстона, алгоритм Ху

15. Потоки в кососимметрических и двунаправленых графах, приложения к недвудольным паросочетаниям