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

Цикл в графе

Замкнутый путь без повторения внутренних вершин
2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Цикл в графеСлово происходит от греческого kyklos — «круг».
Цикл — это последовательность вершин \(v_0, v_1, \ldots, v_k\), где каждая соседняя пара соединена ребром, \(v_0=v_k\), а внутренние вершины \(v_1,\ldots,v_{k-1}\) попарно различны. В неориентированном графе цикл обычно содержит не менее трёх рёбер.

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

\[v_0=v_k,\qquad v_i\ne v_j\ \text{для}\ 1\le i<j\le k-1\]
№
Пример

В графе с рёбрами \(A-B\), \(B-C\), \(C-A\) последовательность \(A\to B\to C\to A\) образует цикл. Вершина \(A\) повторяется только как начало и конец, а \(B\) и \(C\) встречаются по одному разу. Последовательность \(A\to B\to C\to B\to A\) циклом не считается: вершина \(B\) повторена внутри пути.

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

Проверь себя

Какая последовательность является циклом?

!
Не путайте

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

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

Главное

  • Цикл замкнут: его первая и последняя вершины совпадают.
  • Внутренние вершины цикла не повторяются.
  • Циклы можно искать обходом графа в глубину.