Эйлеровы графы
Он имеет эйлеров путь ( x 4 , x 1 , x 3 , x 2 , x 1 , x 5 , x 3 ).
Определение 2. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа и проходящий через каждое по одному разу.
Определение 3. Граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Пример 2. Рассмотрим граф
Данный граф является эйлеровым, так как он имеет эйлеров цикл ( x 2 , x 5 , x 4 , x 1 , x 2 , x 3 , x 4 , x 2 ).
Связность следует из определения эйлерового графа. Эйлеров цикл содержит каждое ребро и притом только один раз. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: количество входов в вершину и количество выходов из вершины.
Теорема 2. Если граф G ( X , T ) связный и все его вершины четны, то он обладает эйлеровым циклом.
Теорема 3. Если граф G ( X , T ) обладает эйлеровым путем с концами А и В, то граф G ( X , T ) связный и А и В его единственные нечетные вершины.
Если путь начинается в А и кончается в В, то А и В нечетные вершины, даже если путь неоднократно проходил через них. В любую другую вершину путь должен привести и вывести из нее, т.е. остальные вершины четные.
Теорема 4. Если граф G ( X , T ) связный и А и В его единственные нечетные вершины, то граф обладает эйлеровым путем с концами А и В.
Теорема 5. Если граф G ( X , T ) связный, то можно построить цикличный маршрут, содержащий все ребра в точности 2 раза, по одному в каждом направлении.
Эйлеровы схемы — Теория графов
В этом уроке разберем, что такое эйлеровые циклы, с помощью которых можно совершить круговое путешествие по графу и посетить каждое ребро только один раз.
Как появились эйлеровы схемы
Традиционно первой проблемой в теории графов считается проблема кенигсбергских мостов. Ниже показан эскиз города Кенигсберг и его семи мостов.
В начале 1700-х годов жители задались вопросом, можно ли совершить круговую поездку по городу, пересекая каждый мост ровно один раз. Мэр отправил письмо с вопросом об этой проблеме известному математику Леонарду Эйлеру. И он решил эту проблему с помощью графа.
Эйлер представил каждую из четырех областей суши в виде графа, где мосты соответствуют ребрам:
Такой график сохраняет только самую важную информацию с карты. Точные детали формы регионов не важны. Когда Эйлер посмотрел на вершины, он определил, что путешествие невозможно.
Почему так? Чтобы разобраться в этом, вспомним определение инцидентных ребер — это когда вершина
является началом или концом какого-то ребра. Две вершины называются инцидентными, если у них есть общее ребро.
Вернемся к графу с мостами. Если начать движение с одной из его вершин, придется использовать одно из ее инцидентных ребер, чтобы покинуть эту вершину. Позже придется использовать еще одно из инцидентных ребер, чтобы вернуться в вершину. В итоге мы будем использовать последнее инцидентное ребро, чтобы покинуть вершину. Нам нужно закончить там, где начали, но из-за инцидентных ребер это невозможно.
Дело в том, что одна из этих вершин имеет степень
. Это не начальная точка, поэтому мы застрянем в этой вершине и не сможем покинуть ее.
Что такое эйлерова цепь
Эйлерова цепь или эйлерова экскурсия в графе — это чередующаяся последовательность вершин и ребер в графе. Она начинается и заканчивается одной и той же вершиной и использует каждое ребро ровно один раз. Граф с эйлеровой цепью называется эйлеровым.
Так выглядит эйлерова схема в графе:
Здесь ребра обозначены в порядке их посещения. Ни одно ребро не посещается дважды, и мы заканчиваем там, где начали.
Если у графа есть хоть одна нечетная вершина, то у него не может быть эйлеровой схемы. Верно и обратное — если у связного графа нет нечетных вершин, то у него есть эйлеровая схема.
Доказательство этого обычно проводится индуктивно — то есть от частных фактов к установлению общих положений. Для этого нужно выдернуть цикл из графа и объединить эйлеровы схемы из оставшихся частей в одну большую схему. При этом использовать удаленный цикл. В этом случае не будет цикла, который нельзя удалить.
Доказательство теоремы
Чтобы доказать эйлерову цепь, сперва сформулируем и докажем такую теорему:
— граф, в котором у каждой вершины степень не менее двух, то
Возьмем самый длинный путь
и рассмотрим одну из его конечных точек
. Эта вершина примыкает к предпоследней вершине пути. Так как у
степень не меньше двух, то должно существовать еще одно ребро, инцидентное ей.
Если другая конечная точка этого ребра не находится на пути, то мы могли бы использовать, чтобы построить более длинный путь, чем
. Это невозможно, поэтому другая конечная точка ребра должна быть вершиной
пути. Это создает цикл от
У этой теоремы много применений. Здесь мы используем ее для доказательства теоремы об эйлеровых схемах. В доказательстве мы будем использовать термин четный граф для обозначения графа, в котором степень каждой вершины четная.
Докажем еще следующую теорему:
Связный граф будет эйлеровым, когда у каждой вершины четная степень
есть эйлерова цепь, то эта цепь должна входить и выходить из каждой вершины. Такое возможно несколько раз, если добавлять
к своей степени при каждом проходе. Поскольку эта цепь учитывает все ребра графа, каждая вершина должна иметь четную степень.
Докажем третью теорему — обратную импликацию индукцией по числу ребер. Базовый случай
ребер тривиально верен — это значит, что в графе есть только одна вершина и нет ребра.
Предположим, что утверждение справедливо для всех связных четных графов с e ребрами или меньше, и рассмотрим связный четный граф
связный и четный, у каждой вершины степень не менее двух, поэтому по Теореме у
есть цикл. Удалим ребра цикла из
Степень каждой вершины в уменьшенном графе будет по-прежнему четной, поскольку мы удаляем ровно два ребра из каждой вершины цикла. По гипотезе индукции, каждая из компонент редуцированного графа имеет эйлерову схему.
Эти схемы можно объединить с циклом, чтобы создать эйлеровы схемы в исходном графе путем обхода цикла. Когда мы достигаем вершины, которая является частью компоненты редуцированного графа, мы обходим ее по эйлеровой схеме этой компоненты и возвращаемся к вершине на цикле:
Чтобы получить эйлерову схему всего графа, начнем прослеживать цикл от
. Далее проследим эйлерову схему, которая существует в правой компоненте графа, начинается и заканчивается в
После этого проследим цикл от
мы следуем эйлеровой схеме, которая существует на левой компоненте графа, начинается и заканчивается в точке
. В конце мы возвращаемся по циклу от
, и завершаем эйлерову схему всего графа. Значит, теорема доказана.
Мы предполагаем, что можем работать с небольшими случаями и использовать, чтобы строить более крупные случаи. Большая часть работы заключается в описании того, как использовать малые случаи для получения больших.
Алгоритм Флери
Есть еще один простой способ найти эйлерову цепь — алгоритм Флери. Разберем, как он работает.
Можно начинать с любого места. В каждой вершине выбираем ребро для добавления в тур, а затем удаляем его из графа. Мы можем выбрать это ребро как угодно. При этом мы никогда не выбираем ребро с разрезом, если есть ребро без разреза. Если мы выберем ребро, когда доступно ребро без разреза, это отрежет часть графа, и мы никогда не сможем до него добраться.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
- 130 курсов, 2000+ часов теории
- 1000 практических заданий в браузере
- 360 000 студентов
Наши выпускники работают в компаниях:
Эйлеров цикл
Определение. Эйлеров путь — это путь в графе, проходящий через все его рёбра.
Определение. Эйлеров цикл — это эйлеров путь, являющийся циклом.
Для простоты в обоих случаях будем считать, что граф неориентированный.
Также существует понятие гамильтонова пути и цикла — они посещают все вершины по разу, а не рёбра. Нахождение гамильтонова цикла (задача коммивояжера, англ. travelling salesman problem) — одна из самых известных NP-полных задач, в то время как нахождение эйлерова цика решается за линейное время, и мы сейчас покажем, как.
#Нахождение эйлерова цикла
Теорема. Эйлеров цикл существует тогда и только тогда, когда граф связный и степени всех вершин чётны.
Доказательство. Необходимость показывается так: можно просто взять эйлеров цикл и ориентировать все его ребра в порядке обхода. Тогда из каждой вершины будет выходить столько же рёбер, сколько входить, а значит степень у всех вершин исходного неориентированного графа была четной.
Достаточность докажем конструктивно — предъявим алгоритм нахождения цикла:
Заметим, что:
- выведется последовательность из ровно $(m + 1)$ вершин,
- между каждой соседней парой выписанных вершин есть ребро,
- каждое ребро будет выписано ровно один раз.
Значит, если условия на связность и четность степеней выполняются, то выведенная последовательность вершин действительно будет эйлеровым циклом, причём и в случае ориентированного графа тоже.
#Как удалять ребра
Проще всего хранить все списки смежности в set -подобной структуре и удалять их напрямую там:
Это будет работать за $O(m \log n)$, однако просто заменив дерево на хеш-таблицу ( unordered_set ) можно уменьшить время до линейного.
Также можно использовать более общий подход, который часто применяется в задачах, где ребра как-то изменяются. Создадим отдельный массив с мета-информацией о ребрах и будем хранить в списках смежности не номера вершин, а номера рёбер:
Если добавлять каждое ребро неориентированного графа через add_edge , то у получившейся нумерации ребер будет интересное свойство: чтобы получить обратное к ребру e , нужно вычислить e^1 .
Тогда во время обхода можно поддерживать эту информацию вместо какой-то сложной модификации структур:
Во всех вариантах реализации нужно быть чуть аккуратнее в случае, когда в графе есть петли и кратные ребра. #Эйлеров путь
Поговорим теперь про эйлеровы пути. Может, всё-таки можно что-нибудь сделать, даже если степени не всех вершин чётные?
Заметим, что, так как каждое ребро меняет четность степеней ровно двух вершин, и в пустом графе все степени изначально нулевые, то число вершин с нечетными степенями будет четным.
Если нечетных вершин ровно две, то можно сделать следующее: соединить их ребром, построить эйлеров цикл (ведь теперь степени всех вершин четные), а затем удалить это ребро из цикла. Если правильно сдвинуть этот цикл, мы получили эйлеров путь.
Альтернативно, можно просто запустить обход из одной из нечетных вершин и получить такой же результат.
Если нечетных вершин больше двух, то мы уже построить эйлеров путь не сможем, потому что любой эйлеров путь входит или покидает каждую вершину четное число раз, кроме, возможно двух своих концов.
Следствие. Эйлеров путь существует тогда и только тогда, когда граф связен и количество вершин с нечётными степенями не превосходит 2.
Упражнение. Дан связный неориентированный граф. Требуется покрыть его ребра наименьшим количеством непересекающихся путей. Асимптотика $O(n + m)$.
Упражнение. Сформулируйте и докажите аналогичные утверждения для случая ориентированного графа.
10. Эйлеровы графы. Условия существования цепи и цикла. Гамильтоновы цепи и циклы.
Эйлеров граф — это граф, в котором существует цикл, содержащий все рёбра графа по одному разу (вершины могут повторяться).
Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Условия существования цепи и цикла.
Лемма 1. Если степень каждой вершины графа G не меньше двух, то граф G содержит цикл.
Теорема Эйлера 2. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четная степень.
Следствие 2.1. Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы.
Следствие 2.2. Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени.
Теорема 3 (алгоритм Флёри). Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:
- стираем ребра по мере их прохождения. И стираем также изолированные вершины, которые при этом образуются;
- на каждом этапе идем по мосту только тогда, когда нет других возможностей.
Любой простой полный граф с нечетным количеством вершин является эйлеровым.
Любой циклический граф является эйлеровым.
Гамильтоновы цепи и циклы.
Гамильтонов цикл — цикл, проходящий ровно один раз через каждую вершину графа G.
Тогда граф G называется гамильтоновым графом.
Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым.
Теорема 4 (Дирарк, 1952).
Если в простом графе G с n>=3 вершинами степень любой вершины v scr37 , то граф G является гамильтоновым.
Любой простой полный граф является гамильтоновым.
Любой циклический граф является гамильтоновым.
Граф, являющийся колесом, является гамильтоновым.