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

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

Конечная последовательность ребер в[, е₂, …, е_п графа (не обязательно различных) называется маршрутом длины п, если существует последовательность vo, v, v" из л+1 (не обязательно различных) вершин. Одно ребро рассматривается как маршрут единичной длины.

Путь — маршрут, в котором все ребра различны.

Маршрут замкнут, если начальная vq и конечная v" вершины совпадают vq — v", и не замкнут, если v₀ Ф v" .

Пример. На рис. 5.5 последовательность ребер е, е$, е₄, е$, е$, e-j образует незамкнутый маршрут длиной 6 единиц. Последовательность е$, е₂, *7″ ^еь образует путь, а е₃, е₂, ei, е₄, еь — замкнутый путь.

Рис. 5.5. Иллюстрация понятий «маршрут (путь)», «цепь», «цикл»

Если все ребра, составляющие маршрут, различны и при этом начальная и конечная вершины маршрута не совпадают, он называется цепью (последовательность ребер в, е₄, е$ на рис. 5.5). Если цепь замкнута, маршрут называется циклом (последовательность ребер е, еь, е₄, ^е5 ^на рис. 5.5).

Граф — связный, если любая пара различных его вершин может бьггь соединена, по крайней мере, одной цепью. В противном случае граф называется несвязным. Связностью графа называется наименьшее число вершин, удаление которых делает граф несвязным. Реберной связностью называется наименьшее количество ребер, удаление которых делает граф несвязным.

Цикл, в котором содержатся все ребра графа, причем каждое ребро встречается только один раз, называется эйлеровым. Эйлеров цикл содержится в графе, не содержащем вершин нечетной степени.

Пример. Последовательность ребер от исходной вершины v₀ графа рис. 5.6 составляет эйлеров цикл С= {но, v₃, v_b v₀, v₄, v_b v* v₅, v₄, v^, v₀).

Рис. 5.6. Эйлеров цикл

Для того чтобы в графе имелась эйлерова цепь, содержащая все его ребра в точности, но одному разу (начальная и конечная вершины маршрута не совпадают), необходимо и достаточно, чтобы V/ и vj были единственными вершинами нечетной степени (рис. 5.7). На любом связном графе с 2к нечетными вершинами имеется семейство из к цепей, которые содержат все ребра графа по одному разу (рис. 5.8).

Рис. 5.7. Граф, содержащий эйлерову цепь

Рис. 5.8. Граф, содержащий семейство, состоящее из 2 эйлеровых цепей

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

Граф с п вершинами имеет гамильтонов цикл, если для любой пары его вершин выполняется соотношение.

В частности, граф имеет гамильтонов цикл, если для каждой его вершины.

Если выполняется условие то граф имеет гамильтонову цепь.

Если граф обладает гамильтоновым циклом, то он обладает и гамильтоновой цепью. Обратное, вообще говоря, неверно.

При решении ряда технических задач, связанных, например, с расчетом электрических цепей требуется определение числа независимых контуров (циклов). Эта задача решается путем определения цикломатического числа y (G) графа G, имеющего п вершин, т ребер и г компонент связности: