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

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

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

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

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

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

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

Определение [ править ]

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

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

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

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

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

Свойства [ править ]

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

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

Алгоритм Флери [ править ]

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

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

Алгоритм Хирхольцера [ править ]

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

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

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

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

Подсчет эйлеровых схем [ править ]

Проблемы сложности [ править ]

Количество эйлеровых цепей в орграфах можно рассчитать , используя так называемую ЛУЧШУЮ теорему , названную в честь де B ruijn , ван Aardenne- Х hrenfest , S Mith и Т utte . Формула утверждает, что количество эйлеровых цепей в орграфе является произведением факториалов определенной степени и количества корневых ветвей . Последний может быть вычислен как определитель по теореме о матричном дереве , что дает алгоритм с полиномиальным временем.

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

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

Особые случаи [ править ]

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

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

Приложения [ править ]

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

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

В бесконечных графах [ править ]

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

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Н.Л. Биггс, Е.К. Ллойд и Р.Дж. Уилсон, Теория графов, 1736–1936 , Clarendon Press, Oxford, 1976, 8–9, ISBN  0-19-853901-0 .
  2. ^ CL Мальвы, NJA Sloane (1975). «Двухграфы, классы переключения и графы Эйлера равны по количеству» (PDF) . Журнал СИАМ по прикладной математике . 28 (4): 876–880. DOI : 10.1137 / 0128070 . JSTOR 2100368 .  
  3. ^ a b Некоторые люди резервируют термины путь и цикл для обозначения несамопересекающихся путей и циклов. (Потенциально) самопересекающийся путь известен как тропа или открытая прогулка ; и (потенциально) самопересекающийся цикл, кругооборот или замкнутая прогулка . Этой неоднозначности можно избежать, используя термины Эйлеров след и Эйлеров контур, когда разрешено самопересечение.
  4. ^ Дзюн-ичи Ямагути, Введение в теорию графов .
  5. ^ Очерк теории Шаума и проблемы теории графов В.К. Балакришнан [1] .
  6. ^ Шриджвер, А. (1983), "Граница числа эйлеровых ориентаций" , Combinatorica , 3 (3-4): 375-380, DOI : 10.1007 / BF02579193 , МР 0729790 .
  7. ^ Флери, Пьер-Анри (1883), "Deux problèmes de Géométrie deposition" , 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. Перейти ↑ MI Isaev (2009). «Асимптотическое число схем Эйлера в полных двудольных графах». Proc. 52-я конференция МФТИ . Москва: 111–114.
  13. ^ Певзнер, Павел А .; Тан, Хайсю; Уотерман, Майкл С. (2001). «Эйлеров след подход к сборке фрагментов ДНК» . Труды Национальной академии наук Соединенных Штатов Америки . 98 (17): 9748–9753. Bibcode : 2001PNAS ... 98.9748P . DOI : 10.1073 / pnas.171285098 . PMC 55524 . PMID 11504945 .  
  14. ^ Рой, Кунтал (2007). «Оптимальный порядок вентилей логических вентилей CMOS с использованием подхода Эйлера пути: некоторые идеи и объяснения» . Журнал вычислительной техники и информационных технологий . 15 (1): 85–92. DOI : 10.2498 / cit.1000731 .
  15. ^ Tarjan, Роберт E .; Вишкин, Узи (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 Обзор . 39 (4): 605–629. DOI : 10.1137 / S0036144595295272 . ISSN 0036-1445 . 
  18. ^ Komjáth, Питер (2013), «Работа Эрдёша над бесконечными графами» , столетие Эрдёша , Bolyai Soc. Математика. Stud., 25 , János Bolyai Math. . Soc . , Будапешт, С. 325-345, DOI : 10.1007 / 978-3-642-39286-3_11 , МР 3203602 .
  19. ^ Bollobás, Бел (1998), Современная теория графов , Graduate тексты по математике, 184 , Springer-Verlag, Нью - Йорк, стр. 20, DOI : 10.1007 / 978-1-4612-0619-4 , ISBN 0-387-98488-7, Руководство по ремонту  1633290.

Ссылки [ править ]

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

Внешние ссылки [ править ]

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