Теория: Графы

  1. Определения
    1. Граф, орграф, неорграф, путь, кратные ребра, петли [ru-wiki]
    2. Обозначения O, o, Θ [ru-wiki]
    3. Асимптотика алгоритмов: на примере сортировок и бинпоиска
  2. Хранение графа
    1. Матрица смежности [ru-wiki]
    2. Список смежных вершин для каждой вершины
  3. dfs = поиск в глубину [e-maxx]
    1. Компоненты связности за O(E)
    2. Поиск цикла в неорграфе за O(V)
    3. Поиск цикла в орграфе за O(E) [e-maxx]
    4. Топологическая сортировка графа за O(E) [e-maxx]
  4. bfs = поиск в ширину, кратчайший путь [e-maxx]
    1. Дерево кратчайших путей, восстановление пути.
    2. Поиск от A до v. Поиск от v до A.
    3. Пример с поиском по матрице. Оптимизация памяти за счет циклической очереди.
      Реализация циклической очереди на массиве.
  5. Модификации bfs-а
    1. 0-1 за O(E)
    2. 1-k за O(kE) (нужно разкатерить ребра)
    3. 1-k за O(E + kV) (много очередей)
  6. Дейкстра = поиск кратчайшего пути в графе без отрицательных ребер
    1. Реализация в лоб за O(V2) [e-maxx]
    2. Куча дает O(ElogV) [e-maxx]
    3. Фибоначева куча дает O(E + VLogV)
  7. ford-bellman = поиск кратчайшего пути в графе без отрицательных циклов [e-maxx]
    1. Реализация за O(VE). С док-вом.
    2. Реализация за O(kE).
    3. Реализация bfs-ом с циклической очередью. [wiki]
  8. Динамика на ацикличном графе (ДП)
    1. число путей
    2. мин путь
    3. макс путь
  9. Ацикличный граф кратчайших путей
    1. Построение графа: d[ae] + we = d[be]
    2. Если we > 0, можно посчитать число кратчайших путей (ДП на ацикличном графе)
    3. Д.З. Если we <= 0, то? (в полученном графе могут быть циклы) [на самом деле, очень простой вопрос]
  10. Флойд = поиск всех кратчайших путей в графе без отрицательных циклов [e-maxx]
  11. Алгоритм Прима = минимальный остов (почти Дейкстра, только остов). [e-maxx]
  12. Алгоритм Краскала = минимальный остов с СНМ (без объяснения, что такое СНМ). [e-maxx]
  13. Модификации dfs-а
    1. Сильная связность [e-maxx]
    2. Not read Ориентация графа
    3. Мосты [e-maxx]
    4. Not read Точки сочленения [e-maxx]
    5. Not read 2-связность (реберная и вершинная)
    6. Конденсация графа (любые классы, сильная связность, 2-связность)
  14. Not read Эйлеров путь и цикл [e-maxx]
  15. Not read Гамильтоновы путь и цикл
    1. Not read 2n n2 [src]
    2. Not read перебор
    3. Not read эвристика конем
    4. Not read эвристика связности
  16. Not read Циклы
    1. Not read Минимальной длины, граф не взвешенный (в неорграфе, в орграфе).
    2. Not read Минимальной длины, граф взвешенный
    3. Not read Отрицательный с помощью FB [e-maxx]
    4. Not read Отрицательный с помощью Floyd [e-maxx]
    5. Not read Цикл минимального среднего веса за O(VElog) (с бинпоиском)
    6. Not read Цикл минимального среднего веса за O(VE)

Задачи

  1. Найти путь из A в B : max вес ребра в пути минимален
  2. Not read Для каждой пары вершина A и B сделать (1)
  3. Найти в графе цикл длины три
  4. Найти кратчайший путь четной длины
  5. Найти самый длинный (не обязательно простой) путь в графе
  6. Not read Дополнить граф до связного
  7. Not read Дополнить граф до сильносвязного
  8. Not read Найти диаметр графа (2 самые удаленные вершины)
  9. Not read Найти диаметр дерева
  10. Not read Проверить, является ли граф деревом
  11. Not read Разбить кактус на циклы
  12. Not read Число способов пройти по шахматной доске конем из (1,1) в (N,N).
  13. Not read Маша и грибы (Маша ходит по матрице и собирает грибы, ходить можно только вниз и вправо, нельзя врезаться в деревья).
  14. Not read Найти расстояние от множества A до множества B в невзвешенном графе.
  15. Not read Найти расстояние от множества A до множества B во взвешенном графе.