5.3 Эйлеровы и гамильтоновы графы

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

Теорема. Для того, чтобы связный псевдограф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными.

Теорема. Для того, чтобы связный псевдограф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.

Определение. Цикл (цепь) в псевдографе G называется гамильтоновым, если он проходит через каждую вершину псевдографа G ровно один раз.

а) Гамильтонов путь в графе

б) Граф, в котором не существует гамильтонова пути

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

Также необходимым условием существования гамильтонова цикла явояется связность графа.