Потоки

1. [Ваня] Потоки
1. Два неперсекающихся по ребрам пути − поток. k неперсекающихся по ребрам пути − поток.
2. Определение потока (f) в общем случае. 0 ≤ f ≤ c. Сумма f для каждой вершины = 0. f[e] = -f[e']
3. Разрез. Min Cut ≤ Max Flow.
4. Теорема и алгоритм Форда Фалкерсона поиска потока за O(|f| × E)
5. Декомпозиция потока (разбиение на пути и циркуляцию) за O(E²). За O(VE).
6. Решение задачи о k неперсекающихся по ребрам пути. Картинка, почему "просто k раз пустить dfs" не работает.
7. Непересекающиеся по вершинам пути. Раздвоение вершин.
8. Ориентированный граф и неориентированный граф. Два способа представления неориентированного.
9. Нахождение паросочетания в двудольном графе с помощью потока за O(VE).
2. [Ваня] Потоковые Фишечки
1. Несколько истоков и стоков
2. Избытки и недостатки в вершинах
3. [L,R]-циркулция (с нижними и верхними ограничениями)
3. [Ваня] Алгоритмы поиска потока
1. Общая идея #1: проталкивать максимум
2. Эдмондс-Карп (bfs, VE² = E × VE). А еще он работает на вещественных пропускных способностях.
3. Масштабирование, оно же Scaling (2^k, E²logU, а в реальности даже E²)
4. [Ваня] Задачи
1. [flow] Выделение k-регулярного рёберного подграфа из двудольного (определок: совершенное паросочетание, регулярность)
2. [flow] Восстановление матрицы (есть суммы строк и столбцов, каждое число от 0 до 100)
3. [flow] Турнирная таблица (нужно доиграть несыгранные матчи, чтобы получились нужные суммы очков)
4. [NP-hard] Поиск A-B и C-D путей