Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

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

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

Как появились эйлеровы схемы

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

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

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

eyJpZCI6ImVkNGY4MDk5MWE1MzBmYThmMjBlMmVkNzEwMTc0MTNmLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=ab912540c2c4a05bb59e7566931291ff32db01d1d9738211822d2d32daaf2b54

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

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

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

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

Что такое эйлерова цепь

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

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

eyJpZCI6IjU3MGM3NWIzNmIzOGQyY2ZkYzRhM2IxNmU3NGMyM2MzLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=65a031358cfe96454ad60d99b695a58183383dfe6ddcf280e3ad194b345c4e08

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

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

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

Доказательство теоремы

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

Если — граф, в котором у каждой вершины степень не менее двух, то содержит цикл

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

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

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

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

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

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

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

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

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

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

eyJpZCI6IjdlNWUzYjU4MDk4YjJiZmNiYmQwZWI0ZmZiODUwMzYxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=297eda7a0b4608e112eea65de80877bbfb0c97e08a2af7abfe36e1599b1b4945

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

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

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

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

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

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

Выводы

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


Самостоятельная работа

Задача №1

Какие графы на рисунке ниже считаются графами Эйлера?

eyJpZCI6ImE5NDNmYjBmZjEwZjIyMzkwNTJiNjU3YmRjNDQ0YmRmLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=6bddb314bd3ad4f01ee64a7dd108add39a831b5546325da0de68729d7fa291f4
Нажмите, чтобы увидеть ответ

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



Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

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