5. Эйлеровы циклы и задача китайского почтальона

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

Очевидно, не все графы имеют эйлеровы циклы (см., например, граф на рис. 9.8), но если эйлеров цикл существует, то это

Рис. 9.8. Граф без эйлерова цикла.

Рис. 9.9.

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

Направление движения по каждому ребру показано на рисунке стрелками.

Эйлер первым в своей знаменитой задаче о Кёнигсбергских мостах рассмотрел вопрос о существовании таких циклов в графах.

Рис. 9.10. (а) Карта Кёнигсберга, (б) Эквивалентный граф.

Кёнигсберг (теперь Калининград) расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами как показано на карте на рис. 9.10 (а).

Вопрос — поставленный в 1736 году — состоит в том, можно ли, начав с некоторой точки, совершить прогулку и вернуться

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

Основная теорема о существовании эйлеровых циклов формулируется так.

Теорема Связный неориентированный -граф содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно (0 или 2).

Доказательство. Мы докажем эту теорему для случая цикла; случай цепи рассматривается аналогично.

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

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

Начиная теперь с получаем цикл начинающийся и оканчивающийся в Если все оставшиеся ранее ребра использованы для цикла то процесс окончен. Нужный эйлеров цикл будет образован частью цикла от вершины до затем циклом и, наконец, частью цикла от вершины до Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов дает новый цикл Мы снова можем найти вершину принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла начинающегося в и так продолжать до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Это доказывает теорему.

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

Если ориентированный -граф, то справедлива теорема, полностью аналогичная предыдущей, а именно

Теорема Связный ориентированный -граф содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда все полустепени захода и полустепени исхода вершин удовлетворяют условиям:

где начальная, конечная вершины эйлеровой цепи.

Флёри [16] дал очень простой алгоритм построения эйлерова цикла в неориентированном графе (если такой цикл существует). Этот алгоритм легко может быть распространен на ориентированные графы (см. также задачи 7 и 8) и состоит в следующем. Алгоритм нахождения эйлерова цикла. Начинать с некоторой вершины и каждый раз вычеркивать пройденное ребро. Не проходить по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин).