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

Маршрут в графе G = (V, Е) представляет собой конечную чередующуюся последовательность вершин и ребер v0, е1, v2, е2, … , vk-1, ek, vk, начинающуюся и кончающуюся на вершинах, причем Vi-t и Vi являются концевыми вершинами ребра e1, 1 ≤ i ≤ k. С другой стороны, маршрут можно рассматривать как конечную последовательность таких вершин v0, v1, v2, … , vk, что (vi-1, vi), 1≤ i ≤ k - ребро графа G. Такой маршрут обычно называется v0 – vk - маршрутом, a v0 и vk - концевыми или терминальными вершинами маршрута. Все другие вершины маршрута называются внутренними. Заметим, что ребра и вершины в маршруте могут появляться более одного раза.

Маршрут называется Открытым, если его концевые вершины различны, в противном случае он называется замкнутым. В графе на рис. 12 последовательность v1, e1, v2, е2, v3, е8, v6, e9, v5, e7, v3, e11, v6 является Открытым маршрутом, а последовательность v1, е1, v2, е2, v3, е7, v5, e3, v2, е4, v4, e5, v1-Замкнутым.

Рисунок 12

Маршрут называется Цепью, если все его ребра различны. Цепь называется открытой, если ее концевые вершины различны, в противном случае она называется замкнутой. На рис. 12 цепь v1, e1, v2, e2, v3, e8, v6, e11, v3 - Открытая, а v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1 - Замкнутая.

Открытая цепь называется Путем, если все ее вершины различны. Замкнутая цепь называется Циклом, если различны все ее вершины, за исключением концевых. Например, на рис. 12 последовательность v1, e1, v2, e2, v3 является путем, а последовательность v1, e1, v2, e3, v5, e6, v4, e5, v1 - циклом.

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

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

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

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

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

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

< Предыдущая		Следующая >