Чего Точная оценка Почему
Время O(n²) Поиск вершины, удовлетворяющей заданному условию работает за O(n), а таких поисков будет осуществлено не более чем n. Оставшиеся n(n−2) итерации выполняются за O(1). Тогда алгоритм выполняется за O(n²).
Память O(V) Очередь

Что делает: ищет цикл без повторяющихся вершин и ребер, проходящий через каждую вершину графа

Общая идея:

  1. Проверить на то, Гамильтонов ли граф
  2. Завести очередь, и в конечном итоге получить последовательность вершин, смежных между собой. Если при этом первая вершина в очереди будет смежна с последней, то Гамильтонов цикл будет найден

Теория (НЕ ПРОПУСКАТЬ А ТО УЕБУ):

Гамильтонов путь - простой путь, проходящий через каждую вершину графа ровно один раз

Гамильтонов цикл - замкнутый Гамильтонов путь (∃ путь из V.first в V.last в гамильтоновом пути)

Гамильтонов граф - граф, содержащий Гамильтонов цикл

‼ Перед тем, как искать Гамильтонов цикл, необходимо проверить, что граф - Гамильтонов. Для этого существуют теоремы Оре, Дирака или Гуйя-Уре:

Теорема Оре:

Если число вершин больше трёх и для любых несмежных вершин сумма степеней будет не менее числа вершин в графе, то этот граф - Гамильтонов

(|V| > 3) И (для любых несмежных Vi сумма степеней ≥ |V|)

Доказательство

Теорема Дирака:

Если в неориентированном графе минимальная степень вершины равна не менее половины от общего числа вершин, то этот граф - Гамильтонов

степень любой вершины ≥ $n/2$

Доказательство

Теорема Гуйя-Уре (ориентированный вариант Дирака):

Если G - сильносвязный ориентированный граф, то:

степень входа для любой вершины ≥ $n/2$

степень выхода для любой вершины ≥ $n/2$

Реализация: