Потоки (СПБГУ МатМех, весна 2013, спецкурс 344-й группы)

  1. Определения
    1. 2 неперсекающихся по ребрам пути - поток. k неперсекающихся по ребрам путей - поток.
    2. Определение потока f в общем случае: (1) 0 ≤ fe ≤ ce. (2) Сумма fe для каждой вершины равна 0. (3) fe = -fe'
    3. Решение задачи о k неперсекающихся по ребрам путях. Картинка, объясняющая, почему "просто k раз пустить dfs" не работает.
    4. Разрез C(A,B) - разрез между множествами. C(s,t) - разрез между вершинами.
    5. Лемма: любой разрез |C(S,T)| >= |F(S,T)| = |f|.
  2. Форд-Фалкерсон
    1. Алгоритм Форда-Фалкерсона для поиска max потока за O(|f|*E).
    2. Теорема Менгера, Теорема Форда-Фалкерсона, формулировки.
    3. Доказательство теоремы Форда-Фалкерсона. Поиск min разреза по готовому max потоку за O(E).
    4. Хранение графа и короткая реализация dfs-а для потока.
  3. Модификации
    1. Ориентированный и неориентированный граф
    2. Вершинный поток (и вершинно непересекающиеся пути)
    3. Вершинный разрез (пример с препятствиями на гриде)
    4. Несколько истоков и стоков
    5. Избытки и недостатки (переправить все избытки в недостатки)
    6. [L,R]-циркуляция
    7. [L,R]-поток
    8. Задача "найти два непересекающихся пути: из A в B и из C в D"
  4. Применения потоков
    1. [flow] Нахождение max паросочетания в двудольном графе с помощью потока за O(VE).
    2. [flow] Даны суммы в строках и столбцах матрицы. Восстановить матрицу с такими суммами, чтобы все элементы были от 0 до 100.
    3. [LR-flow] Нужно округлить вещественную матрицу так, чтобы суммы в строках и столбцах тоже округлились.
    4. [flow] Дана недоигранная турнирная таблица и окончательные суммы очков. Ничей не бывает. Восстановить таблицу.
    5. [cut] Дан ориентированный граф, у вершины i есть ценность wi. Выбрать замкнутое множество вершин с положительной суммой wi.
    6. [flow-easy] Простой цикл, проходящий через s и t
    7. [flow] Люди и самолеты. У самолета есть время вылета и вместимость, у человека есть отрезок допустимых времен вылета.
    8. [cut] Работы и инструменты (или гранты и критерии, по которым они выдаются).
  5. Алгоритмы поиска
    1. Проталиквать максимум по пути
    2. Искать путь bfs-ом, а не dfs-ом
    3. Искать сперва толстые пути. Например, размера ≥ 2k.
    4. 1 + 2 = Эдмондс-Карп = O(V2E). Доказательство.
    5. 3 = Масштабирование = O(E2logC). Доказательство.
    6. 1 + 3 = O(E2) в среднем. Пример с полным двудольным графом.
    7. Технические оптимизации: (1) храним не f и c, а c и c-f, (2) храним граф списком ребер, (3) минимум c-f на пути ищем не по ходу dfs, а в конце.