Введение

Путь в графе, проходящий по каждому ребру ровно один раз

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

Для заданного графа на изображении, возможно ли построить путь (или цикл, то есть путь, начинающийся и заканчивающийся в одной и той же вершине), который проходит по каждому ребру ровно один раз? Эйлер доказал, что необходимым условием существования эйлеровых циклов является то, что все вершины графа имеют чётную степень, и без доказательства утверждал, что связные графы, у всех вершин которых чётная степень, имеют эйлеров цикл. Первое полное доказательство этого утверждения было опубликовано посмертно в 1873 году Карлом Иерхольцером. Это известно как теорема Эйлера:

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

Определение

Эйлеровский путь, или эйлеровская ходьба, в неориентированном графе — это путь, который использует каждое ребро ровно один раз. Если такой путь существует, граф называется обходимым или полуэйлеровым. Термин «эйлеров граф» также иногда используется в более слабом смысле для обозначения графа, в котором каждая вершина имеет чётную степень. Для конечных связных графов оба определения эквивалентны, в то время как несвязный граф является эйлеровым в более слабом смысле тогда и только тогда, когда каждая связная компонента имеет эйлеров цикл. Для ориентированных графов термин «путь» следует заменять на «ориентированный путь», а «цикл» — на «ориентированный цикл». Определение и свойства эйлеровских путей, циклов и графов справедливы также и для мультиграфов. Эйлерова ориентация неориентированного графа G — это присвоение направления каждому ребру G таким образом, чтобы в каждой вершине v входящая степень v равнялась исходящей степени v. Такая ориентация существует для любого неориентированного графа, в котором каждая вершина имеет чётную степень, и может быть найдена путём построения эйлерова тура в каждой связной компоненте G, а затем ориентирования рёбер в соответствии с этим туром. Любая эйлерова ориентация связного графа является сильной ориентацией, то есть ориентацией, которая делает полученный ориентированный граф сильно связным.

Свойства

Ненаправленный граф имеет эйлеров цикл, если и только если каждая вершина имеет чётную степень, и все его вершины с ненулевой степенью принадлежат одному связному компоненту. Ненаправленный граф может быть разложен на рёберно непересекающиеся циклы, если и только если все его вершины имеют чётную степень. Таким образом, граф имеет эйлеров цикл, если и только если он может быть разложен на рёберно непересекающиеся циклы и его вершины с ненулевой степенью принадлежат одному связному компоненту. Ненаправленный граф имеет эйлеров путь, если и только если ровно ноль или две вершины имеют нечётную степень, и все его вершины с ненулевой степенью принадлежат одному связному компоненту. Рассмотрим граф, у которого все рёбра принадлежат одному компоненту связности и не более двух вершин имеют нечётную степень. Алгоритм начинается с вершины нечётной степени, или, если в графе нет вершин нечётной степени, он начинается с произвольно выбранной вершины. На каждом шаге он выбирает следующее ребро в пути, удаление которого не разъединит граф, если такое ребро существует. В противном случае он выбирает единственное оставшееся ребро, инцидентное текущей вершине. Затем он переходит к другому концу этого ребра и удаляет его. В конце алгоритма рёбра не остаются, и последовательность выбранных рёбер образует эйлеров цикл, если в графе нет вершин нечётной степени, или эйлеров путь, если есть ровно две вершины нечётной степени. Хотя обход графа в алгоритме Флёри линеен по числу рёбер, необходимо также учитывать сложность обнаружения мостов. Если после удаления каждого ребра повторно запускать алгоритм поиска мостов Таряна за линейное время, временная сложность алгоритма Флёри составит A. Динамический алгоритм поиска мостов позволяет улучшить это до , но это всё ещё значительно медленнее, чем альтернативные алгоритмы.

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

Число эйлеровых циклов в диграфах можно вычислить с помощью так называемой теоремы BEST, названной в честь де Брюйна, ван Аарденне-Эренфеста, Смита и Тютте. Формула утверждает, что число эйлеровых циклов в диграфе является произведением определенных факториалов степеней и числа укорененных арборесценций. Последнее можно вычислить как определитель, используя теорему о матричном дереве, что дает алгоритм полиномиального времени. Теорема BEST впервые была сформулирована в этой форме в "примечании, добавленной после завершения работы" в статье Аарденне-Эренфеста и де Брюйна (1951). Исходное доказательство было биективным и обобщало последовательности де Брюйна. Это вариация более раннего результата Смита и Тютте (1941). Подсчет числа эйлеровых циклов на неориентированных графах значительно сложнее. Эта задача известна как #P-полная. В позитивном ключе, подход Монте-Карло на основе цепей Маркова, использующий преобразования Коцига (введенные Антоном Коцигом в 1968 году), предположительно дает точное приближение для числа эйлеровых циклов в графе, хотя на данный момент доказательств этого факта нет (даже для графов ограниченной степени).

Приложения

Эйлеровы пути используются в биоинформатике для восстановления последовательности ДНК по её фрагментам. Они также применяются при проектировании CMOS-схем для нахождения оптимальной последовательности размещения логических элементов. Существуют алгоритмы обработки деревьев, основанные на эйлеровом обходе дерева (где каждое ребро рассматривается как пара дуг). Последовательности де Брюйна можно построить как эйлеровы пути в графах де Брюйна.

В бесконечных графах

В бесконечном графе понятие, соответствующее эйлерову пути или эйлерову циклу, – это эйлерова линия, двунаправленно бесконечный путь, проходящий по всем рёбрам графа. Для существования такого пути недостаточно, чтобы граф был связным и все степени вершин были чётными; например, показанный бесконечный граф Кэли, в котором все степени вершин равны четырём, не имеет эйлеровой линии. Бесконечные графы, содержащие эйлеровы линии, были охарактеризованы следующим образом: для бесконечного графа или мультиграфа G наличие эйлеровой линии необходимо и достаточно, чтобы выполнялись все следующие условия: G связен. G имеет счётные множества вершин и рёбер. G не содержит вершин (конечной) нечётной степени. Удаление любого конечного подграфа S из G оставляет в оставшемся графе не более двух бесконечных связных компонент, и если S имеет чётную степень в каждой своей вершине, то удаление S оставляет ровно одну бесконечную связную компоненту.

Ненаправленные эйлеровские графики

Эйлер установил необходимое условие для того, чтобы конечный граф был эйлеровым: все его вершины должны иметь чётную степень. Иерхольцер доказал, что это условие также достаточно, в статье, опубликованной в 1873 году. Это приводит к следующему необходимому и достаточному условию эйлеровости конечного графа: Ненаправленный связный конечный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины чётна. Веблен в 1912 году доказал следующий результат: Ненаправленный связный граф является эйлеровым тогда и только тогда, когда он представляет собой непересекающееся объединение циклов. Иерхольцер разработал алгоритм, работающий за линейное время, для построения эйлерова обхода в ненаправленном графе.

Направленные эйлеровские графики

Возможно построить ориентированный граф, у которого все исходящие степени чётны, но который не является эйлеровым. Поскольку эйлеров цикл покидает вершину столько же раз, сколько и входит в неё, необходимым условием существования эйлерова цикла является равенство входящей и исходящей степеней в каждой вершине. Очевидно, также необходима связность. Кёниг доказал, что эти условия также достаточны. То есть, ориентированный граф является эйлеровым тогда и только тогда, когда он связен и входящая и исходящая степени равны в каждой вершине. В этой теореме не имеет значения, понимается под "связным" "слабая связность" или "сильная связность", поскольку для эйлеровых графов они эквивалентны. Линейный по времени алгоритм Иерхольцера для построения эйлерова тура также применим к ориентированным графам.

Смешанные графы Эйлера

Все смешанные графы, которые одновременно чётные и симметричные, гарантированно являются эйлеровыми. Однако это не является необходимым условием, поскольку можно построить несимметричный чётный граф, который является эйлеровым. Форд и Фулкерсон в 1962 году в своей книге «Потоки в сетях» доказали необходимое и достаточное условие для того, чтобы граф был эйлеровым, а именно, что каждая вершина должна быть чётной и удовлетворять условию баланса, то есть для любого подмножества вершин S разность между количеством дуг, выходящих из S, и количеством дуг, входящих в S, должна быть меньше или равна количеству рёбер, инцидентных S. Проверка того, является ли смешанный граф эйлеровым, сложнее, чем проверка эйлеровости неориентированного или ориентированного графа, поскольку условие баланса множества относится к каждому возможному подмножеству вершин.