Изучи теоретическую справку

Путь в графе от одной вершины к другой — это такая последовательность рёбер графа, в которой каждые \(2\) соседних ребра имеют общую вершину.

Длиной пути будем считать количество рёбер в этом пути.

Пример. На графе выше путь от точки \(Б\) до точки \(Ж\) можно описать следующим образом:

\(БД-ДЖ\) или \(БД-ДЕ-ЕЖ\) .

Длина пути \(БД-ДЖ\) равна \(2\) , а длина пути \(БД-ДЕ-ЕЖ\) равна \(3\) .

Путь в графе, вершины которого не повторяются, называется цепью.

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