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

Цепь в графе

Маршрут, в котором каждое ребро используется не более одного раза

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

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

Цепь в графеТермин связан с представлением о последовательном соединении рёбер графа.

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

Как распознать цепь

Чтобы проверить, является ли последовательность переходов цепью, нужно перечислить использованные рёбра и убедиться, что ни одно из них не повторяется. Повторение вершины само по себе не нарушает условие. Например, маршрут \(A\!-B\!-C\!-B\!-D\) может быть цепью, если рёбра \(AB\), \(BC\), \(CB\) и \(BD\) считаются разными рёбрами только при наличии соответствующих рёбер графа. В неориентированном графе переходы \(B\!-C\) и \(C\!-B\) используют одно и то же ребро, поэтому здесь повторение будет нарушением.

\[L(\text{цепи})=\text{число использованных рёбер}\]

№

Пример

Пусть в графе есть рёбра \(AB\), \(BC\), \(CD\) и \(DA\). Последовательность \(A\!-B\!-C\!-D\) — цепь: рёбра \(AB\), \(BC\) и \(CD\) не повторяются. Последовательность \(A\!-B\!-C\!-B\) цепью не является, потому что ребро \(BC\) используется дважды: сначала из \(B\) в \(C\), затем из \(C\) в \(B\).

Не путайте с другими понятиями

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

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

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

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

Главное

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