Пример 2.1.

Маршруты и цепи

Степени вершин графов

Def.Степенью вершины v графа называется число инцидентных ей ребер. Обозначается deg v. Вершина степени 0 называется изолированной, степени 1 – концевой или висячей.

Для орграфа вводятся также понятия

- полустепень исхода – число дуг выходящих из v; обозначается deg^– v;

- полустепень захода – число дуг входящих в v; обозначается deg⁺ v;

Свойство..

Теорема 2.1. (Теорема Эйлера, лемма о рукопожатиях). ;

Доказательство очевидно, если учесть, что каждое ребро в данной сумме учитывается 2 раза.

Теорема 2.2. (о нечетных степенях). В конечном графе число вершин с нечетными степенями четно.

Доказательство. Обозначим . По теореме 1.2. S четно. Далее, положим S_Ч – сумма степеней вершин с четной степенью, S_Н – сумма степеней вершин с четной степенью. Очевидно, S = S_Ч + S_Н. В S_Ч каждое слагаемое четно, значит, само S_Ч тоже четно. Отсюда, в силу четности S, получаем, что S_Н четно. Но каждое слагаемое в нем – нечетно. Следовательно, таких слагаемых должно быть четное число. Ч Т Д.

Def.Пусть G = (V, E) – неориентированный граф. Маршрутом называется такая последовательность его ребер e₁, … e_k, что каждые два соседних ребра e_j, e_j+1 имеют общую вершину.

Пусть e₁ = (v₀, v₁), e_k = (v_k–1, v_k). Тогда v₀ – начальная, v_k – конечная вершины маршрута. Если v₀ = v_k, то такой маршрут называется циклическим маршрутом.

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

В этом графе: (1, 2) и (1, 2, 4, 7) – простые цепи; (1, 2, 4, 7, 8, 4) – цепь, но не простая; (1, 2, 4, 7, 8, 4, 2) – маршрут, но не цепь; (1, 2, 4, 1) – простой цикл; (1, 2, 4, 7, 8, 4, 1) – цикл.

Задание 1. Доказать, что маршрут наименьшей длины, соединяющий две вершины графа является простой цепью.

Задание 2. Обозначим d(u, v) – длина маршрута наименьшей длины, соединяющего вершины u и v. Доказать, что для любых вершин x, y, z выполняется неравенство треугольника: d(x, y) £ d(x, z) + d(z, y).

Для орграфа существуют аналогичные понятия: неориентированный маршрут, цепь, цикл и т.д., в которых при прохождении ребер их ориентация не принимается во внимание. Также существуют ориентированный маршрут, цепь, цикл, в которых ребра проходятся в направлении их ориентации (по стрелке). Ориентированная цепь называется также путем, ориентированный цикл – контуром.

Свойства маршрутов. 1. Всякий маршрут, соединяющий вершины u и v, содержит простую цепь, соединяющую u и v.

Доказательство очевидно, т.к. удалив из маршрута повторяющиеся куски, можно преобразовать его в простую цепь.

2. Всякий цикл содержит простой цикл.

Доказательство аналогично.

3. Объединение двух несовпадающих простых цепей, соединяющих u и v, содержит простой цикл.

Доказательство.Пусть последовательности вершин P = (u₁, …, u_k) и Q = (v₁, …, v_s) – несовпадающие простые цепи, u₁ = v₁ = u. Пусть u_i и v_i – первые, считая от u, несовпадающие вершины, а u_j и v_r – первые из совпадающих вершин (u_j = v_r) после u_i и v_i .

Тогда u_i-1, u_i , …, u_j , v_r–1, … , v_i, u_i–1 – простой цикл (см. рис.) .