Гамильтонов цикл — Теория графов

Гамильтонов цикл в графе — это подграф и цикл, который включает в себя все вершины графа. Граф, в котором есть гамильтонов цикл, называется гамильтоновым. Гамильтонов путь — это подграф-путь, который все вершины графа:

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

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

Если граф содержит срезанную вершину или срезанное ребро, то у него нет гамильтонова цикла. Когда срезанные вершины или ребра пересекаются, пропадает возможность вернуться, чтобы завершить цикл. Например:

На графике видно, что нет способа вернуться на другую сторону графа, когда мы пересекаем вершину или ребро .

Рассмотрим следующую теорему:

Например, мы можем попытаться удалить одну вершину, которая разбивает граф на два или более компонентов. Это будет вершина разреза. Или мы можем попытаться удалить две вершины, чтобы разбить граф на три или более компонентов. И так дальше по возрастанию.

Например, возьмем . Три компоненты графа показаны справа:

Число компонентов больше, чем , поэтому гамильтонова цикла не существует. и действуют как узкое место. Каждый раз, когда мы хотим покинуть одну из компонент , мы должны использовать либо , либо . Таким образом, мы расходуем и и не можем завершить наше круговое путешествие.

Эта теорема дает необходимое, но не достаточное условие для гамильтонова цикла. Существует множество графов, которые удовлетворяют этому условию, но не имеют гамильтоновых циклов. Одним из таких примеров является граф Петерсена.

Существует противоположная теорема:

Такую теорему доказать немного проще. Основная идея состоит в том, что когда мы проходим через гамильтонов цикл в и достигаем компоненты , единственный способ достичь других вершин, не входящих в эту компоненту — это вернуться через . Получается, у должно быть столько же вершин, сколько и компонент :

Другой пример приведен ниже. Четыре вершины удалены, и полученный граф имеет пять компонент, поэтому в нем нет гамильтонова цикла:

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