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

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

  • автор:

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 является гамильтоновым.

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

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

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

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

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

Эйлеров цикл

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск Эйлерового цикла и пути

Эйлеров путь(цепь) проходит через каждое ребро графа ровно по одному разу.

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

Алгоритм поиска Эйлеров цикла

Сервис использует алгоритм поиска Эйлеров цикла на основе циклов.

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

Кроме того, перед поиском цикла проверяется его существование, для этого происходит поиск степени вершин.

Более подробно вы можете узнать об этом алгоритме в Википедии.

Реализацию алгоритма на языке C++ вы можете найти в нашем репозитории на GitHub: Реализация поиска Эйлерового цикла в Graphoffline.

Алгоритм поиска Эйлервой цепи

Для поиска Эйлеров пути мы добавляем псевдо ребро соединяющие начальную и конечную вершину Эйлерова пути.

Начальная и конечная вершина для неориентированного графа будет иметь нечётные степени.

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

Как использовать

  1. Создайте граф.
  2. Выберите пункт меню Алгоритмы -> «Найти Эйлеров цикл» для поиска Эйлеров цикл.
  1. Выберите пункт меню Алгоритмы -> «Найти Эйлерову цепь» для поиска Эйлеровой цепи.

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)

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

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