Эйлеровы графы.

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

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

Рисунок 3

а) б)

Задача, которая привела к появлению понятия Эйлерова цикла, широко известна в истории математики. Это так называемая задача о кенигсбергских мостах. Расположение семи мостов в городе Кенигсберге в начале XVIII века приведено на рисунке 3а. Требуется обойти город, пройдя через каждый мост ровно один раз, и вернуться в исходную точку.

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

Именно решение данной задачи привело Л. Эйлера к доказательству приведённой выше теоремы. Кстати, согласно ей, данная задача неразрешима, поскольку степени всех вершин графа нечётны.

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

По сути дела, теоремы 15.1 и 15.2 описывают условия, при которых можно построить геометрическую фигуру “не отрывая карандаша от бумаги”, одной сплошной линией. Только в первом случае начало и конец этой линии будут совпадать, а во втором случае они будут различны.

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

Пример 1.

а)

- в графе есть и Эйлеров и Гамильтонов циклы

б)

- в графе есть Эйлеров цикл, но нет Гамильтонова

в)

- в графе есть гамильтонов, но нет Эйлерова цикла

г)

- в графе нет ни Эйлерова, ни Гамильтонова цикла

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

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