В теории графов , 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]
Приложения
Следы Эйлера используются в биоинформатике для восстановления последовательности ДНК из ее фрагментов. [13] Они также используются в схемах КМОП для поиска оптимального порядка логических элементов . [14] Есть несколько алгоритмов обработки деревьев , основанных на эйлеровом обходе дерева (где каждое ребро рассматривается как пара дуг). [15] [16] Последовательности де Брейна могут быть построены как эйлеровы следы графов де Брейна . [17]
В бесконечных графах
В бесконечном графе понятие, соответствующее эйлерову тропу или эйлерову циклу, является эйлеровой линией, дважды бесконечным следом, покрывающим все ребра графа. Для существования такого следа недостаточно, чтобы граф был связным и чтобы все степени вершин были четными; например, показанный бесконечный граф Кэли со всеми степенями вершин, равными четырем, не имеет эйлеровой прямой. Бесконечные графы, содержащие эйлеровы прямые, были охарактеризованы Erdõs, Grünwald и Weiszfeld (1936) . Для того чтобы бесконечный граф или мультиграф G имел эйлерову прямую, необходимо и достаточно, чтобы выполнялись все следующие условия: [18] [19]
- G связан.
- G имеет счетное множество вершин и ребер.
- G не имеет вершин (конечной) нечетной степени.
- Удаление любого конечного подграфа S из G оставляет не более двух бесконечных компонент связности в оставшемся графе, и если S имеет четную степень в каждой из его вершин, то удаление S оставляет ровно одну бесконечную компоненту связности.
Смотрите также
- Эйлеров матроид , абстрактное обобщение эйлеровых графов
- Пазл с пятью комнатами
- Лемма о рукопожатии , доказанная Эйлером в его оригинальной статье, показывающая, что любой неориентированный связный граф имеет четное число вершин нечетной степени
- Гамильтонов путь - путь, который посещает каждую вершину ровно один раз.
- Задача проверки маршрута , поиск кратчайшего пути, который посещает все ребра, возможно, повторяющиеся ребра, если эйлеров путь не существует.
- Теорема Веблена о том , что графы с четной степенью вершин можно разбить на реберно-непересекающиеся циклы независимо от их связности.
Заметки
- ^ Н.Л. Биггс, Е.К. Ллойд и Р.Дж. Уилсон, Теория графов, 1736–1936 , Clarendon Press, Oxford, 1976, 8–9, ISBN 0-19-853901-0 .
- ^ CL Mallows, NJA Sloane (1975). «Двухграфы, классы переключения и графы Эйлера равны по количеству» (PDF) . Журнал SIAM по прикладной математике . 28 (4): 876–880. DOI : 10.1137 / 0128070 . JSTOR 2100368 .
- ^ a b Некоторые люди резервируют термины путь и цикл для обозначения несамопересекающихся путей и циклов. (Потенциально) самопересекающийся путь известен как тропа или открытая прогулка ; и (потенциально) самопересекающийся цикл, кругооборот или замкнутая прогулка . Этой неоднозначности можно избежать, используя термины Эйлеров след и Эйлеров контур, когда разрешено самопересечение.
- ^ Дзюн-ичи Ямагути, Введение в теорию графов .
- ^ Очерк теории Шаума и проблемы теории графов В.К. Балакришнан [1] .
- ^ Шриджвер, А. (1983), "Граница числа эйлеровых ориентаций" , Combinatorica , 3 (3-4): 375-380, DOI : 10.1007 / BF02579193 , МР 0729790.
- ^ Флери, Пьер-Анри (1883 г.), "Deux problèmes de Géométrie deposition" , 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). «Асимптотическое число схем Эйлера в полных двудольных графах». Proc. 52-я конференция МФТИ . Москва: 111–114.
- ^ Певзнер, Павел А .; Тан, Хайсю; Уотерман, Майкл С. (2001). «Эйлеров след подход к сборке фрагментов ДНК» . Труды Национальной академии наук Соединенных Штатов Америки . 98 (17): 9748–9753. Bibcode : 2001PNAS ... 98.9748P . DOI : 10.1073 / pnas.171285098 . PMC 55524 . PMID 11504945 .
- ^ Рой, Кунтал (2007). «Оптимальный порядок вентилей логических вентилей CMOS с использованием подхода Эйлера пути: некоторые идеи и объяснения» . Журнал вычислительной техники и информационных технологий . 15 (1): 85–92. DOI : 10.2498 / cit.1000731 .
- ^ Tarjan, Robert E .; Вишкин, Узи (1985). «Эффективный параллельный алгоритм двусвязности». SIAM Journal on Computing . 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . DOI : 10.1137 / 0214061 .
- ^ Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Поиск предков уровней в деревьях» . J. Comput. Syst. Sci . 2. 48 (2): 214–230. DOI : 10.1016 / S0022-0000 (05) 80002-9 .
- ^ Сэвидж, Карла (январь 1997 г.). "Обзор комбинаторных кодов Грея". SIAM Обзор . 39 (4): 605–629. DOI : 10.1137 / S0036144595295272 . ISSN 0036-1445 .
- ^ Комьят, Питер (2013), «Работа Эрдёша над бесконечными графами» , столетие Эрдёша , Bolyai Soc. Математика. Stud., 25 , János Bolyai Math. . Soc . , Будапешт, С. 325-345, DOI : 10.1007 / 978-3-642-39286-3_11 , МР 3203602.
- ^ Боллобас, Бела (1998), Современная теория графов , Тексты для выпускников по математике, 184 , Springer-Verlag, New York, p. 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.. Переведено как Erds, 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.
Внешние ссылки
- Обсуждение ранних упоминаний алгоритма Флери .
- Эйлер тур по энциклопедии математики .