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

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

v 0, a 1, v 1, a 2, v 2, …, vk –1, ak, vk,

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

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

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

«маршрута».

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

1 a 2 c 3 e 1, или, короче, 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

Не нашли, что искали? Воспользуйтесь поиском: