Поиск в глубину (4 ноября 2015, Лёша)

  1. [30 минут] Кодим dfs
    1. Выделение мостов и компонент реберной двусвязности [code]
    2. Что нужно поменять в коде, чтобы получилась вершинная двусвязность и точки сочленения?
    3. Эйлеров цикл (в ориентированном графе, комментарий к неориентированному графу) [code]

  2. [10 минут] Эйлеровость
    1. Если Паша не все критерии Эйлеровости рассказал на паре
    2. Неорграф, цикл (связность, чётность)
    3. Неорграф, путь
    4. Орграф, цикл (связность, in=out)
    5. Орграф, путь

  3. [50 минут] Задачи на dfs
    1. Найти путь из множества вершин A в множество вершин B (из любой вершины a ∈ A в любую b ∈ B)
    2. Найти все вершины неориентированного графа, которые обязательно будут лежать на пути от a до b. O(V+E).
    3. Разбить все рёбра слабосвязного орграфа на минимальное число путей (слабосвязность: неор версия графа связна)
    4. Дополнение графа до Эйлерова (минимизировать число рёбер)
    5. Разбить множество вершин на две доли (V = A ⊔ B) так, чтобы у каждой вершины был сосед в другой доли. O(V+E)
    6. 2-List-Coloring через 3-SAT. Каждой вершине неорграфа сопоставлены два возможных цвета. Покрасить вершины так, чтобы соседние вершины были покрашены в различные цвета.
    7. 3-List-Coloring: решения за 2nm (перебрали вершины цвета 3), 1.5nm (случайным образом заблокировали 1 из 3 цветов у каждой вершины)

  4. Дополнительные задачи
    1. Дополнение графа до Эйлерова (минимизировать суммарный вес рёбер)
    2. Дополнение графа до сильносвязного.