Поиск в глубину и применения (12 декабря 2017)

  1. [20 минут] Компоненты сильной связности
    1. Алгоритм поиска за O(V+E) двумя dfs (topsort + красим по обратным рёбрам)
    2. Доказательство корректности
    3. Применение: конденсация матрица достижимости за O(VE)

  2. [20 минут] Эйлеровость
    1. Критерий эйлеровости для ор и неор
    2. Доказательство и элементарный алгоритм поиска пути:
      выделим цикл жадным циклом for (идём вглубь до упора), по индукции сделаем из каждой компоненты оставшихся рёбер Эйлеровы цикл, склеим.
    3. Алгоритм поиска для орграфа за O(V+E) одним dfs (result.push_back(e); на выходе из dfs)
    4. Картинку с примером
    5. Алгоритм поиска для неорграфа отличается тем, что после прохода по ребру нужно удалить парное пройденному.
      Удаляем лениво: Edge.rev->deleted = true;
− Перерыв −
  1. [30 минут] Двусвязность
    1. Определения: рёберная, вершинная, мосты, точки сочленения
    2. Наивный алгоритм поиска всех мостов и точек сочленения за O(VE)
    3. Поиск компонент по данным мостам, точкам сочленения.
    4. Алгоритм поиск мостов = 1 dfs.
    5. Учим этот dfs искать компоненты (доставать их из стека).
    6. Таким же образом ищем точки сочленения
    7. Таким же образом ищем компоненты вершинной двусвязности (стек рёбер, что делать с парным ребром)
    8. Корректность всех алгоритмов (на самом деле алгоритм един, его конечная версия ищет всё и сразу)
    9. Условия: (mt[x] ≥ t[v]) ⇔ is_bridge (new_component), (mt[x] ≥ t[v]) ⇔ is_point (new_component)

  2. [15 минут] 2-SAT
    1. Определение. Переформулировка через импликации, сведение в обе стороны.
    2. Решаем в форме импликаций, граф из 2n вершин. Видим критерий неразрешимости в компонентах сильной связности.
    3. Решение за O(V+E): рассматриваем компоненты снизу вверх.
    4. Корректность: x=e ⇒ не появится противоречий