Гамильтонов граф

---

Гамильтонов граф — граф, содержащий гамильтонов цикл^[1]. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу^[2]; то есть простой цикл, в который входят все вершины графа.

Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз^[1]. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз^[3]. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра^[4].

Необходимое условие существования гамильтонова цикла в неориентированном графе: если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины ${\displaystyle x(i)}$ с локальной степенью ${\displaystyle p(x(i))<2}$. Доказательство следует из определения.

Условие Поша: Пусть граф G имеет ${\displaystyle p>2}$ вершин. Если для всякого ${\displaystyle n}$, ${\displaystyle 0<n<(p-1)/2}$, число вершин со степенями меньшими или равными n меньше, чем n, и для нечетного ${\displaystyle p}$ число вершин со степенью ${\displaystyle (p-1)/2}$ не превосходит ${\displaystyle (p-1)/2}$, то G — гамильтонов граф. Это достаточное условие не является необходимым^[6].

Как следствие теоремы Поша, получаем более простые и менее сильные достаточные условия, найденные Дираком и Оре.

---