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

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

Пусть e1 = (v0, v1), ek = (vk–1, vk). Тогда v0 – начальная, vk – конечная вершины маршрута. Если v0 = vk, то такой маршрут называется циклическим маршрутом.

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

В этом графе: (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 = (u1, …, uk) и Q = (v1, …, vs) – несовпадающие простые цепи, u1 = v1 = u. Пусть ui и vi – первые, считая от u, несовпадающие вершины, а uj и vr – первые из совпадающих вершин (uj = vr) после ui и vi .

Тогда ui-1, ui , …, uj , vr–1, … , vi, ui–1 – простой цикл (см. рис.) .