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

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, то такой маршрут называется циклическим маршрутом.

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

Ч

2

1

исло ребер маршрута называетсядлиной маршрута.

Пример 2.1.

6

5

3

4

8

7

В этом графе: (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 – простой цикл (см. рис.) .

u_j–1

u_i

….

u_j

u_i-1

u₂

u₁

v

u

…

….

v_r

v_i–1

v₁

v₂

v_i

….

v_r–1

2.3. Связность

Def. Говорят, что вершина u достижима из v, если существует маршрут, соединяющий u и v.

Def. Граф называется связным, если любые его две вершины можно соединить маршрутом.

Замечание. Учитывая свойство 1 маршрутов, в этих определениях слово “маршрут” можно заменить на “простая цепь”.

Теорема 2.3. (1-я теорема о связности) Для связности графа необходимо и достаточно, чтобы в нем какая-нибудь фиксированная вершина u была достижима из любой другой вершины.

Доказательство. Пусть вершина u достижима из любой другой вершины. Выберем две любые вершины v и w. Соединим v и u, а также w и u маршрутами. Объединив их, получим маршрут v, u, w, соединяющий вершины v и w. В силу произвольности v и w, теорема доказана.

Компоненты связности

Задание. Доказать, что отношение достижимости между двумя вершинами обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является эквивалентностью.

Так как отношение достижимости между двумя вершинами является эквивалентностью, то, по теореме о разбиении, вершины графа можно разбить на непересекающиеся классы V₁, …, V_k, и такие, что вершины, принадлежащие одному классу достижимы друг для друга, но не достижимы для вершин из любого другого класса.

Образуем подграфы G_i = (V_i, E_i), соединив вершины множества V_i ребрами из множества E_i  E. Очевидно – граф распался на связные подграфы, не имеющие общих вершин и ребер. Такие подграфы называютсякомпонентами связности графа G. Геометрически они выглядят, как отдельные изолированные куски.

Теорема 2.4. (2-я терема о связности) Если в произвольном неориентированном графе ровно две вершины имеют нечетную степень, то они достижимы друг для друга.

Доказательство. Пусть в графе G только две вершины u и v имеют нечетную степень. По теореме 2.2. о нечетных степенях, в конечном графе число вершин с нечетными степенями четно. Пусть G_u – компонента связности, которой принадлежит вершина u. Так как теорема 2.2 применима и к G_u , то в ней кроме u должна быть еще хотя бы одна вершина с нечетной степенью. Но во всем графе всего одна такая вершина – это v. Следовательно, v  G_u. Значит, u и v достижимы друг для друга, т.к. принадлежат одной компоненте связности. ЧТД.

Теорема 2.5. (3-я терема о связности) Для n-вершинного графа с m ребрами и k компонентами связности справедливо неравенство m  n – k.

Доказательство. Докажем индукцией по m. При m = 0 будет n = k, значит, неравенство выполняется.

Пусть m > 0 и для графов с меньшим числом ребер неравенство верно. Удалим из графа любое ребро. Тогда число его ребер станет m₁ = m – 1, а число компонент связности либо станет k + 1, либо останется равным k. Рассмотрим два случая.

1) Стало k + 1 компонент. Тогда по предположению индукции m₁ = m – 1  n – (k + 1). Значит m  n – k.

2) Осталось k компонент. Тогда m₁ = m – 1  n – k. Тем более m  n – k.

Теорема доказана.