Основные определения.

Пусть G(V, Е) – неориентированный граф. Рассмотрим конечную последовательность рёбер такую, что любые два соседние ребра имеют одну общую инцидентную вершину . Эту последовательность называется маршрутом графа.

Определение . Маршрутом (путем) для графа G(V, Е) называется последовательность v₁e₁v₂e₂v₃…e_kv_k+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути).

Любой отрезок конечного или бесконечного маршрута вида , где также является маршрутом и называется участком маршрута .

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

Рисунок 1.

Рассмотрим случай, когда , то есть начало и конец маршрута совпадают. Отметим, что в этом случае маршрут может быть только конечным..

Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.

В простой цепи любая вершина маршрута инцидентна не более чем двум его рёбрам.

Определение. Замкнутый маршрут (путь) называется циклическим маршрутом или циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.

Иначе говоря, простой цикл – это циклический маршрут, в котором любые два соседние ребра имеют одну инцидентную вершину. Последовательности , и представляют один и тот же цикл (рисунок 2). Часто считается, что можно менять порядок рёбер цикла на противоположный, то есть, например, последовательность представляет тот же цикл.

Рисунок 2.

Участок цепи или цикла является цепью; соответственно, участок простой цепи или простого цикла является простой цепью.