Поиск в глубину (5 ноября 2015, Глеб)

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