Эйлеров цикл

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь)

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

Эйлеров граф — граф, содержащий эйлеров цикл.

Полуэйлеров граф — граф, содержащий эйлеров путь.

Существование эйлерова цикла и эйлерова пути

В неориентированном графе

Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.

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

В ориентированном графе

Ориентированный граф <math>G=(V,A)</math> содержит эйлеров цикл тогда и только тогда, когда он сильно связан и для каждой вершины графа её полустепень захода <math>\mathrm{indeg}(\cdot)</math> равна её полустепени исхода <math>\mathrm{outdeg}(\cdot)</math>, то есть в вершину входит столько же ребер, сколько из неё и выходит: <math>\mathrm{indeg}(v)=\mathrm{outdeg}(v)\quad \forall v\in V</math>.

Так эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф <math>G=(V,A)</math> содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющейся циклом. Ориентированный граф <math>G=(V,A)</math> содержит эйлеров путь, не являющейся циклом, тогда и только тогда, когда существуют две вершины <math>p\in V</math> и <math>q\in V</math> (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами <math>\mathrm{indeg}(q)=\mathrm{outdeg}(q)+1</math> и <math>\mathrm{indeg}(p)=\mathrm{outdeg}(p)-1</math>, а все остальные вершины имеют одинаковые полустепени исхода и захода: <math>\mathrm{outdeg}(v)=\mathrm{indeg}(v)\quad \forall v\in V\setminus\{p,q\}</math>.

Поиск эйлерова пути в графе

Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществующее ребро.

Поиск эйлерова цикла в графе

Алгоритм Флёри

Это хоть и элегантный, но неэффективный алгоритм, который был предложен Флёри в 1883 году.

Пусть задан граф <math>G=(V,E)</math>. Начинаем с некоторой вершины <math>p\in V</math> и каждый раз вычеркиваем пройденное ребро. Не проходим по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин), т.е. необходимо проверять, является ли ребро мостом или нет.

Алгоритм может быть распространен на ориентированные графы.

Алгоритм на основе циклов

Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.

Реализовать это можно, например, так, рекурсивно:

procedure find_all_cycles (v)
var массив cycles
1. пока есть цикл, проходящий через v, находим его
    добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода)
    удаляем цикл из графа
2. идем по элементам массива cycles
    каждый элемент cycles[i] добавляем к ответу
    из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i])

Достаточно вызвать эту процедуру из любой вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл.

Для поиска цикла на шаге 1 используем поиск в глубину.

Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.

См. также

• Гамильтонов цикл
• Граф (математика)
• Задача о ходе коня
• Дискретная математика
• Проблема семи мостов Кёнигсберга
• Список объектов, названных в честь Леонарда Эйлера

Ссылки

• [e-maxx.ru/algo/euler_path Реализация алгоритма поиска эйлерова цикла (краткие описания и программы на C++)]
• [sources.codenet.ru/download/936/graph3.html Реализация алгоритма поиска эйлерова цикла на codenet.ru]
• [belsky.narod.ru/v2/download/mathemat/courses/tgik/ Теория графов и комбинаторика]
• [rain.ifmo.ru/cat/view.php/vis/graph-circuits-cuts Графы. Циклы и разрезы (ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ, Визуализаторы)]
• Е. Гик. [golovolomka.hobby.ru/books/gik/index.shtml «Шахматы и математика»] [golovolomka.hobby.ru/books/gik/02.shtml Конь-хамелеон]
• Weisstein, Eric W. [mathworld.wolfram.com/EulerianCircuit.html Eulerian Circuit] (англ.) на сайте Wolfram MathWorld.

Отрывок, характеризующий Эйлеров цикл

Некоторые из генералов негромким голосом, совсем в другом диапазоне, чем когда они говорили на совете, передали кое что главнокомандующему.
Малаша, которую уже давно ждали ужинать, осторожно спустилась задом с полатей, цепляясь босыми ножонками за уступы печки, и, замешавшись между ног генералов, шмыгнула в дверь.
Отпустив генералов, Кутузов долго сидел, облокотившись на стол, и думал все о том же страшном вопросе: «Когда же, когда же наконец решилось то, что оставлена Москва? Когда было сделано то, что решило вопрос, и кто виноват в этом?»
– Этого, этого я не ждал, – сказал он вошедшему к нему, уже поздно ночью, адъютанту Шнейдеру, – этого я не ждал! Этого я не думал!
– Вам надо отдохнуть, ваша светлость, – сказал Шнейдер.
– Да нет же! Будут же они лошадиное мясо жрать, как турки, – не отвечая, прокричал Кутузов, ударяя пухлым кулаком по столу, – будут и они, только бы…


В противоположность Кутузову, в то же время, в событии еще более важнейшем, чем отступление армии без боя, в оставлении Москвы и сожжении ее, Растопчин, представляющийся нам руководителем этого события, действовал совершенно иначе.
Событие это – оставление Москвы и сожжение ее – было так же неизбежно, как и отступление войск без боя за Москву после Бородинского сражения.
Каждый русский человек, не на основании умозаключений, а на основании того чувства, которое лежит в нас и лежало в наших отцах, мог бы предсказать то, что совершилось.
Начиная от Смоленска, во всех городах и деревнях русской земли, без участия графа Растопчина и его афиш, происходило то же самое, что произошло в Москве. Народ с беспечностью ждал неприятеля, не бунтовал, не волновался, никого не раздирал на куски, а спокойно ждал своей судьбы, чувствуя в себе силы в самую трудную минуту найти то, что должно было сделать. И как только неприятель подходил, богатейшие элементы населения уходили, оставляя свое имущество; беднейшие оставались и зажигали и истребляли то, что осталось.
Сознание того, что это так будет, и всегда так будет, лежало и лежит в душе русского человека. И сознание это и, более того, предчувствие того, что Москва будет взята, лежало в русском московском обществе 12 го года. Те, которые стали выезжать из Москвы еще в июле и начале августа, показали, что они ждали этого. Те, которые выезжали с тем, что они могли захватить, оставляя дома и половину имущества, действовали так вследствие того скрытого (latent) патриотизма, который выражается не фразами, не убийством детей для спасения отечества и т. п. неестественными действиями, а который выражается незаметно, просто, органически и потому производит всегда самые сильные результаты.
«Стыдно бежать от опасности; только трусы бегут из Москвы», – говорили им. Растопчин в своих афишках внушал им, что уезжать из Москвы было позорно. Им совестно было получать наименование трусов, совестно было ехать, но они все таки ехали, зная, что так надо было. Зачем они ехали? Нельзя предположить, чтобы Растопчин напугал их ужасами, которые производил Наполеон в покоренных землях. Уезжали, и первые уехали богатые, образованные люди, знавшие очень хорошо, что Вена и Берлин остались целы и что там, во время занятия их Наполеоном, жители весело проводили время с обворожительными французами, которых так любили тогда русские мужчины и в особенности дамы.
Они ехали потому, что для русских людей не могло быть вопроса: хорошо ли или дурно будет под управлением французов в Москве. Под управлением французов нельзя было быть: это было хуже всего. Они уезжали и до Бородинского сражения, и еще быстрее после Бородинского сражения, невзирая на воззвания к защите, несмотря на заявления главнокомандующего Москвы о намерении его поднять Иверскую и идти драться, и на воздушные шары, которые должны были погубить французов, и несмотря на весь тот вздор, о котором нисал Растопчин в своих афишах. Они знали, что войско должно драться, и что ежели оно не может, то с барышнями и дворовыми людьми нельзя идти на Три Горы воевать с Наполеоном, а что надо уезжать, как ни жалко оставлять на погибель свое имущество. Они уезжали и не думали о величественном значении этой громадной, богатой столицы, оставленной жителями и, очевидно, сожженной (большой покинутый деревянный город необходимо должен был сгореть); они уезжали каждый для себя, а вместе с тем только вследствие того, что они уехали, и совершилось то величественное событие, которое навсегда останется лучшей славой русского народа. Та барыня, которая еще в июне месяце с своими арапами и шутихами поднималась из Москвы в саратовскую деревню, с смутным сознанием того, что она Бонапарту не слуга, и со страхом, чтобы ее не остановили по приказанию графа Растопчина, делала просто и истинно то великое дело, которое спасло Россию. Граф же Растопчин, который то стыдил тех, которые уезжали, то вывозил присутственные места, то выдавал никуда не годное оружие пьяному сброду, то поднимал образа, то запрещал Августину вывозить мощи и иконы, то захватывал все частные подводы, бывшие в Москве, то на ста тридцати шести подводах увозил делаемый Леппихом воздушный шар, то намекал на то, что он сожжет Москву, то рассказывал, как он сжег свой дом и написал прокламацию французам, где торжественно упрекал их, что они разорили его детский приют; то принимал славу сожжения Москвы, то отрекался от нее, то приказывал народу ловить всех шпионов и приводить к нему, то упрекал за это народ, то высылал всех французов из Москвы, то оставлял в городе г жу Обер Шальме, составлявшую центр всего французского московского населения, а без особой вины приказывал схватить и увезти в ссылку старого почтенного почт директора Ключарева; то сбирал народ на Три Горы, чтобы драться с французами, то, чтобы отделаться от этого народа, отдавал ему на убийство человека и сам уезжал в задние ворота; то говорил, что он не переживет несчастия Москвы, то писал в альбомы по французски стихи о своем участии в этом деле, – этот человек не понимал значения совершающегося события, а хотел только что то сделать сам, удивить кого то, что то совершить патриотически геройское и, как мальчик, резвился над величавым и неизбежным событием оставления и сожжения Москвы и старался своей маленькой рукой то поощрять, то задерживать течение громадного, уносившего его вместе с собой, народного потока.