Условия существования эйлерова цикла
Эйлеров цикл — это замкнутый маршрут в графе, который проходит по каждому ребру ровно один раз и возвращается в начальную вершину. На экзамене существование такого цикла проверяют по двум условиям: связности графа и чётности степеней его вершин.
Что нужно проверить
Сначала вспомним Эйлеров цикл: маршрут начинается и заканчивается в одной вершине, а каждое ребро используется ровно один раз. Вершины при этом могут встречаться несколько раз. Это важно: проверяется именно использование рёбер, а не вершин.
Степень вершины — количество рёбер, выходящих из неё или входящих в неё. Для обычного неориентированного графа каждое ребро, соединённое с вершиной, увеличивает её степень на 1. Подробнее о понятии можно прочитать на странице степень вершины.
Граф называется связным, если из любой его вершины можно добраться до любой другой по рёбрам. Для условия Эйлерова цикла обычно рассматривают связность части графа, содержащей рёбра: изолированные вершины без рёбер не мешают существованию цикла.
В конечном неориентированном графе существует Эйлеров цикл тогда и только тогда, когда граф связен по рёбрам и степени всех его вершин чётные.
Значит, для решения задачи достаточно выполнить два шага: проверить, что все вершины с рёбрами принадлежат одной связной компоненте, и пересчитать степени всех вершин. Если хотя бы одна степень нечётная или граф распадается на части, Эйлерова цикла нет.
Почему степени должны быть чётными
Представим движение по Эйлерову циклу. Каждый раз, когда маршрут приходит в вершину по одному ребру, он должен выйти из неё по другому неиспользованному ребру. Рёбра около вершины разбиваются на пары: одно ребро для входа и одно для выхода.
Для начальной вершины действует то же правило: маршрут сначала выходит из неё, а в конце возвращается. Поэтому и там рёбра также объединяются в пары. Нечётная степень означает, что одно ребро останется без пары, а значит, замкнутый маршрут невозможен.
Связность тоже необходима. Если рёбра находятся в двух несвязанных частях, нельзя одним маршрутом пройти рёбра обеих частей: между ними нет перехода. Обратите внимание, что изолированная вершина с нулевой степенью не нарушает критерий, потому что в ней нет ребра, которое нужно проходить.
У связного графа степени вершин равны 2, 2, 4, 4 и 6. Существует ли Эйлеров цикл?
Алгоритм решения экзаменационной задачи
- Найдите все вершины, которые имеют хотя бы одно ребро.
- Для каждой такой вершины посчитайте степень: сколько рёбер к ней прилегает.
- Проверьте чётность степеней. Если найдена хотя бы одна нечётная степень, ответ отрицательный.
- Проверьте связность: из любой вершины с рёбрами должна быть достижима любая другая.
- Если оба условия выполнены, Эйлеров цикл существует.
В таблице или на рисунке удобно составить строку степеней. Для каждой вершины считайте каждое прилегающее ребро один раз. Если между двумя вершинами есть два параллельных ребра, оба увеличивают степень. Петля в неориентированном графе обычно учитывается дважды, потому что имеет два конца в одной вершине.
Разобранный пример
Дан граф с вершинами \(A,B,C,D,E\) и рёбрами \(AB\), \(BC\), \(CD\), \(DE\), \(EA\), \(AC\), \(CE\). Требуется определить, существует ли в нём Эйлеров цикл.
Сначала найдём степени вершин и затем проверим связность.
Здесь важно не остановиться после проверки связности. Граф действительно связен, но две вершины имеют нечётную степень. Такой граф может иметь Эйлеров путь с разными началом и концом, однако Эйлеров цикл в нём невозможен. О различии между этими случаями см. Эйлеров путь.
Связность и особые случаи
Если граф состоит из нескольких компонент, в каждой из которых есть рёбра, одного Эйлерова цикла для всего графа быть не может. Иногда на рисунке есть отдельные вершины без рёбер. Их можно не учитывать при проверке связности: маршрут не обязан посещать вершину, если через неё нельзя пройти по ребру.
В задачах с матрицей смежности связность можно проверять по рисунку или поиском в глубину. Если требуется только ответ «существует ли цикл», обычно быстрее пересчитать степени и убедиться, что все вершины с ненулевой степенью находятся в одной компоненте.
Связность + все степени чётные = Эйлеров цикл. Для Эйлерова пути условие другое: нечётных вершин должно быть ровно 0 или 2, а для цикла — только 0.
Не путайте Эйлеров цикл с Гамильтоновым циклом: Эйлеров цикл проходит по каждому ребру, а Гамильтонов — по каждой вершине. Не требуйте, чтобы вершины посещались ровно по одному разу. Не считайте граф связным только потому, что в нём нет очевидных пустых участков: проверьте достижимость всех вершин с рёбрами. Наконец, одной чётности степеней недостаточно — граф должен быть связным.
Связь с другими задачами на графы
Эйлеров цикл относится к задачам на маршруты: здесь важны рёбра и возможность пройти по ним без повторений. Это отличается от задач на кратчайший путь, где ищут маршрут минимальной длины, и от Гамильтонова пути, где требуется посетить вершины. Для задач экзамена полезно сначала определить, что именно нужно использовать ровно один раз: рёбра или вершины.
Проверьте себя
Главное
- Эйлеров цикл — замкнутый маршрут, проходящий по каждому ребру ровно один раз.
- Он существует тогда и только тогда, когда граф связен по рёбрам и степени всех его вершин чётные.
- Чётность объясняется тем, что в каждой вершине рёбра маршрута образуют пары «вход — выход».
- Изолированные вершины без рёбер не мешают проверке связности.
- Не путайте Эйлеров цикл с Гамильтоновым: первый связан с рёбрами, второй — с вершинами.