Гамильтоновы графы. Метод Робертса – Флореса

Простая цепь называется гамильтоновой.

Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа.

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

Теорема Дирака (достаточное условие гамильтоновости графа)

Если граф является связным и степень каждой вершины удовлетворяет неравенству

где - ближайшее целое число, то граф является гамильтоновым.

В орграфе рассматривают гамильтонов путь и гамильтонов контур.

Рассмотрим задачу построения гамильтонового контура в заданном графе.