2.4 Маршруты, цепи, пути и циклы

Маршрут в графе G = (V, Е) представляет собой конечную чередующуюся последовательность вершин и ребер v₀, е₁, v₂, е₂, … , v_k-1, e_k, v_k, начинающуюся и кончающуюся на вершинах, причем V_i-t и V_i являются концевыми вершинами ребра e₁, 1 ≤ i ≤ k. С другой стороны, маршрут можно рассматривать как конечную последовательность таких вершин v₀, v₁, v₂, … , v_k, что (v_i-1, v_i), 1≤ i ≤ k - ребро графа G. Такой маршрут обычно называется v₀ – v_k -маршрутом, a v₀ и v_k - концевыми или терминальными вершинами маршрута. Все другие вершины маршрута называются внутренними. Заметим, что ребра и вершины в маршруте могут появляться более одного раза.

Маршрут называется открытым, если его концевые вершины различны, в противном случае он называется замкнутым. В графе на рис. 12 последовательность v₁, e₁, v₂, е₂, v₃, е₈, v₆, e₉, v₅, e₇, v₃, e₁₁, v₆ является открытым маршрутом, а последовательность v₁, е₁, v₂, е₂, v₃, е₇, v₅, e₃, v₂, е₄, v₄, e₅, v₁-замкнутым.

Рисунок 12

Маршрут называется цепью, если все его ребра различны. Цепь называется открытой, если ее концевые вершины различны, в противном случае она называется замкнутой. На рис. 12 цепь v₁, e₁, v₂, e₂, v₃, e₈, v₆, e₁₁, v₃ - открытая, а v₁, e₁, v₂, e₂, v₃, e₇, v₅, e₃, v₂, e₄, v₄, e₅, v₁ - замкнутая.

Открытая цепь называется путем, если все ее вершины различны. Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых. Например, на рис. 12 последовательность v₁, e₁, v₂, e₂, v₃ является путем, а последовательность v₁, e₁, v₂, e₃, v₅, e₆, v₄, e₅, v₁ - циклом.

Ребро графа G называется циклическим, если в графе G существует цикл, содержащий ребро. В противном случае ребро называется нециклическим. На рис. 12 все ребра, за исключением е₁₂, циклические.

Число ребер в пути называется длиной пути. Аналогично определяется длина цикла.

Необходимо указать следующие свойства путей и циклов.

1. Степень каждой не концевой вершины пути равна 2, концевые вершины имеют степень, равную 1.

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

3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.