1.2. Маршруты и пути

Последовательность V1X1V2X2V3…XKVK+1, (где K³1, VIÎV, I=1,…,K+1, XIÎX, J=1,…,K), в которой чередуются вершины и ребра (дуги) и для каждого J=1,…,K ребро (дуга) XJ имеет вид {Vj,Vj+1} (для ориентированного графа (Vj,Vj+1)), называется Маршрутом, соединяющим вершины V1 и Vk+1 (Путем из V1 в Vk+1).

Пример

В графе, изображенном на рис.4, V1X1V2X2V3X4V4X3V2 – маршрут, V2X2V3X4V4 – подмаршрут;

Маршрут можно восстановить и по такой записи X1X2X4X3 ;

Если кратности ребер (дуг) равны 1, можно записать и так V1V2V3V4V2 .

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

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (Цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (Контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (Путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (Путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (Пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.

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