Эйлеров путь - Eulerian path

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

Каждая вершина этого графа имеет четную степень. Следовательно, это эйлеров граф. Отслеживание ребер в алфавитном порядке дает эйлеров контур / цикл.

В теория графов, Эйлерова тропа (или же Эйлеров путь) это тащить в конечном графе, который посещает каждый край ровно один раз (с учетом пересмотра вершин). Точно так же Контур Эйлера или же Эйлеров цикл эйлерова тропа, которая начинается и заканчивается на одном вершина. Впервые их обсудили Леонард Эйлер решая знаменитый Семь мостов Кенигсберга Задача 1736 года. Математически задачу можно сформулировать так:

Учитывая график на изображении, можно ли построить путь (или цикл; т.е. путь, начинающийся и заканчивающийся в одной вершине), который посещает каждое ребро ровно один раз?

Эйлер доказал, что необходимым условием существования эйлеровых схем является то, что все вершины графа имеют четные степень, и заявил без доказательства, что связные графы со всеми вершинами четной степени имеют эйлеров контур. Первое полное доказательство этого последнего утверждения было опубликовано посмертно в 1873 г. Карл Хирхольцер.^[1] Это известно как Теорема Эйлера:

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

Период, термин Граф Эйлера имеет два общих значения в теории графов. Одно значение - это граф с эйлеровой схемой, а другое - граф с каждой вершиной четной степени. Эти определения совпадают для связных графов.^[2]

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

Определение

An Эйлерова тропа,^[3] или же Прогулка Эйлера в неориентированный граф это прогулка, в которой каждое ребро используется ровно один раз. Если такое блуждание существует, граф называется проходимый или же полуэуллеров.^[4]

An Эйлеров цикл,^[3] Контур Эйлера или же Эйлер тур в неориентированном графе есть цикл который использует каждое ребро ровно один раз. Если такой цикл существует, граф называется Эйлеров или же уникурсальный.^[5] Термин «эйлеров граф» также иногда используется в более слабом смысле для обозначения графа, в котором каждая вершина имеет четную степень. Для конечных связанные графы эти два определения эквивалентны, в то время как, возможно, несвязный граф эйлеров в более слабом смысле тогда и только тогда, когда каждая связная компонента имеет эйлеров цикл.

За ориентированные графы, "путь" следует заменить на направленный путь и "цикл" с направленный цикл.

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

An Эйлерова ориентация неориентированного графа грамм - задание направления каждому краю грамм такое, что в каждой вершине v, степень v равняется степени v. Такая ориентация существует для любого неориентированного графа, в котором каждая вершина имеет четную степень, и может быть найдена путем построения эйлерова тура в каждой связной компоненте графа. грамм а затем сориентируем края в соответствии с маршрутом.^[6] Любая эйлерова ориентация связного графа является сильная ориентация, ориентация, которая делает полученный ориентированный граф сильно связанный.

Характеристики

• Неориентированный граф имеет эйлеров цикл тогда и только тогда, когда каждая вершина имеет четную степень, и все его вершины с ненулевой степенью принадлежат одному связный компонент.
• Неориентированный граф можно разложить на реберно-непересекающиеся циклы тогда и только тогда, когда все его вершины имеют четную степень. Итак, граф имеет эйлеров цикл тогда и только тогда, когда он может быть разложен на непересекающиеся по ребрам циклы, а его вершины ненулевой степени принадлежат одной компоненте связности.
• Неориентированный граф имеет эйлеров след тогда и только тогда, когда ровно ноль или две вершины имеют нечетную степень, и все его вершины с ненулевой степенью принадлежат одной компоненте связности.
• Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда каждая вершина имеет равные в степени и степень, а все его вершины ненулевой степени принадлежат одному компонент сильной связности. Эквивалентно ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он может быть разложен на реберно-непересекающиеся направленные циклы и все его вершины ненулевой степени принадлежат одной компоненте сильной связности.
• Ориентированный граф имеет эйлеров след тогда и только тогда, когда не более одной вершины имеет (высшая степень ) − (в степени ) = 1, не более одной вершины имеет (входящая степень) - (выходная степень) = 1, каждая другая вершина имеет одинаковую входную и исходящую степень, и все ее вершины с ненулевой степенью принадлежат одной компоненте связности основного неориентированного графа.

Построение эйлеровых троп и схем

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

Алгоритм Флери это элегантный, но неэффективный алгоритм, датируемый 1883 годом.^[7] Рассмотрим граф, в котором все ребра находятся в одной компоненте и не более двух вершин нечетной степени. Алгоритм начинается с вершины нечетной степени или, если в графе ее нет, начинается с произвольно выбранной вершины. На каждом шаге он выбирает следующее ребро на пути, удаление которого не разъединит граф, если только такого ребра нет, и в этом случае он выбирает оставшееся ребро, оставшееся в текущей вершине. Затем он перемещается к другой конечной точке этого ребра и удаляет ребро. В конце алгоритма не остается никаких ребер, и последовательность, из которой были выбраны ребра, образует эйлеров цикл, если в графе нет вершин нечетной степени, или эйлеров след, если есть ровно две вершины нечетной степени.

В то время как обход графа в алгоритме Флери линейна по количеству ребер, т.е. ${ Displaystyle O (| E |)}$, мы также должны учитывать сложность обнаружения мосты. Если мы хотим перезапустить Tarjan алгоритм поиска моста с линейным временем^[8] после удаления каждого ребра алгоритм Флери будет иметь временную сложность ${ Displaystyle O (| E | ^ {2})}$. Алгоритм динамического поиска мостов Thorup (2000) позволяет улучшить это до ${ Displaystyle О (| E | CDOT log ^ {3} | E | CDOT log log | E |)}$, но это все равно значительно медленнее, чем альтернативные алгоритмы.

Алгоритм Хирхольцера

Hierholzer В статье 1873 года предлагается другой метод поиска циклов Эйлера, более эффективный, чем алгоритм Флери:

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

Используя такую ​​структуру данных, как двусвязный список для поддержания набора неиспользуемых ребер, инцидентных каждой вершине, для поддержки списка вершин в текущем обходе, которые имеют неиспользуемые ребра, и для поддержания самого обхода, отдельные операции алгоритма (поиск неиспользуемых ребер, выходящих из каждой вершины, нахождение новая начальная вершина для тура и соединение двух туров, которые имеют общую вершину) могут выполняться в постоянное время каждый, поэтому общий алгоритм требует линейное время, ${ Displaystyle O (| E |)}$.^[9]

Этот алгоритм также может быть реализован с помощью очередь. Поскольку застрять можно только тогда, когда очередь представляет собой закрытый тур, следует повернуть очередь (удалить элемент из головы и добавить его в хвост) до тех пор, пока он не откроется, и продолжить, пока не будут учтены все края. Это также занимает линейное время, поскольку количество выполненных вращений никогда не превышает ${ displaystyle | E |}$.

Подсчет эйлеровых схем

Проблемы сложности

Число эйлеровых схем в диграфы можно рассчитать с помощью так называемого ЛУЧШАЯ теорема, названный в честь де BRuijn, ван АарденнEхренфест, SМиф и Тпроизносить. Формула утверждает, что количество эйлеровых цепей в орграфе является произведением факториалов определенной степени и количества корневых древесные растения. Последний может быть вычислен как детерминант, посредством теорема о матричном дереве, что дает алгоритм с полиномиальным временем.

Теорема BEST впервые сформулирована в такой форме в «примечании, добавленном в доказательство» к статье Аарденна-Эренфеста и де Брюйна (1951). Первоначальное доказательство было биективный и обобщил последовательности де Брейна. Это вариант более раннего результата Смита и Тутте (1941).

Подсчет количества эйлеровых схем на ненаправленный графики намного сложнее. Эта проблема известна как # P-complete.^[10] В положительном направлении Цепь Маркова Монте-Карло подход через Коциг трансформации (представлен Антон Коциг в 1968 г.), как полагают, дает точное приближение для числа эйлеровых схем в графе, хотя до сих пор нет доказательства этого факта (даже для графов ограниченной степени).

Особые случаи

В асимптотическая формула для числа эйлеровых схем в полные графики был определен Маккей и Робинсон (1995):^[11]

${ displaystyle operatorname {ec} (K_ {n}) = 2 ^ {(n + 1) / 2} pi ^ {1/2} e ^ {- n ^ {2} / 2 + 11/12} n ^ {(n-2) (n + 1) / 2} { bigl (} 1 + O (n ^ {- 1/2 + epsilon}) { bigr)}.}$

Аналогичная формула была позже получена М.И. Исаева (2009) за полные двудольные графы:^[12]

${ displaystyle operatorname {ec} (K_ {n, n}) = (n / 2-1)! ^ {2n} 2 ^ {n ^ {2} -n + 1/2} pi ^ {- n +1/2} n ^ {n-1} { bigl (} 1 + O (n ^ {- 1/2 + epsilon}) { bigr)}.}.$

Приложения

Использование эйлеровых путей для решения головоломок, включающих рисование фигуры непрерывным штрихом.
1. Поскольку Загадка Haus vom Nikolaus имеет две нечетные вершины, путь должен начинаться в одной и заканчиваться в другой.
2. У Энни Поуп с четырьмя нечетными вершинами нет решения.
3. Если нечетных вершин нет, путь может начинаться где угодно и образует замкнутый контур.
4. Свободные концы считаются вершинами степени 1.

Эйлеровы тропы используются в биоинформатика реконструировать Последовательность ДНК из его фрагментов.^[13] Они также используются в CMOS схемотехника для поиска оптимального логический вентиль заказ.^[14] Есть несколько алгоритмов обработки деревья которые основаны на эйлеровом обходе дерева (где каждое ребро рассматривается как пара дуг).^[15][16] В последовательности де Брейна могут быть построены как следы Эйлера графы де Брейна.^[17]

В бесконечных графах

Бесконечный граф со всеми степенями вершин, равными четырем, но без эйлеровой прямой

В бесконечный граф, соответствующее понятие эйлерову тропу или эйлерову циклу является эйлеровой линией, дважды бесконечным следом, который покрывает все ребра графа. Для существования такого следа недостаточно, чтобы граф был связным и чтобы все степени вершин были четными; например, бесконечное Граф Кэли показанный, со всеми степенями вершин, равными четырем, не имеет эйлеровой прямой. Бесконечные графы, содержащие эйлеровы прямые, характеризовались Эрды, Грюнвальд и Вайсфельд (1936). Для бесконечного графа или мультиграфа грамм чтобы получить эйлерову прямую, необходимо и достаточно, чтобы выполнялись все следующие условия:^[18][19]

• грамм подключен.
• грамм имеет счетные множества вершин и ребер.
• грамм не имеет вершин (конечной) нечетной степени.
• Удаление любого конечного подграфа S из грамм оставляет не более двух бесконечных компонент связности в оставшемся графе, а если S имеет четную степень в каждой вершине, то удаляя S оставляет ровно одну бесконечную компоненту связности.

Смотрите также

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

Примечания

Рекомендации

• Erdõs, Пал; Грюнвальд, Тибор; Вайсфельд, Эндре (1936), "Végtelen gráfok Euler vonalairól" [О линиях Эйлера бесконечных графов] (PDF), Мат. Исправить. Лапок (на венгерском), 43: 129–140. Переведено как Эрдеш, П.; Грюнвальд, Т.; Вазсоний, Э. (1938), "Über Euler-Linien undendlicher Graphen" [Об эйлеровых прямых в бесконечных графах] (PDF), J. Math. Phys. (на немецком), 17 (1–4): 59–75, Дои:10.1002 / sapm193817159.
• Эйлер, Л. "Решение проблемы с геометрией situs pertinentis ", Комментарий. Academiae Sci. I. Petropolitanae 8 (1736), 128–140.
• Хирхольцер, Карл (1873), "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen, 6 (1): 30–32, Дои:10.1007 / BF01442866.
• Лукас, Э., Récréations Mathématiques IV, Париж, 1921 год.
• Флери, "Две проблемы геометрии ситуации", Journal de mathematiques elementaires (1883), 257–261.
• Т. ван Аарденне-Эренфест и Н. Г. де Брёйн (1951) "Схемы и деревья в ориентированных линейных графах", Саймон Стевин 28: 203–217.
• Торуп, Миккель (2000), "Почти оптимальная полностью динамическая связность графов", Proc. 32-й симпозиум ACM по теории вычислений, стр. 343–350, Дои:10.1145/335305.335345
• В. Т. Тутте и К. А. Б. Смит (1941) «О уникурсальных путях в сети степени 4», Американский математический ежемесячный журнал 48: 233–237.

внешняя ссылка

• Обсуждение ранних упоминаний алгоритма Флери.
• Эйлер тур в Энциклопедия математики.