Эйлеров путь

Тропа в графе, которая посещает каждое ребро один раз

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

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

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

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

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

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

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

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

Определение

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

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

Для направленных графов «путь» необходимо заменить на направленный путь , а «цикл» на направленный цикл .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ортографические проекции и диаграммы Шлегеля с гамильтоновыми циклами вершин пяти платоновых тел – только октаэдр имеет эйлеров путь или цикл, расширяя свой путь с помощью пунктирного пути

• в
• т
• е

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

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

Число эйлеровых контуров в орграфах можно вычислить с помощью так называемой теоремы BEST , названной в честь де Брёйна , ван Аарденне - Эренфеста , Смита и Т утте . Формула гласит, что число эйлеровых контуров в орграфе является произведением определенных факториалов степени и числа корневых древовидных структур . Последнее может быть вычислено как определитель с помощью теоремы о матричном дереве , что дает алгоритм с полиномиальным временем.

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

Неориентированные эйлеровы графы

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

Следующий результат был доказан Вебленом в 1912 году: неориентированный связный граф является эйлеровым тогда и только тогда, когда он является несвязным объединением некоторых циклов. ^[20]

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

Хирхольцер разработал линейный алгоритм построения эйлерова тура в неориентированном графе.

Направленные эйлеровы графы

Возможно иметь направленный граф , который имеет все четные исходящие степени, но не является эйлеровым. Поскольку эйлеров цикл покидает вершину столько же раз, сколько входит в нее, необходимым условием для существования эйлерова цикла является равенство входящей и исходящей степеней в каждой вершине. Очевидно, что связность также необходима. Кёниг доказал, что эти условия также достаточны. То есть направленный граф является эйлеровым тогда и только тогда, когда он связен, а входящая и исходящая степени равны в каждой вершине. ^[20]

В этой теореме не имеет значения, означает ли «связный» «слабо связанный» или «сильно связанный», поскольку для эйлеровых графов они эквивалентны.

Линейный алгоритм времени Хирхольцера для построения эйлерова тура применим также к ориентированным графам. ^[20]

Смешанные эйлеровы графы

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

Все смешанные графы , которые являются одновременно четными и симметричными, гарантированно являются эйлеровыми. Однако это не является необходимым условием, поскольку можно построить несимметричный четный граф, который является эйлеровым. ^[20]

В 1962 году в своей книге «Потоки в сетях» Форд и Фулкерсон доказали необходимое и достаточное условие для того, чтобы граф был эйлеровым, а именно, что каждая вершина должна быть четной и удовлетворять условию баланса, т. е. для каждого подмножества вершин S разница между числом дуг, выходящих из S и входящих в S, должна быть меньше или равна числу ребер, инцидентных S. ^[20]

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

Чётный смешанный граф, который нарушает условие сбалансированности множества и, следовательно, не является эйлеровым.

Чётный смешанный граф, который удовлетворяет условию сбалансированного множества и, следовательно, является эйлеровым смешанным графом.

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

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

Примечания

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

Ссылки

1. Н. Л. Биггс, Э. К. Ллойд и Р. Дж. Уилсон, Теория графов, 1736–1936 , Clarendon Press, Оксфорд, 1976, 8–9, ISBN  0-19-853901-0 .
2. CL Mallows, NJA Sloane (1975). «Двухграфы, переключающиеся классы и графы Эйлера равны по числу» (PDF) . SIAM Journal on Applied Mathematics . 28 (4): 876–880. doi :10.1137/0128070. JSTOR  2100368.
3. Дзюнъити Ямагути, Введение в теорию графов.
4. Очерк теории и проблем теории графов Шаума. В.К. Балакришнан [1].
5. Schrijver, A. (1983), «Границы числа эйлеровых ориентаций», Combinatorica , 3 (3–4): 375–380, doi :10.1007/BF02579193, MR  0729790, S2CID  13708977.
6. Полиа, Джордж ; Тарьян, Роберт Э .; Вудс, Дональд Р. (октябрь 2009 г.), «Гамильтоновы и эйлеровы пути», Заметки по вводной комбинаторике , Birkhäuser Boston, стр. 157–168, doi :10.1007/978-0-8176-4953-1_13, ISBN 9780817649531
7. Флери, Пьер-Анри (1883), «Две проблемы геометрии ситуации», Journal de mathématiques élémentaires , 2-я сер. (на французском языке), 2 : 257–261..
8. Тарьян, Р. Эндре (1974), «Заметка о поиске мостов графа», Information Processing Letters , 2 (6): 160–161, doi :10.1016/0020-0190(74)90003-9, MR  0349483.
9. Флейшнер, Герберт (1991), «X.1 Алгоритмы для эйлеровых путей», Эйлеровы графы и смежные темы: Часть 1, Том 2, Анналы дискретной математики, т. 50, Elsevier, стр. X.1–13, ISBN 978-0-444-89110-5.
10. Брайтвелл и Винклер , «Заметка о подсчете эйлеровых цепей», 2004.
11. Брендан Маккей и Роберт В. Робинсон, Асимптотическое перечисление эйлеровых цепей в полном графе, Combinatorica , 10 (1995), № 4, 367–377.
12. М. И. Исаев (2009). «Асимптотическое число эйлеровых циклов в полных двудольных графах». Труды 52-й конференции МФТИ . М.: 111–114.
13. Певзнер, Павел А.; Тан, Хайсю; Уотерман, Майкл С. (2001). «Подход Эйлерова следа к сборке фрагментов ДНК». Труды Национальной академии наук Соединенных Штатов Америки . 98 (17): 9748–9753. Bibcode : 2001PNAS ...98.9748P. doi : 10.1073/pnas.171285098 . PMC 55524. PMID  11504945. 
14. Рой, Кунтал (2007). «Оптимальное упорядочение логических вентилей КМОП с использованием подхода Эйлера: некоторые идеи и объяснения». Журнал вычислительной техники и информационных технологий . 15 (1): 85–92. doi : 10.2498/cit.1000731 .
15. Tarjan, Robert E.; Vishkin, Uzi (1985). «Эффективный параллельный алгоритм двусвязности». SIAM Journal on Computing . 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . doi :10.1137/0214061. 
16. Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Поиск предков уровня в деревьях». J. Comput. Syst. Sci . 2. 48 (2): 214–230. doi :10.1016/S0022-0000(05)80002-9.
17. Сэвидж, Карла (январь 1997 г.). «Обзор комбинаторных кодов Грея». SIAM Review . 39 (4): 605–629. doi :10.1137/S0036144595295272. ISSN  0036-1445.
18. Комьят, Питер (2013), «Работа Эрдеша над бесконечными графами», столетие Эрдеша , Bolyai Soc. Математика. Студ., вып. 25, Янош Бояи Матем. Soc., Будапешт, стр. 325–345, doi :10.1007/978-3-642-39286-3_11, MR  3203602.
19. Боллобаш, Бела (1998), Современная теория графов, Graduate Texts in Mathematics, т. 184, Springer-Verlag, Нью-Йорк, стр. 20, doi :10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, г-н  1633290.
20. Corberán, Ángel; Laporte, Gilbert, ред. (2015). Arc Routing: Problems, Methods, and Applications. Серия MOS-SIAM по оптимизации. SIAM. doi :10.1137/1.9781611973679. ISBN 978-1-61197-366-2. Получено 2022-08-19 .

Библиография

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

Внешние ссылки

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