Маршруты, циклы в неориентированном графе

Пусть G – неориентированный граф.

Определение 3.5.1. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) ребер a ₁, a ₂,... a_n..., что каждые соседние два ребра a_i и a_i+ 1 имеют общую инцидентную вершину.

Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a ₁, a ₂,... a_n) имеется первое ребро a ₁ и последнее ребро a_n. Вершина x ₁, инцидентная ребру a ₁, но не инцидентная ребру a ₂, называется началом маршрута, а вершина x_n, инцидентная ребру a_n, но не инцидентная ребру a_n– 1, называется концом маршрута.

Определение 3.5.2. Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько

раз, сколько оно входит в данный маршрут. Замкнутый маршрут называется циклом.

Пример. В изображенном на рис. 16 графе рассмотрим два маршрута из вершины x ₁ в вершину x ₄: M ₁ = (a ₁, a ₂, a ₄) и M ₂ = (a ₁, a ₂, a ₅, a ₆).

рис.16

Длина маршрута M 1 равна 3, а длина маршрута M 2 равна 4.

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

Пример. В приведенном на рис. 17 графе выделим следующие маршруты:

рис.17

(a ₁, a ₃, a ₄) – простая элементарная цепь длины 3, т.к. все ребра и вершины попарно различны;

(a ₂, a ₄, a ₃) – простой элементарный цикл, т.к. это замкнутый маршрут, у которого все ребра и вершины, кроме первой и последней, различны;

(a ₁, a ₂, a ₄, a ₃) – цепь, которая является простой, но не элементарной, т.к. все ребра различны, но вершина x ₂ встречается дважды;

(a ₁, a ₂, a ₂) – маршрут длины 3, не являющийся ни простой, ни элементарной цепью, т.к. ребро a ₂ и вершина x ₂ встречаются дважды.

Дата добавления: 2014-01-06