Эйлеровы пути и циклы

Некоторые фигуры можно нарисовать одним росчерком, не отрывая карандаша и не проводя ни одну линию дважды, а другие — нет, сколько ни пробуй. Пробовать и не нужно: сосчитайте линии в каждом углу. Если не больше двух углов имеют нечётное число линий, фигуру нарисовать можно, и именно в этих углах росчерк должен начаться и закончиться. Леонард Эйлер нашёл это правило в 1736 году и положил им начало теории графов.

Семь мостов Кёнигсберга в виде графа: четыре участка суши как вершины, у всех четырёх нечётное число мостов, по обоим берегам реки
Семь мостов Кёнигсберга в виде графа: четыре участка суши как вершины, у всех четырёх нечётное число мостов, по обоим берегам реки

Семь мостов Кёнигсберга

Прусский город Кёнигсберг, нынешний Калининград, лежал на обоих берегах реки Прегель и на двух островах в ней — Кнайпхофе и Ломзе. Семь мостов связывали четыре части: два с Кнайпхофа на каждый берег, один между островами и по одному с Ломзе на каждый берег. Горожане гадали, может ли прогулка пройти по каждому мосту ровно один раз. Эйлер ответил в работе, представленной академии в Санкт-Петербурге в 1735 году и напечатанной в 1741-м: не может. Его решающий шаг — отбросить всё, кроме частей города и мостов между ними, а это и есть граф: вершина для каждого участка суши и ребро для каждого моста, причём там, где два моста соединяют одни и те же места, рёбер два.

Портрет Леонарда Эйлера
Портрет Леонарда Эйлера
Portrait of Leonhard Euler
Portrait of Leonhard Euler

Правило степеней

Степень вершины — это число рёбер при ней. Росчерк, проходящий через вершину, входит по одному ребру и выходит по другому, то есть расходует рёбра этой вершины парами. Только первая и последняя вершины росчерка могут сохранить ребро без пары. Поэтому вершина нечётной степени обязана быть началом или концом росчерка. У Кнайпхофа было пять мостов, у трёх других частей — по три: четыре нечётные вершины, на две больше нужного. В общем случае у связного графа есть эйлеров цикл — росчерк, заканчивающийся там, где начался, — когда все степени чётные, и эйлеров путь, когда ровно две степени нечётные, из одной в другую. Число нечётных вершин никогда не равно единице или другому нечётному числу: каждое ребро добавляет 2 к сумме всех степеней, поэтому сумма чётная. Это заметил и Эйлер, а сегодня это называют леммой о рукопожатиях.

Почему правила достаточно

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

Алгоритм Флёри: не сжигайте мосты

Росчерк может не удаться даже на фигуре, которую нарисовать можно. Возьмите два треугольника, соединённых одним ребром, и начните с угла первого: если перейти ко второму треугольнику до того, как закончен первый, вернуться уже не удастся. Соединяющее ребро — мост: убрав его, фигуру разделишь надвое. Алгоритм Флёри 1883 года даёт одно правило: в каждой вершине берите ребро, которое не является мостом для оставшихся рёбер, если только другого нет. Следуя ему, вы всегда дойдёте до конца. Проверка на мост требует времени, поэтому алгоритм Флёри медленнее алгоритма Хирхольцера, зато именно ему можно следовать с карандашом, и подсказка в приложении использует его.

Как исправить фигуру

Фигура с k нечётными вершинами требует k/2 росчерков. Чтобы нарисовать её одним, добавьте рёбра, соединяющие нечётные вершины попарно: каждое новое ребро делает две нечётные вершины чётными. После k/2 − 1 рёбер остаются две нечётные вершины и получается путь; после k/2 не остаётся ни одной и получается цикл. Ещё один мост в Кёнигсберге, между любыми двумя из четырёх частей, сделал бы прогулку возможной, а два позволили бы вернуться в начало. История поступила похоже: два моста были потеряны во Второй мировой войне, два заменила современная дорога, и по пяти мостам, стоящим сегодня на старых местах, можно пройти по одному разу — с одного острова на другой.

Как сосчитать способы

Домик Деда Мороза — квадрат с обеими диагоналями и крышей — это немецкая детская версия задачи: в «Das ist das Haus vom Ni-ko-laus» восемь слогов, по одному на линию. Два его нижних угла — единственные нечётные вершины, и из каждого есть ровно 44 способа его нарисовать, всего 88. Для ориентированных графов число эйлеровых циклов даёт формула — теорема BEST, названная по именам де Брёйна, ван Арденне-Эренфест, Смита и Татта. Для обычных графов такой формулы не известно, а подсчёт в общем случае считается трудным, поэтому приложение считает небольшие фигуры перебором всех способов, пропуская шаги, которые разрезали бы фигуру надвое.

Где применяются эйлеровы пути

Снегоуборочная машина, подметальная машина или почтальон хотят проехать каждую улицу один раз и вернуться. Если на каждом перекрёстке чётное число улиц, годится эйлеров цикл; иначе часть улиц придётся проехать дважды, и выбор самых дешёвых — задача китайского почтальона, поставленная Мэйгу Гуанем в 1962 году. Перьевой плоттер или лазерный резак экономят время, проводя как можно больше линий без отрыва. При секвенировании генома миллионы коротких фрагментов ДНК собирают, отыскивая эйлеров путь в графе де Брёйна, где каждый фрагмент — ребро. И то же правило подсказывает, какие рисунки в сборнике головоломок стоит пробовать.

Попробуйте сами

Откройте поиск эйлеровых путей, чтобы самому обвести двенадцать фигур — от Кёнигсберга 1736 года и сегодняшнего до звёзд, вложенных квадратов и куба, — или нарисуйте свои, с параллельными рёбрами. Нечётные вершины закрашены, каждая вершина показывает свою степень, а правило степеней под фигурой говорит, что возможно и какие рёбра исправили бы фигуру. Если вы застрянете, приложение скажет, начали ли вы не с той вершины или слишком рано прошли по мосту, и на каком шаге. Подсказка даёт безопасное ребро, а Решить рисует фигуру алгоритмом Флёри, показывая проверку моста, или алгоритмом Хирхольцера, показывая каждую вставку.

Часто задаваемые вопросы

Эйлеров путь — это то же самое, что гамильтонов путь?

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

Работает ли правило степеней, когда две вершины соединены несколькими рёбрами?

Да. Каждое ребро учитывается в степени обоих своих концов, независимо от того, соединяет ли те же две вершины ещё одно ребро. Кёнигсберг — как раз такой мультиграф: Кнайпхоф связан с каждым берегом двумя мостами. Ребро из вершины в неё саму, петля, добавляет к степени 2 и никогда не меняет её чётность.

А как быть с улицами с односторонним движением?

В ориентированном графе у каждого ребра есть направление, и правило сравнивает рёбра, входящие в вершину, с выходящими. Эйлеров цикл есть, когда у каждой вершины входящих рёбер столько же, сколько выходящих, и рёбра держатся вместе; эйлеров путь — когда у одной вершины на одно исходящее ребро больше, у другой на одно входящее больше, а все прочие уравновешены. Тогда путь идёт от первой ко второй.

Может ли существовать фигура ровно с одной нечётной вершиной?

Нет. Сумма степеней всех вершин равна удвоенному числу рёбер, ведь у каждого ребра два конца. Эта сумма чётная, значит, и число нечётных степеней в ней должно быть чётным: 0, 2, 4 и так далее, но никогда 1 или 3.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть поиск эйлеровых путей