Эйлеров путь

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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\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}}+\epsilon }){\bigr )}.

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

\operatorname {ec} (K_{n,n})=\left({\frac {n}{2}}-1\right)!^{2n}2^{n^{2}-n+{\frac {1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.

Приложения

Эйлеровы следы используются в биоинформатике для восстановления последовательности ДНК по ее фрагментам. ^[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.

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

[pathcycle-3] 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 .

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

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

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

[ptw-7] Jump up to: ^а ^б ^с ^д Полиа, Джордж ; Тарьян, Роберт Э .; Вудс, Дональд Р. (октябрь 2009 г.), «Гамильтоновы и эйлеровы пути», Заметки по вводной комбинаторике , Birkhäuser Boston, стр. 157–168, doi : 10.1007/978-0-8176-4953-1_13 , ISBN 9780817649531

[8] Флери, Пьер-Анри (1883), «Две задачи ситуационной геометрии» , Журнал элементарной математики , 2-я сер. (на французском языке), 2 : 257–261 .

[9] Тарьян, Р. Эндре (1974), «Заметки о поиске мостов графа», Information Processing Letters , 2 (6): 160–161, doi : 10.1016/0020-0190(74)90003-9 , MR 0349483 .

[10] Флейшнер, Герберт (1991), «Алгоритмы X.1 для эйлеровых путей», эйлеровы графики и смежные темы: часть 1, том 2 , Анналы дискретной математики, том. 50, Elsevier, стр. X.1–13 , ISBN. 978-0-444-89110-5 .

[11] Брайтуэлл и Винклер , « Заметки о подсчете эйлеровых цепей », 2004.

[12] Брендан Маккей и Роберт В. Робинсон, Асимптотическое перечисление эйлеровых схем в полном графе , Combinatorica , 10 (1995), вып. 4, 367–377.

[13] М.И. Исаев (2009). «Асимптотическое число эйлеровых схем в полных двудольных графах». Учеб. 52-я конференция МФТИ . Москва: 111–114.

[14] Певзнер, Павел А.; Тан, Хайсюй; Уотерман, Майкл С. (2001). «Эйлеров подход к сборке фрагментов ДНК» . Труды Национальной академии наук Соединенных Штатов Америки . 98 (17): 9748–9753. Бибкод : 2001PNAS...98.9748P . дои : 10.1073/pnas.171285098 . ПМЦ 55524 . ПМИД 11504945 .

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

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

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

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

[19] Комьят, Питер (2013), «Работа Эрдеша над бесконечными графами» , Столетие Эрдеша , Bolyai Soc. Студ., вып. 25, Янош Бояи Матем. Соц., Будапешт, с. 325–345, doi : 10.1007/978-3-642-39286-3_11 , МР 3203602 .

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

[:0-21] Jump up to: ^а ^б ^с ^д ^и ^ж Корберан, Анхель; Лапорт, Гилберт, ред. (2015). Дуговая трассировка: проблемы, методы и приложения . Серия MOS-SIAM по оптимизации. СИАМ. дои : 10.1137/1.9781611973679 . ISBN 978-1-61197-366-2 . Проверено 19 августа 2022 г.

[1]

[2]

[примечание 1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]