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

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

  • автор:

Эйлеров цикл

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эйлеровость графов

2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.

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

Эйлерова пути нет.
Количество вершин нечетной степени больше двух.

Две компоненты связности, одна имеет ребра.
В графе [math]G = (V, E) [/math] существует эйлеров цикл тогда и только тогда, когда:

1. Все вершины имеют четную степень.

2. Все компоненты связности, кроме, может быть, одной, не содержат ребер.

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин [math]n[/math] .

База индукции: [math]n = 0[/math] цикл существует.

Предположим что граф имеющий менее [math]n[/math] вершин содержит эйлеров цикл.

Рассмотрим связный граф [math]G = (V, E)[/math] с [math]n \gt 0[/math] вершинами, степени которых четны.

Пусть [math]v_1[/math] и [math]v_2[/math] — вершины графа. Поскольку граф связный, то существует путь из [math]v_1[/math] в [math]v_2[/math] . Степень [math]v_2[/math] — чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из [math]v_2[/math] . Так как граф конечный, то путь, в конце концов, должен вернуться в [math]v_1[/math] , следовательно мы получим замкнутый путь (цикл). Назовем этот цикл [math]C_1[/math] . Будем продолжать строить [math]C_1[/math] через [math]v_1[/math] таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины [math]v_1[/math] , то есть [math]C_1[/math] будет покрывать все ребра, инцидентные [math]v_1[/math] . Если [math]C_1[/math] является эйлеровым циклом для [math]G[/math] , тогда доказательство закончено. Если нет, то пусть [math]G'[/math] — подграф графа [math]G[/math] , полученный удалением всех рёбер, принадлежащих [math]C_1[/math] . Поскольку [math]C_1[/math] содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа [math]G'[/math] имеет чётную степень. А так как [math]C_1[/math] покрывает все ребра, инцидентные [math]v_1[/math] , то граф [math]G'[/math] будет состоять из нескольких компонент связности.

В графе [math]G = (V, E) [/math] существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

Ориентированный граф

В ориентированном графе [math]G = (V, E) [/math] существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

В ориентированном графе [math]G = (V, E)[/math] существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых [math]\operatorname^+ — \operatorname^- = 1[/math] , а для другой [math]\operatorname^+ — \operatorname^- = -1[/math] .

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

См. также

Источники информации

  • Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
  • Уилсон Р. Введение в теорию графов. — М.: Мир, 1977
  • Нахождение эйлерова пути

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

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

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

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

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

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

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

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

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

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

Дело в том, что одна из этих вершин имеет степень

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

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

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

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

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

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

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

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

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

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

Возьмем самый длинный путь

и рассмотрим одну из его конечных точек

. Эта вершина примыкает к предпоследней вершине пути. Так как у

степень не меньше двух, то должно существовать еще одно ребро, инцидентное ей.

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

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

пути. Это создает цикл от

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

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

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

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

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

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

ребер тривиально верен — это значит, что в графе есть только одна вершина и нет ребра.

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

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

есть цикл. Удалим ребра цикла из

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

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

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

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

После этого проследим цикл от

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

. В конце мы возвращаемся по циклу от

, и завершаем эйлерову схему всего графа. Значит, теорема доказана.

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

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

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

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

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

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

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов

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

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

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

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

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