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

ГАМИЛЬТОНОВ ЦИКЛ в графе, простой цикл, содержащий все вершины графа. Простым называется цикл, в последовательности вершин которого все вершины встречаются ровно один раз (смотри Графов теория). Граф, имеющий Гамильтонов цикл, называется гамильтоновым. Гамильтонов граф двусвязен. Одно из достаточных условий существования Гамильтонова цикла состоит в том, что если в графе G с р вершинами р≥3, для любого n, 1≤ n ≤ (р-1)/2, число вершин со степенями, не превосходящими n, меньше n и, при нечётном р, число вершин степени (р-1)/2 не превосходит (р-1)/2, то граф G имеет Гамильтонов цикл. Задача нахождения эффективного описания гамильтоновых графов остаётся актуальной.

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

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

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

Лит.: Euler L. The Кönigsberg bridges // Scientific American. 1953. Vol. 189. № 1; Харари Ф., Палмер Э. Перечисление графов. М., 1977.