Эйлеровы схемы — Теория графов

Традиционно первой проблемой в теории графов считается проблема кенигсбергских мостов. Ниже показан эскиз города Кенигсберг и его семи мостов.

В начале 1700-х годов жители задались вопросом, можно ли совершить круговую поездку по городу, пересекая каждый мост ровно один раз. Мэр отправил письмо с вопросом об этой проблеме известному математику Леонарду Эйлеру. И он решил эту проблему с помощью графа.

Эйлер представил каждую из четырех областей суши в виде графа, где мосты соответствуют ребрам:

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

Почему так? Чтобы разобраться в этом, вспомним определение инцидентных ребер — это когда вершина является началом или концом какого-то ребра. Две вершины называются инцидентными, если у них есть общее ребро.

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

Дело в том, что одна из этих вершин имеет степень . Это не начальная точка, поэтому мы застрянем в этой вершине и не сможем покинуть ее.

Эйлерова цепь или эйлерова экскурсия в графе — это чередующаяся последовательность вершин и ребер в графе. Она начинается и заканчивается одной и той же вершиной и использует каждое ребро ровно один раз. Граф с эйлеровой цепью называется эйлеровым.

Так выглядит эйлерова схема в графе:

Здесь ребра обозначены в порядке их посещения. Ни одно ребро не посещается дважды, и мы заканчиваем там, где начали.

Если у графа есть хоть одна нечетная вершина, то у него не может быть эйлеровой схемы. Верно и обратное — если у связного графа нет нечетных вершин, то у него есть эйлеровая схема.

Доказательство этого обычно проводится индуктивно — то есть от частных фактов к установлению общих положений. Для этого нужно выдернуть цикл из графа и объединить эйлеровы схемы из оставшихся частей в одну большую схему. При этом использовать удаленный цикл. В этом случае не будет цикла, который нельзя удалить.

Чтобы доказать эйлерову цепь, сперва сформулируем и докажем такую теорему:

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

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

У этой теоремы много применений. Здесь мы используем ее для доказательства теоремы об эйлеровых схемах. В доказательстве мы будем использовать термин четный граф для обозначения графа, в котором степень каждой вершины четная.

Докажем еще следующую теорему:

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

Докажем третью теорему — обратную импликацию индукцией по числу ребер. Базовый случай ребер тривиально верен — это значит, что в графе есть только одна вершина и нет ребра.

Предположим, что утверждение справедливо для всех связных четных графов с e ребрами или меньше, и рассмотрим связный четный граф с ребром. Поскольку связный и четный, у каждой вершины степень не менее двух, поэтому по Теореме у есть цикл. Удалим ребра цикла из .

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

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

Чтобы получить эйлерову схему всего графа, начнем прослеживать цикл от до . Далее проследим эйлерову схему, которая существует в правой компоненте графа, начинается и заканчивается в .

После этого проследим цикл от до , от до . В точке мы следуем эйлеровой схеме, которая существует на левой компоненте графа, начинается и заканчивается в точке . В конце мы возвращаемся по циклу от до , и завершаем эйлерову схему всего графа. Значит, теорема доказана.

Мы предполагаем, что можем работать с небольшими случаями и использовать, чтобы строить более крупные случаи. Большая часть работы заключается в описании того, как использовать малые случаи для получения больших.

Есть еще один простой способ найти эйлерову цепь — алгоритм Флери. Разберем, как он работает.

Можно начинать с любого места. В каждой вершине выбираем ребро для добавления в тур, а затем удаляем его из графа. Мы можем выбрать это ребро как угодно. При этом мы никогда не выбираем ребро с разрезом, если есть ребро без разреза. Если мы выберем ребро, когда доступно ребро без разреза, это отрежет часть графа, и мы никогда не сможем до него добраться.

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