4.7. Маршруты, цепи, циклы и связность

Пусть G — конечный граф. Маршрутом S в G на­зы­вается последовательность ребер,

S = (u₁, u₂, …, u_n), (4.6)

в которой любые соседние два ребра u_i-1, u_i, (i = 2, n) имеют общую вершину.

На графах допускаются маршруты, в которых не при­нимаются во внимание направления ребер. Такие марш­руты называются неориентированными.

Пусть на графе определен маршрут (4.6). Та вершина ребра u₁, которая не является общей с вершиной ребра u₂, называется начальной вершиной маршрута S.

Аналогично вводится понятие конечной вершины мар­шрута: та вершина ребра u_n, которая не является общей с вершиной u_n-1, называется конечной вершиной маршрута S.

Остальные вершины маршрута S называются внутренними.

Нуль‑маршрутом называется маршрут, не содержа­щий ребер.

Вершина u_j называется достижимой из вершины u_i, ес­ли существует маршрут из u_i в u_j. Для определенности счи­тают, что любая вершина u_i достижима из себя нуль-маршрутом независимо от наличия петель.

Неориентированный граф называется связным, если все его вершины попарно достижимы.

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

Ориентированный либо смешанный граф называется связным, если связен соответствующий ему соотнесенный граф.

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

Маршрут называется цепью, если все его ребра различны и — простой цепью, если все его вершины различны

Цепь называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла — зам­кнутая цепь, которое понимается в первоначальном опре­делении. Цикл называется простым, если все его вер­шины различны.

Началом (концом) цикла можно считать любую из его вершин.

На ориентированном графе аналогично понятию цепи вводится понятие пути, а аналогично понятию цикла — по­нятие контура.

Путь — это ориентированная цепь. Контур — это зам­кнутый путь. Рассмотрим примеры различных маршрутов на графе G, представленном на рисунке 4.11.

v₁

u₅

v₄ u₄ v₃ u₁ u₂

u₃ v₂

u ₆

u₇ v₅

Рисунок 4.11

Маршрут (u₄, u₁, u₂) является простой цепью.

Маршрут (u₄, u₁, u₂, u₃, u₁ ) цепью не является, поскольку ребро u₁ встречается в нем дважды. Маршрут (u₄, u₃, u₂, u₁) представляет цепь, но не простую, поскольку вершина v₃ встречается на ней дважды: как начало ребра u₁ и как конец ребра u₃. Такая цепь содержит в себе цикл. В данном случае в цепи (u₄, u₃, u₂, u₁) имеем цикл (u₃, u₂, u₁ ). Этот цикл простой. Примером не простого цикла может служить маршрут (u₁, u₂, u₃, u₇, u₆, u₅ ).

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