Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

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

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

Что такое гамильтонов цикл

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

eyJpZCI6IjBhYjQ0MTEyMDJkZTBhMTQ4OGIyZmMzZWRmZWY5N2Q5LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=b5b132bb7177cf5b8d3a4d50e09e58786ed02381605b9f73c86cee11704ca3da

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

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

Как понять, что у графа нет цикла

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

eyJpZCI6ImQzYzgxMWUxNzYzOGJkZWRlZTcwMjg2MWZmMzE5MzEwLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=651192b36643628c769f32bc3d7aec0f1f32bdc87f13a47178b8380835b62c5d

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

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

Если существует некоторое подмножество вершин такое, что у больше компонент, чем у вершин, то у нет гамильтонова цикла

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

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

eyJpZCI6Ijk2Y2NiNTcxZDEyZGEzZmY1ODFiNTg5OTVjMGY5MzQ5LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=9191352575e45b1ede63dd6132d29780ac1924763f8b72c6d74c27037e7d9673

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

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

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

Если у есть гамильтонов цикл, то для каждого подмножества вершин число компонент больше или равно

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

eyJpZCI6Ijg2ODFkZmRkZmU5N2RjY2UzMjQ5MGM2ODYxOWZhNmRlLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=4735a748f60bec15d42993b66267def7f108fe18dde7e7f6df626dec7b710ba4

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

eyJpZCI6ImM5YmE5MTUzOWE3MzIyZjM4Y2ZhM2IzMzJjMTk4NDcxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=27ccd397bd2642e7f6c45845c3e5292c8a4a930b5375b6c587a606e87231f63b

Выводы

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


Самостоятельная работа

Задача №1

Какие графы на рисунке ниже считаются гамильтоновыми графами?

eyJpZCI6IjQ4NGMxYTFlMzM0YThmMWYwYWEyNmVkYTRiZWJjNTAzLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=4785f229f970f009f4601188879a5fca6ffb425c0bf80e7ae15aa668d6d7222e
Нажмите, чтобы увидеть ответ

Графы и не содержfт ни гамильтонова пути, ни гамильтоновой цепи. Cледовательно, они не считаются гамильтоновыми графами.

Остальные графы считаются гамильтоновыми. Рассмотрим их подробнее:

  • Граф содержит гамильтонов путь и гамильтонов контур

  • Граф содержит гамильтонов путь и гамильтонов контур

  • Граф содержит гамильтонов путь и гамильтонов контур


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

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