Гамильтонов цикл

Гамильто́нов цикл в графе, простой цикл, содержащий все вершины графа. Простым называется цикл, в последовательности вершин которого все вершины встречаются ровно один раз. Граф, имеющий гамильтонов цикл, называется гамильтоновым. Гамильтонов граф двусвязен. Одно из достаточных условий существования гамильтонова цикла состоит в том, что если в графе ${\displaystyle G}$ с ${\displaystyle p}$ вершинами ${\displaystyle p\geqslant 3}$, для любого ${\displaystyle n}$, ${\displaystyle 1\leqslant n\leqslant (p-1)/2}$, число вершин со степенями, не превосходящими ${\displaystyle n}$, меньше ${\displaystyle n}$ и, при нечётном ${\displaystyle p}$, число вершин степени ${\displaystyle (p-1)/2}$ не превосходит ${\displaystyle (p-1)/2}$, то граф ${\displaystyle G}$ имеет гамильтонов цикл. Задача нахождения эффективного описания гамильтоновых графов остаётся актуальной.

Гамильтоновы циклы получили своё название в связи с тем, что первая задача о таких циклах была предложена У. Р. Гамильтоном (1859): это была задача-головоломка о кругосветном путешествии, состоящая в том, чтобы найти замкнутый путь, идущий по рёбрам додекаэдра (изображающего Землю) и проходящий через каждую из его двадцати вершин (городов) ровно один раз.

Цикл, содержащий по одному разу все рёбра графа, называется эйлеровым. Первая публикация по теории графов появилась (1736) в связи с решением Л. Эйлером задачи о кёнигсбергских мостах, состоящей в доказательстве отсутствия такого цикла в графе, описывающем расположение этих мостов. Граф, имеющий эйлеров цикл, называется эйлеровым.

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