Тапсырма № 9 · ОГЭ

Условия существования эйлерова пути

Как определить, можно ли пройти по всем рёбрам ровно один раз

2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

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

Условия существования эйлерова путиНазвание связано с задачей Эйлера о мостах Кёнигсберга.

Для неориентированного графа эйлеров путь — маршрут, проходящий по каждому ребру ровно один раз. Такой путь существует, если граф связен по рёбрам и число вершин нечётной степени равно 0 или 2. Изолированные вершины, не соединённые ни с одним ребром, при проверке связности не учитываются.

Критерий

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

\[\text{Эйлеров путь существует} \iff \begin{cases}\text{граф связен по рёбрам};\\ O=0\ \text{или}\ O=2,\end{cases}\]1

Здесь \(O\) — число вершин нечётной степени. При \(O=2\) путь начинается в одной нечётной вершине и заканчивается в другой. При \(O=0\) начало и конец совпадают, поэтому существует эйлеров цикл. Случай \(O>2\) невозможен: при каждом входе в промежуточную вершину нужен и выход, поэтому такие вершины имеют чётную степень.

№

Пример

Пусть в графе төрт вершины: степени равны \(2, 2, 3, 3\). Если все вершины с рёбрами связаны, нечётных вершин две, значит, эйлеров путь существует. Он начнётся в одной вершине степени \(3\) и закончится в другой. Если степени равны \(2, 2, 4, 4\), нечётных вершин нет — существует эйлеров цикл.

Проверь себя

У связного графа төрт вершины нечётной степени. Может ли в нём существовать эйлеров путь?

Не путайте путь и цикл

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

Главное за минуту

Главное

Проверьте связность всех вершин, имеющих рёбра.
Посчитайте вершины нечётной степени: 0 или 2 — путь существует.
0 нечётных вершин означает эйлеров цикл; 2 — открытый эйлеров путь.