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

Последовательность вершин v0, v1, v2, …, vk графа G представляет собой маршрут в этом графе от вершины v0 к вершине vk, если для любого i = 0, 1, 2, …, k–1 вершины vi и vi+1 соединены дугой. В случае, когда допускаются параллельные дуги, нужно дополнительно указать, по какой дуге из vi в vi+1 проходит маршрут. В этом случае маршрут от вершины v0 к вершине vk, задается последовательностью вида

v0, a1, v1, a2, v2, …, vk–1, ak, vk,

где v0, v1, …, vk – последовательность вершин, a1, a2, …, ak – последовательность дуг, причем дуга ai соединяет вершину vi–1 с вершиной vi. На самом деле, поскольку концы дуг определены однозначно, маршрут можно представить последовательностью дуг a1, a2, …, ak. Длиной маршрута считается число дуг, которые он содержит. Все вершины маршрута, кроме начальной и конечной, называют внутренними или промежуточными. Вообще говоря, и начальная, и конечная вершины могут встретиться на маршруте как промежуточные вершины. Для любой вершины имеется маршрут из этой вершины в нее же, не содержащий ни одной дуги (длины 0).

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

Впрочем, довольно часто «путь» используют как синоним

«маршрута».

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

1a2c3e1, или, короче, ace, является простым циклом. Поскольку параллельных дуг на графе нет, этот цикл можно указать и по вершинам: 1231. Ясно, что маршруты 2312 и 3123 представляют тот же цикл. Граф, не содержащий циклов, называется ациклическим.

Будем говорить, что вершина y достижима из вершины x,

если в графе G имеется путь из x в y.

Пусть G – произвольный орграф. Пополним его новыми дугами. Новая дуга из вершины x в вершину y проводится в том случае, если y достижима из x, а граф G не содержит дуги из x в y. Обозначим пополненный граф через G^. Минимальный подграф графа G, индуцирующий на множестве вершин то же отношение достижимости и, соответственно, порождающий тот же пополненный граф G^, что и граф G, обозначается через GB и называется базисным графом для графа G. Для ациклического графа его базисный граф определен однозначно. На рис. 3

представлен ациклический граф; «жирными» наконечниками

отмечены дуги, входящие в базисный граф.

Рис. 3

На множестве вершин неориентированного графа G отношение достижимости является отношением эквивалентности. Класс эквивалентности составляют все вершины, которые могут быть связаны друг с другом некоторым путем. Эти классы эквивалентности называются компонентами связности. Неориентированный граф G называется связным, если в нем любые две вершины можно соединить путем. Связный граф имеет всего одну компоненту связности. На рис. 4 изображен граф с четырьмя компонентами

связности.

Рис. 4