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

Маршрутом в графе называется чередующаяся последовательность вершин и ребер

v₀, e₁, v₁, e₂, v₂, ..., e_k, v_k,

в которой любые два соседних элемента инцидентны. Количество ребер в маршруте называется его длиной.

Это определение подходит также для псевдо-, мульти- и орграфов. В орграфе маршрут называется ориентированный маршрут. Для неориентированного и ориентированного графов при задании соответственно маршрута и ориентированного маршрута достаточно указать только последовательность вершин или только последовательность ребер.

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

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v₀, e₁, v₁, e₂, v₂, ..., e_k, v_k вершины v₀ и v_k называются концами цепи. Говорят, что цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается . Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф, не содержащий циклов, называется ациклическим.

В ориентированном графе незамкнутый ориентированный маршрут, содержащий попарно различные дуги, называется путем. Путь, в котором все вершины попарно различны, называется простым путем. Замкнутый путь называется контуром, замкнутый простой путь - простым контуром. Виды маршрутов, соответствующие друг другу в неориентированном и ориентированном графах приведены в таблице 1.

Таблица 1

Виды маршрутов в неориентированном и ориентированном графах

Неорграф	Орграф
Маршрут	Ориентированный маршрут
Цепь	Путь
Простая цепь	Простой путь
Цикл	Контур
Простой цикл	Простой контур

Например, графе, диаграмма которого приведена на рис. 7:

1. v₁, v₃, v₁, v₄ – маршрут, но не цепь;

2. v₁, v₃, v₅, v₂, v₃, v₄ – цепь, но не простая цепь;

3. v₁, v₄, v₃, v₂, v₅ – простая цепь;

4. v₁, v₃, v₅, v₂, v₃, v₄, v₁ – цикл, но не простой цикл;

5. v₁, v₃, v₄ – простой цикл.

Рис. 7. К понятию маршрутов, цепей, циклов

В псевдографах, мультиграфах и простых графах минимальная длина простого цикла рана 1, 2 и 3 соответственно. Если в графе хотя бы одно ребро и отсутствуют висячие вершины, то граф содержит хотя бы один простой цикл. Простой цикл является объединением двух простых несовпадающих цепей. В неорграфе (орграфе) из всякого цикла (контура) можно выделить простой цикл (простой контур), а из всякого незамкнутого маршрута (пути) можно выделить простую цепь (простой путь) с теми же начальными и конечными вершинами.

Цикл (цепь) в графе G называется эйлеровым (эйлеровой), если он (она) проходит по одному разу через каждое ребро этого графа. Цикл (цепь) в графе G называется гамильтоновым (гамильтоновой), если он (она) проходит через каждую вершину графа ровно один раз. Например, для графа, диаграмма которого представлена на рис. 1,

v₂, v₁, v₄, v₂, v₃, v₄ – эйлерова цепь, а v₁, v₂, v₃, v₄, v₁ – гамильтонов цикл.

Граф называется эйлеровым, если он содержит эйлеров цикл, и полуэйлеровым, если он содержит эйлерову незамкнутую цепь.

Граф называется гамильтоновым, если он содержит гамильтонов цикл.