Теорема Эйлера

Рассмотрим задачу о кенигсбергских мостах, сформулированную Эйлером. Река Прегель делит г. Кенигсберг на четыре части: A, B, C, D, соединенные между собой семью мостами (рис. 3.1.5).

Рис. 5

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

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

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

Граф, соответствующей задаче Эйлера о кенигсбергских мостах, не удовлетворяет теореме 1. Он не содержит эйлерова цикла.

Теорема 2. Неориентированный граф содержит эйлерову цепь, соединяющую вершины А и В в том и только в том случае, если граф связен, и только эти вершины А и В являются вершинами с нечетными степенями, а степени всех остальных вершин четны.

Алгоритм построения эйлерова цикла состоит в следующем:

1. Выходим из произвольной вершины X₀, каждое пройденное ребро зачерчиваем.

2. Никогда не идем по такому ребру, которое в рассматриваемый момент является перешейком, а также не выбираем ребра, идущего в X₀, пока есть другие возможности.

Задача об определении гамильтоновых линий в общем виде не решена. Для каждого графа она решается отдельно. Получены некоторые необходимые, некоторые достаточные условия существования гамильтоновых графов, т.е. графов, содержащих гамильтонов цикл. К полученным результатам относится теорема Кенига: в полном графе (т.е. в графе, любая пара вершин которого соединена хотя бы в одном направлении) всегда существует гамильтонов путь.

К числу задач, требующих определения гамильтонова цикла, относится задача о коммивояжере. Бродячий торговец, предлагая товар, посещает ряд городов, причем каждый город он посещает единственный раз, после чего вновь возвращается в исходный пункт. Требуется определить кратчайший путь коммивояжера, если расстояния между городами заданы. Города можно представить как вершины связного неориентированного графа, в котором каждый паре вершин x_ix_j приписывается расстояние l(x_i, x_j). Эта задача имеет ряд важных приложений в экономике, к ней, в частности, сводится задача о наиболее эффектном использовании подвижного состава оборудования. Решается задача методами динамического программирования.