Задание № 9 · ОГЭ

Эйлеров путь

Путь, который использует каждое ребро графа ровно один раз

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Эйлеров путьНазвание связано с именем математика Леонарда Эйлера.

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

Как распознать эйлеров путь

При проверке нужно учитывать именно рёбра, а не только вершины. Например, если путь выглядит как \(A-B-C-B-D\), то ребро \(BC\) пройдено дважды: сначала из \(C\) в \(B\), а затем из \(B\) в \(C\). Такой маршрут эйлеровым не является.

\[\sum_{v \in V} \deg(v)=2|E|\]

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

№

Пример

Пусть граф имеет рёбра \(AB\), \(BC\), \(CD\) и \(DA\). Маршрут \(A-B-C-D-A\) проходит по каждому ребру ровно один раз. Это эйлеров путь, причём его начало и конец совпадают, поэтому одновременно это эйлеров цикл.

Не путайте с гамильтоновым путём

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

Проверь себя

Что обязательно для эйлерова пути?

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

Главное

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