Существует много теорем, которые гарантируют наличие у графа гамильтонова цикла. При этом должно работать условие, что у графа есть определенные свойства. Одним из самых простых является условие Дирака, с котором мы познакомимся в этом уроке.
Как найти гамильтонов цикл с условием Дирака
Докажем наличие гамильтонова цикла в графе через теорему с условием Дирака. Допустим, если в простом графе с вершинами у каждой вершины степень не менее , то у графа есть гамильтонов цикл.
Используем доказательство существования — пока каждая вершина смежна хотя бы с половиной вершин, у этого графа есть гамильтонов цикл. Этот способ показывает, что гамильтонов цикл существует, но не показывает, как его найти.
Найдем в графе путь максимальной длины. Пусть его вершины называются , . Мы покажем, что можно превратить в цикл .
Если и смежные, то очевидно, что у нас есть цикл. В противном случае мы найдем цикл, показав, что на пути есть две смежные вершины, и . При этом смежна с , а смежна с . Тогда мы получим цикл , :
У конечных точек и не может быть соседей, которые не лежат на . В противном случае мы могли бы продлить путь до более длинного. Поэтому — смежная с вершинами от до .
Нам нужно, чтобы была смежной с вершиной на пути, которая предшествует одной из этих вершин. Если бы это было не так, то на пути было бы вершин, к которым не примыкает. Но это невозможно, так как у есть соседей, и все они должны лежать на пути.
Еще нам нужно показать, что только что найденный цикл C точно содержит все вершины графа. Предположим, что есть еще какая-то вершина , которая не лежит в . Поскольку смежна с вершинами, все из которых лежат в , более половины вершин графа лежат в .
Так как , должна быть смежной с какой-то вершиной из . Но тогда мы могли бы создать более длинный путь, чем . Для этого мы бы начали с вершины, которая следует сразу за в цикле , прошли назад до , а затем в обход до . Это невозможно, поэтому каждая вершина графа должна лежать на , что делает гамильтоновым циклом.
из теоремы не может быть уменьшено еще больше. Например, в приведенном ниже графе каждая вершина имеет степень не менее , но гамильтонова цикла не существует из-за разрезанной вершины:
Выводы
В этом уроке мы разобрали теорему с условием Дикара, которая гарантирует наличие у графа гамильтонова цикла. Условие, что каждая вершина должна быть смежной по крайней мере с вершинами, гарантирует, что каждая вершина имеет довольно высокую степень. Это дает графу много ребер и нам большую свободу в попытках создать гамильтонов цикл.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
