Алгоритмы на графах

План (предварительно):

  • Поиск кратчайших путей
  • Проверка транзитивности графа
  • Отыскание сильно связных компонент
  • Алгоритм поиска Эйлерова цикла
  • Поиск циклов заданной длины
  • Топологическая сортировка
  • Минимальное остовное дерево (каркас)
    • Алгоритм Краскала
    • Алгоритм Прима
  • Определение двудольности графа
  • Поиск максимального паросочетания в двудольном графе
  • Отыскание точек сочленения
  • Построение конденсации графа (графа компонент)
  • Максимальный поток
    • Алгоритм Форда-Фалкерсона
    • Алгоритм Эдмондса-Карпа
    • Алгоритм Голдберга-Тарьяна
    • Алгоритм Слейтора-Тарьяна
    • Алгоритм Малхотри-Кумара-Махешвари
    • Алгоритм Диница
  • NP-сложные задачи
    • Покраска графа
    • Отыскание максимального независимого множества вершин
    • Отыскание максимальной клики
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License