Строки. Конец.

  1. Суф. массив
    1. Построение за O(NlogN)
    2. LCP[i,j] за O(N2)
    3. LCP[i,i+1] за O(N) (алгоритм Касаи)
  2. Ахо-Корасик
    1. Префикс-функция
    2. Суффиксные (префиксные) ссылки на боре
    3. Алгоритм Ахо-Корасика
    4. Док-во корректности и времени работы при построении полного автомата
    5. Док-во времени работы при построении только суф. ссылок

Потоки

  1. Вершинные потоки
  2. Потоки с несколькими истоками, стоками
  3. Потоки с избытками и недостатки в вершинах, сток и исток отсутствуют
  4. Потоки с избытками и недостатки в вершинах, некоторые вершины могут быть стоками и истоками.
  5. [L,R] потоки.
    1. Решение за O(MinCostFlow).
    2. Решение за O(Flow): Ребро [L,R] заменяем на ребро [0,R-L] и избыток и недостаток в концых ребра.
  6. Быстрые потоки: нужно помнить, что теоретически оптимальные алгоритмы поиска потока работают ~O(VE).

Разрезы

  1. (s,t) разрез ищется потоком
  2. Разрез минимальной стоимости: Summ(w[e]), Summ(w[e]*c[e]) ищутся так же. Т.е. можно для любой f(e) >= 0 минимизировать сумму по разрезу f(e).
  3. Глобальный разрез. Наивное построение за O(N*Flow)
  4. Глобальный разрез. Нахождение за O(N3) (алгоритм Штор-Вагнера без док-ва).
  5. Глобальный разрез. Вероятностный алгоритм Каргера-Штейна.
    1. Формулировка задачи: нет кратных ребер, нужно удалить из графа мин. число ребер так, чтобы он стал несвязным.
    2. Вероятностное решение за O(N4): будем N-2 раз выбирать случайное ребро и стягивать по нему 2 вершины.
    3. Улучшение до O(N2logN): будем ветвиться на 2 процесса в тот момент, когда вероятность ошибки = 1/2.
    4. Вероятностный - алгоритм, выдающий корректный ответ с вероятностью >= 1/2. Реально алгоритм работает за O(N2 * logN * logP).
  6. Связь задач поиска глобального разреза и кластеризации.

Паросочетания

  1. Двойственность цепей и антицепей. Теорема Дилворта без док-ва.
  2. Not read Короткое док-во теоремы Дилворта.
  3. Задачка про такси, сведение к паросочетанию.
  4. Теорема о чередующейся дополняющей цепи для произвольного графа.
  5. Напоминание min-max Теоремы для двудольного графа (maxM = minC)
  6. Теорема Татта-Берджа для произвольного графа.
    1. maxM <= down(V/2)
    2. maxM <= сумма по всем компонентам связности down(Vi/2)
    3. maxM <= V - (число нечетных компонент связности) = f(G)
    4. maxM <= |U| + f(G/U) для любого U
    5. Собственно теорема: maxM = min по U (|U| - f(G/U)). Пример с цветочком.
    6. Док-во Теоремы Татта Берджа:
    7. Если есть вершина, при удалении которой размер паросочетания уменьшится, выкенем ее из G, докажем теорему, а потом добавим и в G и в U.
    8. При удалении любой вершины размер max паросочетания не меняется. Докажем, что, если граф связен, maxM = down(V/2).
    9. Пусть граф связен и 2maxM + 2 = V. Найдем чередующийся путь между этими двумя вершинами.
  7. Паросочетание в произвольном графе (Эдмондс)
  8. Вероятоностные алгоритмы для нахождения паросочетания в произвольном графе.
  9. Матроиды.
    1. Построение MST: алгоритм Краскала = отсортировали ребра по весу и в таком порядке пробуем их добавлять в ответ.
    2. Построение базиса минимального веса: отсортировали вектора по весу и в таком порядке пробуем их добавлять в ответ.
    3. Паросочетание минимального по сумме весов вершин первой доли весу: отсортировали и...
    4. Пытаемся доказать и обобщить. Утверждение: множество остовных лесов данного графа образуют Матроид.
    5. Матроид = множество хороших множеств. Определение Матроида = 3 аксиомы.
    6. Трансверсальный и векторный матроиды.
    7. Алгоритмы Радо-Эдмондса: получения max по размеру, а из таких min по сумме весов хорошего множества.