Основные определения. Маршрутом (или путем ) в графе G называется чередующаяся последовательность вершин и ребер v 0, e 1

Напомним основные определения из теории графов. Пусть V непустое конечное множество. Через V ⁽²⁾ обозначим множество всех двухэлементных подмножеств из V. Графом G называется пара множеств (V, E), где E — произвольное подмножество из V ⁽²⁾. Элементы множеств V и E называют соответственно вершинами и ребрами графа G. Граф G (V, E) называется полным, если любая пара его вершин соединена, хотя бы в одном направлении.

Маршрутом (или путем) в графе G называется чередующаяся последовательность вершин и ребер v ₀, e ₁, v ₁, …, v_{t −1}, e_t, v_{t +1}, в которой e_i = v_{i −1} v_i (1 ≤ i ≤ t). Такой маршрут кратко называют (v ₀, v_t)-маршрутом и говорят, что он соединяет v ₀ c v_t; в свою очередь вершины v ₀, v_t — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v ₀, v ₁, …, v _t своих вершин. Если v ₀= v_t, то (v ₀, v_t)-маршрут называется замкнутым.

Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, быть может, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром).

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

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

Замечание.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v₁,…,v_p графа G добавить вершины u₁,…,u_p и множество ребер {(v_i,u_i)} {(u_i,v_i+1)}.

Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень d_o(v) по выходящим дугам и d_i(v) — по входящим.