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