Эйлеров граф как определить
Перейти к содержимому

Эйлеров граф как определить

  • автор:

Эйлеров цикл

Определение. Эйлеров путь — это путь в графе, проходящий через все его рёбра.

Определение. Эйлеров цикл — это эйлеров путь, являющийся циклом.

Для простоты в обоих случаях будем считать, что граф неориентированный.

Также существует понятие гамильтонова пути и цикла — они посещают все вершины по разу, а не рёбра. Нахождение гамильтонова цикла (задача коммивояжера, англ. travelling salesman problem) — одна из самых известных NP-полных задач, в то время как нахождение эйлерова цика решается за линейное время, и мы сейчас покажем, как.

#Нахождение эйлерова цикла

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

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

Достаточность докажем конструктивно — предъявим алгоритм нахождения цикла:

    Заметим, что:
  • выведется последовательность из ровно $(m + 1)$ вершин,
  • между каждой соседней парой выписанных вершин есть ребро,
  • каждое ребро будет выписано ровно один раз.

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

#Как удалять ребра

Проще всего хранить все списки смежности в set -подобной структуре и удалять их напрямую там:

 Это будет работать за $O(m \log n)$, однако просто заменив дерево на хеш-таблицу ( unordered_set ) можно уменьшить время до линейного.

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

Если добавлять каждое ребро неориентированного графа через add_edge , то у получившейся нумерации ребер будет интересное свойство: чтобы получить обратное к ребру e , нужно вычислить e^1 .

Тогда во время обхода можно поддерживать эту информацию вместо какой-то сложной модификации структур:

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

#Эйлеров путь

Поговорим теперь про эйлеровы пути. Может, всё-таки можно что-нибудь сделать, даже если степени не всех вершин чётные?

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

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

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

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

Следствие. Эйлеров путь существует тогда и только тогда, когда граф связен и количество вершин с нечётными степенями не превосходит 2.

Упражнение. Дан связный неориентированный граф. Требуется покрыть его ребра наименьшим количеством непересекающихся путей. Асимптотика $O(n + m)$.

Упражнение. Сформулируйте и докажите аналогичные утверждения для случая ориентированного графа.

Эйлеров граф как определить

Задание 4.1. Попробуйте обвести изображения графов на рисунке 22, не отрывая карандаша от бумаги и не проходя уже по обведенному ребру вторично.

рис. 22

Задание по обведению ребер удается выполнить для графов на рисунках 22 (а, б, г, д). Графы на рисунках 22 (в, е) нарисо­вать без отрыва карандаша от бумаги или, не проходя дважды по ребрам, не удастся. В чем секрет? Какие свойства графа повлияли на это? Для удобства введем специальные понятия.
Перед этим рекомендуется вспомнить с учащимися определения пути и цикла.
Эйлеровым путем в графе называется путь, содержащий все ребра графа.
Эйлеровым циклом в графе называется цикл, содержащий все ребра графа
Граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Принято всякую замкнутую линию, если ее можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый уча­сток в точности один раз, называть уникурсальной.
Теперь заглянем в прошлое. Далее показываем презентацию об Эйлере и знаменитой задаче о Кенигсбергских мостах.
Задача 4.1. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (рис. 23, где Л — левый берег, П — правый берег, А и Б — острова). Можно ли, прогуливаясь по берегам реки, пройти по каждому мосту ровно один раз?

Рис. 23 Рис. 24
На рисунке 24 изображен граф, соответствующий задаче о кёнигсбергских мостах. Докажем, что этот граф не является уникурсальным.
Задача 4.2.
Шесть островов на реке в парке «Лотос» соединены мостами.

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


Рис 26 рис. 27
Задача заключается в определении, будет ли граф Gэйлеровым. Найдем необходимые и достаточные условия существования эйлерова цикла.
Теорема 2. (Теорема Эйлера) Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четная.
Доказательство. Необходимость. Пусть G— эйлеров граф. Эйлеров цикл этого графа, проходя через каждую его вершину, входит в нее по одному ребру, а выходит по другому. Это означает, что каждое прохождение вершины по циклу вносит слагаемое 2 в ее степень. По­скольку цикл содержит все ребра графа, то степени всех вершин будут четными.
Достаточность.Предположим, что степени всех вершин связ­ного графа G четные. Начнем цепь G1 из произвольной вершины v1, и будем продлевать ее, выбирая каждый раз новое ребро. Так как степени вершин четные, то, попав в некоторую вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро. Таким образом, построение це­пи Р1обязательно закончится в вершине v1, и Р1будет циклом. Если Р1содержит все ребра графа G, то построен эйлеров цикл. В противном слу­чае, удалив из Gребра Р1, получим граф G2. Так как степени всех вер­шин графов Gи Р1 были четными, то и G2будет обладать этим свойст­вом. В силу связности Gграфы Р1 и G2должны иметь хотя бы одну об­щую вершину v2. Теперь, начиная из v2, построим в G цикл Р2подобно тому, как построили Р1.
Объединим циклы Р1 и Р2следующим образом: пройдем часть Р1 от вершины v1 до вершины v2, затем пройдем цикл Р2, затем — оставшуюся часть Р1 от v2 до v1 (см. рис. 28).

Рис. 28
Если объединенный цикл не эйлеров, то, проделав аналогичные построения, получим еще больший цикл. Поскольку степени вершин во всех графах, составленных из ребер, не попавших в строящийся цикл, четные, и число ребер в этих графах убывает, то процесс закончится по­строением эйлерова цикла. Теорема доказана.
Рассмотрим построенный граф G. В этом графе вершины 2 и 4 имеют нечетную степень, следовательно, граф G не является эйлеровым. Это означает, что желаемую прогулку по мостикам совершить нельзя.
Если же соединить ребром вершины 2 и 4, то степень всех вершин нового графа будет четной, а сам граф будет эйлеровым. Поэтому после постройки моста, соединяющего острова 2 и 4, можно найти маршрут прогулки по мостикам, начинающийся и заканчивающийся в одном мес­те, при котором каждый мостик будет пройден ровно один раз.
Докажем, что имеет место следующая теорема.
Теорема 3. Для уникурсального графа число вершин нечетного индекса равно нулю или двум.
Доказательство. Действительно, если граф уникурсален, то у него есть начало и конец обхода. Остальные вершины имеют четный индекс, так как с каждым входом в такую вершину есть и выход. Каждая пара вход – выход дает два ребра, сходящихся в данной вершине. Если начало и конец не совпадают, то они являются единственными вершинами нечетного индекса. У начала выходов на один больше, чем входов, а у конца входов на один больше чем выходов. Если же начало совпадает с концом, то вершин с нечетным индексом нет.
Теорема 4. Если граф G обладает эйлеровым путем c концами А и В (А не совпадает с В), то граф G связный и А и В — единственные нечетные его вершины.
Доказательство теоремы просим провести учеников.

Рис. 29
Связность графа следует из опреде­ления эйлерова пути. Если путь начинается в А, а заканчивается в другой верши­не В, то и А и В — нечетные, даже если путь неоднократно про­ходил через А и В. В любую другую вершину графа путь должен был привести и вывести из нее, то есть все остальные вершины должны быть четными. Верно и обратное.
Теорема 5. Если граф G связный и А и В единственные нечетные вершины его, то граф G обладает эйлеровым путем с кон­цами А и В.
Доказательство:

Рис. 30
Вершины А и В могут быть соеди­нены ребром в графе (рис. 30), а могут быть и не соединены (рис. 29)

  1. Если А и В соединены ребром, то удалим его; тогда все вершины станут четными. Новый граф, согласно предыдущей теореме, обла­дает эйлеровым циклом, началом и концом которого может служить любая вершина. Начнем эйлеров путь в вершине А и кончим его в вершине А. Добавим ребро (А, В) и получим эйлеров путь с на­чалом в А и концом в В.
  2. Если А и B не соединены ребром, то к графу добавим новое ребро (А, В), тогда все вершины его станут четными. Новый граф, согласно предыдущей теореме, обладает эйлеровым циклом. Нач­нем его из вершины А по ребру (А, В). Закончится путь тоже в вершине А. Если удалить теперь из полученного цикла ребро (А, В), то останется эйлеров путь с началом в В и концом в А или с началом в А и концом в В.

Таким образом, всякую замкнутую фигуру, имеющую в точнос­ти две нечетные вершины, можно начертить одним росчерком без повторений, начав в одной из нечетных вершин, а кончив в другой.
Задача 4.2. «Муха в банке».
Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все двенадцать ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается.

Решение. Является ли куб эйлеровым графом? Куб представляет собой граф, у которого все вершины имеют степень 3. Для того чтобы был эйлеровым нужно, чтобы все его вершины были четными, а это условие в данном случае не выполняется. Следовательно, граф не является эйлеровым. Значит, муха не сможет обойти все ребра куба, не проходя по одному ребру дважды.

Эйлеровы графы

Он имеет эйлеров путь ( 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 раза, по одному в каждом направлении.

10. Эйлеровы графы. Условия существования цепи и цикла. Гамильтоновы цепи и циклы.

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

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

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Условия существования цепи и цикла.

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

Теорема Эйлера 2. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четная степень.

Следствие 2.1. Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы.

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

Теорема 3 (алгоритм Флёри). Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:

  1. стираем ребра по мере их прохождения. И стираем также изолированные вершины, которые при этом образуются;
  2. на каждом этапе идем по мосту только тогда, когда нет других возможностей.

Любой простой полный граф с нечетным количеством вершин является эйлеровым.

Любой циклический граф является эйлеровым.

Гамильтоновы цепи и циклы.

Гамильтонов цикл — цикл, проходящий ровно один раз через каждую вершину графа G.

Тогда граф G называется гамильтоновым графом.

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

Теорема 4 (Дирарк, 1952).

Если в простом графе G с n>=3 вершинами степень любой вершины v scr37 , то граф G является гамильтоновым.

Любой простой полный граф является гамильтоновым.

Любой циклический граф является гамильтоновым.

Граф, являющийся колесом, является гамильтоновым.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *