Пятая лекция (потоки)

  1. Форд-Фалкерсон
    1. Теорема
    2. Конструктивно получили поток за O(|f|×E) и разрез по потоку умеем строить за O(E)
    3. Декомпозиция потока за min(O(VE), O(|f|×E))
    4. Разрез минимального веса -- это тоже самое, что и обычный разрез
    5. Ориентированный граф, неориентированный граф
    6. Вершинный поток, разрез
    7. Задача про k непересекающихся путей. Разбор в ориентированном/неориентированном, вершинном/реберном случаях.
    8. Хранение графа списком ребер
    9. Минусы матрицы смежности: V2 и неудобно поддерживать кратные ребра
  2. Фишечки
    1. Несколько истоков и стоков
    2. Избытки и недостатки в вершинах
    3. [L,R]-циркулция (с нижними и верхними ограничениями)
    4. [L,R]-поток
  3. MinCost
    1. O(|f|×MinPath)
    2. Доказательство корректностипоиск (рассмотрели разность k+1 и k)
    3. Отрицательные циклы. Как их искать, что с ними делать?
    4. Форд-Беллман (обычный, с очередью, Левит)
    5. Дейкстра и потенциалы
    6. Реализации Дейкстры: set, куча, k-ичная куча, дерево отрезков
    7. Случай ориентированного (2E ребер) и неориентированного графа (4E ребер)
  4. Задачи
    1. Паросочетание в двудольном
    2. Выделение k-регулярного подграфа из двудольного
    3. Покрытие грида с дырками доминошками
    4. Покрытие грида с дырками горизонтальными и вертикальными отрезками
    5. Паросочетание минимального веса в двудольном
    6. Восстановление матрицы
    7. Округление матрицы
    8. Турнирная таблица
    9. Ориентация графа
    10. Удаление графа за минимальноую стоимость
    11. Поиск цикла через s и t в неор графа, в ор графе
    12. Поиск A-B и C-D путей
    13. Люди (отрезок времени) и самолеты (вместимость)
    14. K автоматов, выполнить i-заказ = занять один из автоматов в отрезок [Li..Ri]
    15. K автоматов, у каждого заказа есть стоимость (построим два графа, в одном много ребер, в другом мало)
    16. Работы и инструемнты
    17. Поиск подграфа максимальной плотности в неор графе
    18. Матан (поиск замкнутого подграфа в орграфе максимального веса)
  5. Алгоритмы поиска потока
    1. Форд-Фалкерсон -- O(|f|×E)
    2. Эдмондс-Карп -- O(E2V)
    3. Масштабирование -- O(E2)
    4. Диниц + Масштабирование -- O(VElogU)
    5. Хопкрофт-Карп = Диниц для графа паросочетания, работает за O(E√ V )
    6. Push and Relabel -- O(V3), O(V2√ E )
    7. Global Relabeling -- Just very fast
    8. Relabeling with Scaling -- O(VE + V2logU)
  6. Алгоритмы поиска mincost потока
    1. Форд-Беллман или Дейкстра
    2. Последовательное вычеркивание циклов минимального среднего веса
    3. Венгерский алгоритм для задачи о паросочетании макс веса