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

Пусть G - неориентированный граф. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) вершин и ребер v₀, x₁, v₁, x₂, v₂,...,v_n-1, x_n, v_n,..., что каждые соседние два ребра x_i и x_{i+ 1}имеют общую инцидентную вершину v_i. Одно и то же ребро и/или вершина могут встречаться в маршруте несколько раз. Маршрут полностью задается последовательностью ребер (x₁, x₂,..., x_n,...) или последовательностью вершин (v₀, v₁, v₂,.. v_n,..). В конечном маршруте (x ₁, x ₂,... x_n) имеется первое ребро x ₁и последнее ребро x_n. Вершина v ₀, инцидентная ребру x ₁, но не инцидентная ребру x ₂, называется началом маршрута, а вершина v_n, инцидентная ребру x_n, но не инцидентная ребру x_{n- 1}, называется концом маршрута.

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

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

Рис.4.3

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

Маршрут (цикл), в которой все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в которой все вершины, (кроме первой и последней), различны, называется элементарной цепью (циклом). Гамильтонова цепь (цикл) − простая цепь (цикл), проходящая через все вершины. Эйлерова цепь (цикл) − цепь (цикл), содержащая все ребра графа по одному разу.

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

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

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

(x ₁, x ₃, x ₅, x ₄)– цепь, которая является простой, но не элементарной;

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

(x ₁, x ₃, x ₅, x ₆) – Гамильтонова цепь.

Пути, контуры в ориентированном графе

Понятия пути, контура в ориентированном графе аналогичны понятиям цепи, цикла в неориентированном графе.

Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути.

Путь называется контуром, если его начальная вершина совпадает с конечной вершиной.