Эйлеров путь
Также: Eulerian path · Eulerian circuit · эйлеров цикл · алгоритм Хирхольцера · Hierholzer's algorithm · задача почтальона · route inspection problem · граф де Брёйна · de Bruijn graph
Маршрут, который проходит по каждому ребру графа ровно один раз. Есть ли он, решает одно правило — сколько вершин с нечётным числом рёбер. Найти его помогает алгоритм Хирхольцера: идти, пока идётся, а застряв — вставлять пропущенные петли в маршрут. Линейное время, и на нём держатся уборка улиц и сборка геномов.
Зимней ночью снегоуборочная машина выезжает из гаража, должна пройти каждую улицу своего района и вернуться. Каждая улица, которую она проходит второй раз, — пустой пробег: топливо и время, пока город ждёт. Можно ли обойтись без повторов? Почти никогда — зато есть точный ответ, сколько придётся повторить. Ниже квадрат 800 на 800 метров вокруг площади Республики: 47 перекрёстков и 5,5 км улиц. Нажмите «Проехать» — машина пройдёт самый короткий из возможных маршрутов.
Красными кольцами отмечены 22 перекрёстка, где сходится нечётное число улиц. Это они заставляют ездить по второму разу: 1,69 км, полосы под улицами. Меньше повторить нельзя, и маршрут длиной 7,19 км не улучшить. Переключите на «жадные пары» — правило «соединять ближайшие перекрёстки» даёт 1,94 км. Закройте какую-нибудь улицу: у её концов поменяется чётность, а вместе с ней и план. Нажмите за квадратом, чтобы перенести его в другое место города.
Идея
Эйлеров путь — маршрут, который проходит по каждому ребру ровно один раз; если он кончается там, где начался, это эйлеров цикл. Есть ли такой маршрут, видно без всякого поиска. Проезжая перекрёсток насквозь, мы тратим две его улицы: одну на въезд, другую на выезд. Поэтому у перекрёстка, где маршрут не начинается и не кончается, улиц чётное число. Связный граф, где все степени чётные, обходится циклом; где нечётных вершин ровно две — путём из одной в другую; где их больше — никак. Это правило Эйлера, и его доказательство в обе стороны разобрано в «Царице наук», в главе о графах.
Правило говорит, есть ли маршрут, но не строит его. А если просто ехать по непройденным улицам, пока можно, легко застрять: вернуться в начало, когда целые куски графа ещё не тронуты.
Идите по непройденным рёбрам, пока идётся. Застрять можно только в конце маршрута — там, где у вершины кончились рёбра. Отступайте по своему следу, складывая вершины в ответ с конца, пока не встретите вершину, у которой остались непройденные рёбра. От неё начните новую петлю: она обязательно вернётся в ту же вершину и встанет в ответе как раз на её место. Это алгоритм Хирхольцера, и всю склейку петель делает обычный стек.
Как это работает по шагам
Цветок из трёх лепестков: в центре вершина O с шестью рёбрами, у остальных по два. Нечётных вершин нет — значит, будет цикл. Числа у вершин — их степени, красным — нечётные. Пунктиром показаны три ребра внешнего кольца: нажмите на любое, чтобы добавить его, и посмотрите, как меняются степени и что говорит правило Эйлера.
Поиск начинает с A, идёт в O, потом в B — и возвращается в A. У A рёбер больше нет: тупик. Без стека здесь пришлось бы сдаться, ведь два лепестка не тронуты. Хирхольцер отступает: A уходит в ответ последней вершиной маршрута, за ней B, а у O находятся непройденные рёбра. Отсюда начинается петля O → C → D → O → E → F → O, она приходит обратно в O и встаёт в маршрут между O и B. Числа на рёбрах — их места в готовом маршруте: A O C D O E F O B A.
Добавьте ребро B–C: у B и C станет по три ребра, и цикл превратится в путь из одной нечётной вершины в другую. Начать его можно только в нечётной вершине — нажмите на любую другую, и сцена это скажет. Добавьте ещё D–E — нечётных станет четыре, и одного росчерка уже не хватит. Понадобится два: каждый росчерк обслуживает не больше двух нечётных вершин, своё начало и свой конец.
Почему маршрут правильный
Пусть граф связен, нечётных вершин в нём нет или их ровно две, и поиск начат в нечётной вершине, если она есть. Тогда вершины, которые алгоритм Хирхольцера выталкивает из стека, прочитанные задом наперёд, образуют эйлеров путь (или цикл).
Каждая вершина кладётся в стек вместе с ребром, по которому в неё пришли, а каждое ребро проходится ровно один раз: пройденные отмечены. Поэтому в стеке в любой момент лежит путь по рёбрам из начальной вершины. Вершина уходит из стека, только когда у неё не осталось непройденных рёбер, и уходит вместе со своим ребром. Значит, вытолкнутые вершины, прочитанные с конца, тоже идут по рёбрам — по тем самым, по которым их когда-то положили, — и каждое ребро встречается в этом пути ровно раз.
Осталось убедиться, что непройденных рёбер к концу не останется. Если бы такое осталось, по связности нашлось бы непройденное ребро у вершины, которая побывала в стеке. Но вершину выталкивают, лишь когда все её рёбра пройдены, а поиск кончается пустым стеком. Противоречие.
Где именно поиск застревает в первый раз? В каждую вершину, кроме начальной и второй нечётной, мы входим и выходим парами рёбер, и раз уж вошли — ребро для выхода найдётся. Поэтому первый тупик — это конец маршрута: при нечётных вершинах — вторая нечётная, при чётных — сама начальная. Начните поиск с чётной вершины, когда нечётных две, и первый тупик придётся на нечётную вершину в середине «маршрута», а склеенная последовательность уже не будет путём. Поэтому листинг начинает с нечётной вершины, если она есть.
Ловушка: «не сжигай мосты»
У Хирхольцера есть старший соперник — правило Флёри 1883 года. Идите по рёбрам, стирая их за собой, и никогда не выбирайте мост оставшегося графа, если есть другая дорога: сжёгши мост, вы отрежете себе путь к ещё не пройденной части. Правило верное и никогда не застревает, но на каждой развилке приходится проверять, не мост ли ребро, а это обход графа. Вместо O(E) выходит O(E²). Хирхольцер не проверяет ничего: он позволяет себе застрять и потом чинит маршрут склейкой, и это дешевле, чем всё время осторожничать. Замер — в разделе о сложности.
Вторая ловушка — несвязный граф с правильными степенями, например два отдельных треугольника. Правило Эйлера требует связности, и программа обязана её проверить. В листинге проверка бесплатная: если в ответе меньше вершин, чем рёбер плюс один, часть рёбер так и не нашлась.
Код
Граф хранится списками смежности с номерами рёбер. У каждой вершины — указатель на первое ребро, которое, может быть, ещё не пройдено. Ребро неориентированного графа лежит в двух списках, и, пройдя его с одного конца, мы отмечаем его, чтобы второй конец его пропустил.
Указатель вершины только растёт, и каждое ребро пропускается не больше двух раз — по разу с каждого конца. Поэтому весь поиск — O(V + E), без всяких проверок мостов. Семь мостов Эйлера программа разбирает одной строчкой: четыре нечётных куска суши, маршрута нет.
Когда без повторов не обойтись: задача почтальона
В городе нечётные перекрёстки на каждом шагу: любой Т-образный перекрёсток и любой тупик. Значит, обойти район ровно по разу не выйдет, и вопрос другой — какие улицы проехать дважды, чтобы лишний путь был наименьшим. Это задача почтальона: в 1960 году её поставил и предложил способ решения Гуань Мэйгу, думая о почтальоне, которому надо пройти каждую улицу своего участка.
Кратчайший замкнутый маршрут, проходящий каждое ребро связного графа хотя бы раз, длиннее суммы всех рёбер ровно на вес наилучшего разбиения нечётных вершин на пары, где вес пары — кратчайшее расстояние между её вершинами.
Пусть маршрут есть. Запишем, сколько раз он проходит каждое ребро, и выбросим по одному проходу каждого ребра — останутся повторы. Маршрут замкнут, поэтому вместе с повторами у каждой вершины чётное число проходов. Значит, у нечётной вершины повторов нечётное число, у чётной — чётное. Такие повторы распадаются на пути, каждый из которых соединяет две нечётные вершины, и на циклы; каждый путь не короче кратчайшего расстояния между своими концами. Поэтому повторов не меньше, чем вес наилучшего разбиения на пары. Обратно: продублируем кратчайшие пути наилучшего разбиения — у всех вершин станут чётные степени, и эйлеров цикл получившегося графа проходит каждое ребро хотя бы раз ровно с такими повторами.
Отсюда план: Дейкстрой найти расстояния между нечётными перекрёстками, разбить их на пары с наименьшей суммой, продублировать пути между парами и пустить Хирхольцера по удвоенному графу. Жадно, ближайшие сначала, пары выбирать нельзя: в сцене жадный выбор проигрывает 0,25 км из 1,69. Для 22 перекрёстков листинг перебирает разбиения динамикой по маскам: состояние — множество уже спаренных перекрёстков, и самый младший свободный всегда спаривается первым, чтобы одно и то же разбиение не собиралось в разном порядке. Из 4 194 304 возможных масок при таком правиле встречаются только 28 656.
odd crossings: 22 driven twice, pairs taken greedily: 1.94 km driven twice, best pairing: 1.69 km (28656 states of the table out of 4194304 masks) route: 82 pieces in a row, 7.19 km, 26 of them a second time
Маски годятся на два-три десятка нечётных перекрёстков. Для целого города наилучшие пары ищут паросочетанием, только не двудольным, а в произвольном графе — алгоритмом Джека Эдмондса; его быстрые реализации работают за O(n³). Так в 1973 году задачу почтальона и решили за полиномиальное время Эдмондс и Эллис Джонсон. Если все улицы односторонние, вместо пар нужен поток минимальной стоимости, и задача тоже решается быстро. А если односторонние лишь некоторые, как в настоящем городе, она NP-трудна — это доказал Христос Пападимитриу в 1976 году.
Сборка генома
Самые распространённые секвенаторы не читают молекулу ДНК от начала до конца. Много её копий режут на короткие куски, по сотне-другой букв, каждый кусок читается по отдельности, и собирать геном приходится, как разорванную газету. Можно сделать куски вершинами, а наложения кусков — рёбрами и искать путь через все вершины. Но это гамильтонов путь, задача NP-трудная. В 2001 году Павел Певзнер, Хайсюй Тан и Майкл Уотерман предложили смотреть наоборот (идея восходит к работе Раманы Идури и Уотермана 1995 года). Разрежем все прочитанные куски на перекрывающиеся кусочки длины k — k-меры. Вершины — строки длины k − 1, и каждый k-мер — ребро от своего начала к своему концу: GATTA ведёт из GATT в ATTA. Это граф де Брёйна, и геном — путь, проходящий каждое ребро ровно раз. Эйлеров.
Ориентированный вариант правила Эйлера такой (граф, как и прежде, связен): у каждой вершины число входящих рёбер равно числу исходящих — тогда есть цикл; у одной исходящих на одно больше, у другой на одно меньше — тогда путь между ними. Кольцевой геном даёт ровно первый случай. Ниже — фаг φX174, первый геном на основе ДНК, прочитанный целиком (Фредерик Сэнгер с соавторами, 1977): кольцо из 5386 букв. Его k-меры перемешаны, а потом собраны алгоритмом Хирхольцера.
При k = 8 сборка проходит каждый 8-мер ровно столько раз, сколько он встречается в геноме, но кольцо получается другое: оно расходится с настоящим уже после девятой буквы. Виноваты повторы. 965 разных 7-меров встречаются в геноме больше одного раза, и в каждом таком месте эйлеров цикл волен свернуть в любую из нескольких дорог. С ростом k повторов становится меньше: при k = 13 их всего два, но и их хватает, чтобы куски встали в другом порядке. С k = 14 ни одна строка длины 13 не повторяется, каждая вершина графа имеет по одному входу и выходу, граф — одно кольцо, и сборка однозначна. Самый длинный повтор в φX174 — 12 букв, и чтобы его перешагнуть, кусок должен быть хотя бы на две буквы длиннее. Найти длину самого длинного повтора заранее помогает суффиксный массив.
Настоящие ассемблеры — Velvet, SPAdes и другие — строят граф де Брёйна из k-меров прочитанных кусков, но эйлеров путь целиком не ищут. Прочтения содержат ошибки, часть генома покрыта плохо, повторы длиннее k всё равно путают порядок. Поэтому граф сначала чистят от ошибок, а потом выдают однозначные участки между развилками — контиги, — оставляя развилки нераспутанными.
Сколько это стоит
Каждое ребро проходится один раз и попадает в стек один раз. Указатель на следующее ребро у каждой вершины только растёт, а каждое ребро он пропускает не больше двух раз — по разу с каждого конца. Итого O(V + E) времени и O(V + E) памяти на списки смежности, отметки и стек. Ориентированный вариант ещё проще: ребро видно только из своего начала, и отметки «пройдено» не нужны. Правило Флёри на каждой развилке проверяет мост обходом оставшегося графа, и замер на решётке, свёрнутой в тор, это хорошо показывает:
Наклон Флёри около двух: удвоили граф — время выросло вчетверо. Хирхольцер растёт линейно. На трёх тысячах рёбер Флёри на Python медленнее в пятьсот раз, и разрыв растёт вместе с графом. В задаче почтальона самое дорогое — не эйлеров цикл, а поиск пар: расстояния между нечётными вершинами и само разбиение на пары.
Где работает
Маршруты по улицам. Когда обслуживать надо не точки, а дороги, — уборка снега, полив, вывоз мусора, обход почтальона, проверка разметки, — задача сводится к эйлеровым путям. В жизни к ней добавляются односторонние улицы, развороты, вместимость машины, несколько машин, и из чистой задачи почтальона вырастает целое семейство задач о маршрутах по дугам. Чистая задача — простейшая из них, и её ответ служит нижней оценкой для всех остальных: дополнительные условия маршрут не укорачивают.
Сборка последовательностей. Граф де Брёйна — рабочая лошадь сборки геномов по коротким прочтениям: SPAdes, Velvet и многие другие строят именно его.
Строки, где встречается всё. Кратчайшая строка из цифр, в которой встречается каждый код длины n, — эйлеров цикл в графе де Брёйна, где вершины — строки длины n − 1. Её длина 10n + n − 1 вместо n·10n при переборе кодов по одному. Об этом первая задача ниже.
Одним росчерком. Перо плоттера, лазер гравёра, резак станка тратят время на холостые перелёты между линиями. Чертёж — граф, и наименьшее число непрерывных проходов — половина числа нечётных вершин, если они есть, и один проход, если их нет. А полный набор домино из 28 костей можно выложить в кольцо: это эйлеров цикл в графе, где семь вершин — числа от нуля до шести, каждая пара соединена ребром, и у каждого числа есть ещё петля-дубль, так что все степени чётные.
История
В 1735 году Леонард Эйлер решил задачу о семи мостах — можно ли обойти город, пройдя по каждому мосту ровно один раз, — и заодно доказал, что у графа с нечётными вершинами больше двух обхода нет. Эта история подробно рассказана в главе о графах «Царицы наук». Обратное утверждение — что при чётных степенях обход есть — Эйлер считал ясным и не доказывал.
Доказал его Карл Хирхольцер — тем самым способом, что в этой статье: идти, пока идётся, а потом вклеивать в маршрут пропущенные циклы. Незадолго до смерти он рассказал о доказательстве коллегам; Хирхольцер умер в 1871 году, тридцати лет, и статья вышла уже после этого, в 1873 году, вместе с именем Кристиана Винера. Правило «не сжигай мосты» опубликовал Флёри в 1883 году.
Строки, содержащие все коды, считали ещё в 1894 году: тогда Камиль Флай Сент-Мари нашёл, сколько их бывает для двоичного алфавита. В 1934 году Монро Мартин дал простое правило, строящее такую строку для любого алфавита, а в 1946 году задачу заново решил Николас де Брёйн, и граф носит его имя; позже он сам признал первенство Флая Сент-Мари. Задачу почтальона в 1960 году поставил Гуань Мэйгу, а полиномиальное решение через паросочетания дали Джек Эдмондс и Эллис Джонсон в 1973 году. Графы де Брёйна пришли в сборку геномов в 1995 году у Идури и Уотермана и стали её основой после работы Певзнера, Тана и Уотермана 2001 года.
Задачи
В первой задаче нужно найти кратчайшую последовательность нажатий, перебирающую все коды кнопочного замка, — то есть построить строку де Брёйна. Во второй — собрать кольцевой геном по перемешанным k-мерам, и среди тестов настоящие φX174 и митохондрия человека. В третьей снегоуборщик выходит на улицы Алматы: сколько метров придётся проехать, чтобы пройти каждую улицу района и вернуться.
Забытый код Кольцо из кусков СнегоуборщикДанные: Дороги Алматы © участники OpenStreetMap, ODbL Геномы фагов λ и φX174 и митохондрии человека: NCBI RefSeq NC_001416.1, NC_001422.1, NC_012920.1