Эйлеров путь

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

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

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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подсчитать количество эйлеровых схем на неориентированных графах гораздо сложнее. Эта задача известна как #P-complete . ^[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}} + \ эпсилон}) {\ bigr)}.}

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

{\ displaystyle \ operatorname {ec} (K_ {n, n}) = ({\ frac {n} {2}} -1)! ^ {2n} 2 ^ {n ^ {2} -n + {\ frac { 1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1} {2}}+\эпсилон}){\bigr)}.}

Приложения

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

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

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

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

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

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

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

Примечания

^ Н. Л. Биггс, Э. К. Ллойд и Р. Дж. Уилсон, Теория графов, 1736–1936 , Clarendon Press, Оксфорд, 1976, 8–9, ISBN 0-19-853901-0 .
^ CL Mallows, NJA Sloane (1975). «Два графа, классы переключения и графы Эйлера равны по количеству» (PDF) . Журнал SIAM по прикладной математике . 28 (4): 876–880. дои : 10.1137/0128070 . JSTOR 2100368 .
^ a b Некоторые люди резервируют термины « путь » и « цикл » для обозначения несамопересекающихся путей и циклов. (Потенциально) самопересекающийся путь известен как тропа или открытая прогулка ; и (потенциально) самопересекающийся цикл, цепь или замкнутый маршрут . Этой двусмысленности можно избежать, используя термины эйлерова тропа и эйлерова цепь, когда разрешено самопересечение.
^ Джун-ити Ямагути, Введение в теорию графов .
^ Очерк теории и проблем теории графов Шаума В. К. Балакришнан [1] .
^ Шрайвер, А. (1983), «Границы числа эйлеровых ориентаций» , Combinatorica , 3 (3–4): 375–380, doi : 10.1007/BF02579193 , MR 0729790 , S2CID 13708977 .
↑ Флери, Пьер-Анри (1883), «Deux problèmes de Géométrie de position» , Journal de mathématiques élémentaires , 2-я сер. (на французском), 2 : 257–261..
^ Тарьян, Р. Эндре (1974), «Заметка о поиске мостов графа», Письма по обработке информации , 2 (6): 160–161, doi : 10.1016/0020-0190 (74) 90003-9 , MR 0349483 .
^ Флейшнер, Герберт (1991), «Алгоритмы X.1 для эйлеровых троп», Эйлеровы графы и связанные темы: Часть 1, Том 2 , Анналы дискретной математики, том. 50, Elsevier, стр. X.1–13 , ISBN 978-0-444-89110-5.
^ Брайтуэлл и Винклер , « Заметка о подсчете эйлеровых цепей », 2004.
^ Брендан Маккей и Роберт В. Робинсон, Асимптотическое перечисление эйлеровых схем в полном графе , Combinatorica , 10 (1995), нет. 4, 367–377.
^ М.И. Исаев (2009). «Асимптотическое число эйлеровых схем в полных двудольных графах». проц. 52-я конференция МФТИ . Москва: 111–114.
^ Певзнер, Павел А .; Тан, Хайсюй; Уотерман, Майкл С. (2001). «Подход Эйлера к сборке фрагментов ДНК» . Труды Национальной академии наук Соединенных Штатов Америки . 98 (17): 9748–9753. Бибкод : 2001PNAS...98.9748P . doi : 10.1073/pnas.171285098 . ПМС 55524 . PMID 11504945 .
^ Рой, Кунтал (2007). «Оптимальный порядок логических элементов CMOS с использованием подхода Эйлера: некоторые идеи и объяснения» . Журнал вычислительной техники и информационных технологий . 15 (1): 85–92. doi : 10.2498/цит.1000731 .
^ Тарьян, Роберт Э .; Вишкин, Узи (1985). «Эффективный параллельный алгоритм двусвязности». Журнал SIAM по вычислительной технике . 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . дои : 10.1137/0214061 .
^ Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Поиск уровней-предков в деревьях» . Дж. Вычисл. Сист. науч . 2. 48 (2): 214–230. doi : 10.1016/S0022-0000(05)80002-9 .
^ Сэвидж, Карла (январь 1997 г.). «Обзор комбинаторных кодов Грея». Обзор СИАМ . 39 (4): 605–629. doi : 10.1137/S0036144595295272 . ISSN 0036-1445 .
↑ Komjáth , Peter (2013), «Работа Эрдёша о бесконечных графах» , Столетие Эрдёша , Bolyai Soc. Мат. Студ., вып. 25, Янош Бойяи Матем. Soc., Будапешт, стр. 325–345, doi : 10.1007/978-3-642-39286-3_11 , MR 3203602 .
^ Боллобас, Бела (1998), Современная теория графов , Тексты для выпускников по математике, том. 184, Springer-Verlag, Нью-Йорк, с. 20, дои : 10.1007/978-1-4612-0619-4 , ISBN 0-387-98488-7, МР 1633290.

использованная литература

Эрдёш, Пал ; Грюнвальд, Тибор ; Вайсфельд, Эндре (1936), "Végtelen grafok Euler vonalairól" [О линиях Эйлера бесконечных графов] (PDF) , Матем. Исправить. Лапок (на венгерском языке), 43 : 129–140.. Переведено как Erdős, P. ; Грюнвальд, Т. ; Вазсони, Э. (1938), "Über Euler-Linien unendlicher Graphen" [Об эйлеровых линиях в бесконечных графах] (PDF) , J. Math. физ. (на немецком языке), 17 (1–4): 59–75, doi : 10.1002/sapm193817159.
Эйлер, Л., « Solutio Problematis Ad Geometriam Situs Pertinentis », Комментарий. Академии наук. I. Petropolitanae 8 (1736), 128–140.
Hierholzer, Carl (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.
Лукас, Э., Математические развлечения IV , Париж, 1921.
Флери, «Вторые проблемы геометрии ситуации», Journal de mathematiques elementaires (1883 г.), 257–261.
Т. ван Аарденн-Эренфест и Н. Г. де Брейн (1951) «Схемы и деревья в ориентированных линейных графах», Саймон Стевин 28: 203–217.
Торуп, Миккель (2000), «Почти оптимальная связность полностью динамического графа», Proc. 32-й симпозиум ACM по теории вычислений , стр. 343–350, doi : 10.1145/335305.335345 , S2CID 128282
В. Т. Татт и К. А. Б. Смит (1941) «Об однонаправленных путях в сети степени 4», American Mathematical Monthly 48: 233–237 .

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

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

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

[1] Н. Л. Биггс, Э. К. Ллойд и Р. Дж. Уилсон, Теория графов, 1736–1936 , Clarendon Press, Оксфорд, 1976, 8–9, ISBN 0-19-853901-0 .

[2] CL Mallows, NJA Sloane (1975). «Два графа, классы переключения и графы Эйлера равны по количеству» (PDF) . Журнал SIAM по прикладной математике . 28 (4): 876–880. дои : 10.1137/0128070 . JSTOR 2100368 .

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

[4] Джун-ити Ямагути, Введение в теорию графов .

[5] Очерк теории и проблем теории графов Шаума В. К. Балакришнан [1] .

[6] Шрайвер, А. (1983), «Границы числа эйлеровых ориентаций» , Combinatorica , 3 (3–4): 375–380, doi : 10.1007/BF02579193 , MR 0729790 , S2CID 13708977 .

[7] Флери, Пьер-Анри (1883), «Deux problèmes de Géométrie de position» , Journal de mathématiques élémentaires , 2-я сер. (на французском), 2 : 257–261..

[8] Тарьян, Р. Эндре (1974), «Заметка о поиске мостов графа», Письма по обработке информации , 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. Бибкод : 2001PNAS...98.9748P . doi : 10.1073/pnas.171285098 . ПМС 55524 . PMID 11504945 .

[14] Рой, Кунтал (2007). «Оптимальный порядок логических элементов CMOS с использованием подхода Эйлера: некоторые идеи и объяснения» . Журнал вычислительной техники и информационных технологий . 15 (1): 85–92. doi : 10.2498/цит.1000731 .

[15] Тарьян, Роберт Э .; Вишкин, Узи (1985). «Эффективный параллельный алгоритм двусвязности». Журнал SIAM по вычислительной технике . 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . дои : 10.1137/0214061 .

[16] Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Поиск уровней-предков в деревьях» . Дж. Вычисл. Сист. науч . 2. 48 (2): 214–230. doi : 10.1016/S0022-0000(05)80002-9 .

[17] Сэвидж, Карла (январь 1997 г.). «Обзор комбинаторных кодов Грея». Обзор СИАМ . 39 (4): 605–629. doi : 10.1137/S0036144595295272 . ISSN 0036-1445 .

[18] ↑ Komjáth , Peter (2013), «Работа Эрдёша о бесконечных графах» , Столетие Эрдёша , Bolyai Soc. Мат. Студ., вып. 25, Янош Бойяи Матем. Soc., Будапешт, стр. 325–345, doi : 10.1007/978-3-642-39286-3_11 , MR 3203602 .

[19] Боллобас, Бела (1998), Современная теория графов , Тексты для выпускников по математике, том. 184, Springer-Verlag, Нью-Йорк, с. 20, дои : 10.1007/978-1-4612-0619-4 , ISBN 0-387-98488-7, МР 1633290.

[1]