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

Эйлеров цикл

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

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

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

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

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

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

\[v_0=v_m,\qquad e_1,e_2,\ldots,e_m\text{ — все рёбра графа ровно по одному разу}\]1

№

Пример

Пусть граф состоит из треугольника с вершинами \(A\), \(B\), \(C\) и рёбрами \(AB\), \(BC\), \(CA\). Маршрут \(A\to B\to C\to A\) является эйлеровым циклом: он начинается и заканчивается в \(A\), а каждое из трёх рёбер используется один раз.

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

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

Проверьте себя

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

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

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

Главное

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