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

Пусть G - неориентированный граф. Маршрутом или цепью в 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.10.

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

Рис.3.5

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

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

Пример 3.11.

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

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

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

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

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

Рис.3.6