С прошлых пар

  1. Теорема Дилворта.
    1. Транзитивное замыкание графа.
    2. Покрытие путями = паросочетание в транзитивно замкнутом графе.
    3. N - кол-во вершин, M - размер паросочетания, тогда число путей = N - M.
    4. Размер любой антицепи <= размера любого покрытия путями
    5. Рассмотрим контролирующее множество в графе из 2N вершин. Его размер = M.
    6. Если из исходного графа выкинуть все <= M вершин, половинки которых задействованы в контролирующем множестве, получится антицепь.
    7. Размер антицепи = N - M. Значит max AntiChain = min PathCover.
  2. Теорема Татта-Берджа.
    1. maxM <= down(V/2)
    2. maxM <= сумма по всем компонентам связности down(Vi/2)
    3. maxM <= V - (число нечетных компонент связности) = V - odd(G) = f(G)
    4. maxM <= |U| + f(G/U) для любого U
    5. maxM = min по U (|U| + f(G/U))
    6. Если есть вершина x, такая, maxM(Gx) < maxM(G), удаляем ее.
    7. Получили граф, в котором удаление любой вершины не влияет на maxM
    8. Докажем, что maxM = V - odd. От противного: пусть в какой-то компоненте связности есть 2 свободные вершины s и t.
    9. Строим дополняющий путь (s,t).

Двусвязность, сильная связность: теория

  1. Сильная
    1. Орграф. Для любых s и t есть путь из s в t.
    2. Сильная связность - отношение эквивалентности для вершин
  2. Реберная
    1. Мост - ребро, при удалении которого теряется связность. Определение = нет мостов.
    2. Реберная двусвязность - отношение эквивалентности для вершин
    3. Т1: def <=> между любыми двумя вершинами есть 2 непересекающихся по ребрам пути (док-во = поток)
    4. Т2: def <=> для любых вершин a, b и ребра e есть путь из a в b не проходящий через e.
    5. T3: def <=> ребра графа можно ориентировать так, что полученный граф сильно связен
  3. Вершинная
    1. Точка сочленения - вершина, при удалении которого теряется связность. Определение = нет точек сочленения.
    2. Т1: def <=> между любыми двумя вершинами есть 2 непересекающихся по вершинам пути (док-во = вершинный поток)
    3. Т2: def <=> для любых вершин a, b и вершины v есть путь из a в b не проходящий через v.
    4. T3: def <=> для любых вершин a и b существует простой цикл, проходящий через них.
    5. T4: def <=> для любых вершины a и ребра e существует простой цикл, проходящий через них.
    6. T5: def <=> для любых ребер e1, e2 существует простой цикл, проходящий через них.

Двусвязность, сильная связность: алгоритмы

  1. Все можно делать за O(VE). В лоб.
  2. dfs за O(E). Время входа и время выхода.
  3. Сильная связность за O(E) в 2 dfs-а. Тестирование на 10 min-тестах.
  4. Реберная двусвязность за O(E). Компоненты реберной двусвязности.
  5. Вершинная двусвязность за O(E). Компоненты вершинной двусвязности.
  6. Сильная связность за O(E) одним dfs-ом = алгоритм Тарьяна.
  7. Сильная связность за O(E) двумя dfs-ами:
  8. Если ориентировать все ребра по dfs-у, то компоненты сильной связности = компонентам реберной двусвязности

Эйлеровость.

  1. Критерий эйлеровости.
  2. Поиск эйеровых пути и цикла за O(E) в лоб (найдем циклы, склеим циклы)
  3. Поиск эйеровых пути и цикла за O(E) одним dfs-ом.
  4. Дополнение графа до Эйлерова.

Гамильтоновость

  1. Теорема Дирака (1952): если у любой вершины deg >= n / 2, граф гамильтонов.
  2. Алгоритм построения за O(N3) и док-во. На самом деле алгоритм работает за O(N2).
  3. Теорема Оре (1960): deg v + deg u >= N для любых u и v не связных ребром.
  4. Теорема 3: deg[k] > k для всех k < n / 2, где deg[i] - i-я по возрастанию степень.
  5. Теорема Хватала (1972): признак гамильтоновости (deg[k] <= k < n / 2) => (deg[n-k] >= n - k)
  6. Турниры - алгоритм поиска Гамильтонова пути за O(N2)
  7. Турниры - алгоритм поиска Гамильтонова цикла за O(N3)
  8. Турниры - алгоритм поиска Гамильтонова цикла за O(N2)