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

До 4 баллов за конспект

Определение. Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.

В случае простого графа маршрут однозначно определяется последовательностью вершин или последовательностью ребер. Если маршрут в простом графе задан последовательностью вершин v ₀, v ₁ ,, …, v_k, то вершины v ₀, v_k называют концами маршрута. Если v ₀ = v_k, то маршрут называют замкнутым, в противном случае – незамкнутым.

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

Определение. Простой цикл с р вершинами обозначается С_р . Например, граф – это одновременно граф С₃.

Определение. Ориентированная простая цепь называется путем, ориентированный простой цикл называют контуром.

Рассмотрим граф на рис. 11. Маршруты в этом графе будем задавать последовательностью вершин.

Пример маршрута: 1 – 2 – 3 – 5 – 7 – 4 – 3 – 5 – 6 – 2 – 3 – 4.

Пример замкнутого маршрута: 3 – 4 – 5 – 7 – 3 – 4 – 1 – 3.

Пример цепи, соединяющий вершины 6 и 8: 6 – 5 – 3 – 4 – 5 – 7 – 3 – 2 – 6 – 8.

Пример цикла: 5 – 3 – 2 – 6 – 5 – 7 – 4 – 5.

Примеры простых цепей, соединяющих вершины 1 и 6: 1 – 3 – 4 – 5 – 6; 1 – 2 – 6; 1 – 4 – 7 – 8 – 6.

Примеры простых циклов: 3 – 5 – 7 – 4 – 3; 1 – 2 – 6 – 8 – 7 – 4 – 1;

1 – 2 – 6 – 5 – 7 – 3 – 1.

Рис. 11

Рассмотрим ориентированный граф на рис. 12. Ориентированные маршруты в этом графе будем задавать последовательностью вершин, проходимых в направлении ориентации дуг.

Рис. 12

Пример ориентированного маршрута: 1 ® 2 ® 3 ® 5 ® 2 ® 6 ® 8 ® 5.

Пример замкнутого ориентированного маршрута: 1 ® 4 ® 5 ® 2 ® 6 ® 8 ® 5 ® 2 ® 3 ® 1.

Пример ориентированной цепи: 4 ® 5 ® 7 ® 8 ®5 ® 2.

Пример замкнутой ориентированной цепи: 6 ® 8 ® 5 ® 2 ® 3 ® 1 ® 5 ® 6.

Пример пути, соединяющего вершины 3 и 9: 3 ® 1 ® 4 ® 5® 6 ® 9.

Пример контура: 5 ® 7 ® 4 ® 5.

Определение. Длиной маршрута называют число ребер в нем с учетом повторений.

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

Определение. Самая длинная геодезическая цепь называется диаметром графа. Длину диаметра так же будем называть диаметром и обозначать буквой . Расстояние между вершинами и и v обозначим через d (u, v).

Рассмотрим граф на рис. 11.

d (1, 5) = 2; d (5, 7) = 1; d (4, 9) = 3; d (1, 8) = 3. = 3 и геодезических длины 3 в графе несколько. Например, это геодезические 1 – 2 – 6 – 9 и 1 – 4 – 7 – 8.

Определение. Ярусом вершины v порядка n (обозначение: ), n = 0, 1, 2, … называется множество вершин, находящихся от вершины v на расстоянии n.

Рассмотрим граф на рис.11 и выпишем ярусы вершины 9.

D (9, 0) = {9}; (9, 1) = {6}; (9, 2) = {2, 5, 8}; (9, 3) = {1, 3, 4, 7}.

Определение. Две вершины и и v называются связными, если их соединяет хотя бы одна простая цепь.

Очевидно, что отношение связности - это отношение эквивалентности.

Определение. Граф G (V, E) называют связным, если любые две его вершины можно соединить простой цепью. В противном случае граф называется несвязным.

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

На рис. 13 показан граф, состоящий из четных компонент связности.

Рис. 13

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

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

Утверждение (Кениг). Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.