Jump to content

Эйлеров путь

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

В теории графов эйлеров след (или эйлеров путь ) — это путь в конечном графе, который посещает каждое ребро ровно один раз (что позволяет повторно посещать вершины). Аналогично, эйлеров контур или эйлеров цикл — это эйлеров путь, который начинается и заканчивается в одной и той же вершине . Впервые они были обсуждены Леонардом Эйлером при решении знаменитой задачи о семи мостах Кенигсберга в 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.

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

[ редактировать ]

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

Хотя обход графа в алгоритме Флери линеен по числу ребер, т.е. нам также необходимо учитывать сложность обнаружения мостов . Если мы хотим повторно запустить алгоритм Тарьяна линейного времени по поиску мостов [8] после удаления каждого ребра алгоритм Флёри будет иметь временную сложность . Алгоритм динамического поиска мостов Thorup (2000) позволяет улучшить это до , но это все равно значительно медленнее, чем альтернативные алгоритмы.

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

[ редактировать ]

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

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

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

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

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

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

[ редактировать ]

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

Приложения

[ редактировать ]

Эйлеровы следы используются в биоинформатике для восстановления последовательности ДНК по ее фрагментам. [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. ^ Jump up to: а б Некоторые люди оставляют термины «путь» и «цикл» для обозначения несамопересекающихся пути и цикла. (Потенциально) самопересекающийся путь известен как тропа или открытая прогулка ; и (потенциально) самопересекающийся цикл, контур или замкнутый маршрут . Этой двусмысленности можно избежать, используя термины «эйлеров след» и «эйлеров контур», когда разрешено самопересечение.
  1. ^ Н.Л. Биггс, Е.К. Ллойд и Р.Дж. Уилсон, Теория графов, 1736–1936 , Clarendon Press, Oxford, 1976, 8–9, ISBN   0-19-853901-0 .
  2. ^ С. Л. Маллоуз, NJA Слоан (1975). «Два графа, классы переключения и графы Эйлера равны по количеству» (PDF) . SIAM Journal по прикладной математике . 28 (4): 876–880. дои : 10.1137/0128070 . JSTOR   2100368 .
  3. ^ Дзюнъити Ямагучи, Введение в теорию графов .
  4. ^ Очерк теории и проблем теории графов Шаума В.К. Балакришнаном [1] .
  5. ^ Шрийвер, А. (1983), «Границы числа эйлеровых ориентаций» , Combinatorica , 3 (3–4): 375–380, doi : 10.1007/BF02579193 , MR   0729790 , S2CID   13708977 .
  6. ^ Jump up to: а б с д Полиа, Джордж ; Тарьян, Роберт Э .; Вудс, Дональд Р. (октябрь 2009 г.), «Гамильтоновы и эйлеровы пути», Заметки по вводной комбинаторике , Birkhäuser Boston, стр. 157–168, doi : 10.1007/978-0-8176-4953-1_13 , ISBN  9780817649531
  7. ^ Флери, Пьер-Анри (1883), «Две задачи ситуационной геометрии» , Журнал элементарной математики , 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. Бибкод : 2001PNAS...98.9748P . дои : 10.1073/pnas.171285098 . ПМК   55524 . ПМИД   11504945 .
  14. ^ Рой, Кунтал (2007). «Оптимальный порядок логических элементов КМОП с использованием подхода Эйлера: некоторые идеи и объяснения» . Журнал вычислительной техники и информационных технологий . 15 (1): 85–92. дои : 10.2498/cit.1000731 .
  15. ^ Тарьян, Роберт Э.; Вишкин, Узи (1985). «Эффективный параллельный алгоритм двусвязности». SIAM Journal по вычислительной технике . 14 (4): 862–874. CiteSeerX   10.1.1.465.8898 . дои : 10.1137/0214061 .
  16. ^ Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Нахождение уровней-предков в деревьях». Дж. Компьютер. Сист. Наука . 2. 48 (2): 214–230. дои : 10.1016/S0022-0000(05)80002-9 .
  17. ^ Сэвидж, Карла (январь 1997 г.). «Обзор комбинаторных кодов Грея». Обзор СИАМ . 39 (4): 605–629. дои : 10.1137/S0036144595295272 . ISSN   0036-1445 .
  18. ^ Комьят, Питер (2013), «Работа Эрдеша над бесконечными графами» , Столетие Эрдеша , Bolyai Soc. Студ., вып. 25, Янош Бояи Матем. Соц., Будапешт, с. 325–345, doi : 10.1007/978-3-642-39286-3_11 , МР   3203602 .
  19. ^ Боллобас, Бела (1998), Современная теория графов , Тексты для аспирантов по математике, том. 184, Спрингер-Верлаг, Нью-Йорк, с. 20, номер домена : 10.1007/978-1-4612-0619-4 , ISBN  0-387-98488-7 , МР   1633290 .
  20. ^ Jump up to: а б с д и ж Корберан, Анхель; Лапорт, Гилберт, ред. (2015). Дуговая трассировка: проблемы, методы и приложения . Серия MOS-SIAM по оптимизации. СИАМ. дои : 10.1137/1.9781611973679 . ISBN  978-1-61197-366-2 . Проверено 19 августа 2022 г.

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 077f0845d1e06bb7baff2d4256de1dc4__1714794840
URL1:https://arc.ask3.ru/arc/aa/07/c4/077f0845d1e06bb7baff2d4256de1dc4.html
Заголовок, (Title) документа по адресу, URL1:
Eulerian path - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)