Потоки. Введение.

  1. 2 неперсекающихся по ребрам пути - поток. k неперсекающихся по ребрам пути - поток.
  2. Определение потока (f) в общем случае. 0 <= f <= c. Сумма f для каждой вершины = 0. f[e] = -f[e']
  3. Решение задачи о k неперсекающихся по ребрам пути. Картинка, почему "просто k раз пустить dfs" не работает.
  4. Непересекающиеся по вершинам пути. Раздвоение вершин.
  5. Разрез C(A,B) - разрез между множествами. C(s,t) - разрез между вершинами. |C(s,t)| >= |f(s,t)|.
  6. Теорема и алгоритм Форда-Фалкерсона. Если нет дополняющего пути, |C(s,t)| = |f(s,t)|. Алгоритм ищет и поток, и разрез за O(|f|*E)
  7. Нахождение паросочетания в двудольном графе с помощью потока за O(VE).

Потоки. Алгоритмы поиска.

  1. Пускаем каждый раз максимум по пути
  2. Алгоритм Эдмондса-Карпа за O(VE2) (пускаем bfs)
  3. Масштабирование за O(E2logMax) (пускаем не менее 2k)
  4. 1 + 3 = O(E2)

MinCost Потоки.

  1. Задача: ищем поток размера k минимального веса. Обратное ребро имеет вес (-w).
  2. Формулировки прикладных задач: Задача о назначениях. Транспортная задача.
  3. Алгоитм поиска: База = нет отрицательных циклов, переход = добавляем инимальный путь.
  4. Док-во корректности: рассмотрим разность mincost потока размера (k+1) и mincost потока размера (k).
  5. Улучшенные алгоритмы поиска пути: Форд-Белман с очередью и Дейкстра.

Потоки. Обобщение.

  1. Вершинные потоки
  2. Потоки с несколькими истоками, стоками

Задачи

  1. Покрытие грида с дырками доминошками
  2. Футбольный турнир от Пети Митричева
  3. Восстановление матрицы по суммам в сторках и столбцах