Связность графов. Глава 2

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

Маршруты

Цепи и циклы

Лемма. Всякий маршрут графа содержит хотя бы одну простую цепь, соединяющую ту же пару вершин.
Доказательство
Если в полученном маршруте есть еще повторяющиеся вер-шины, то снова заменяем его более коротким и так далее, пока не выделим маршрут без повторяющихся вершин.

Пример
Маршрут a 1 b 2 c 3 d 4 b 5 e содержит простую цепь a 1 b 5 e.
Следствие Всякий кратчайший маршрут между двумя заданными вершинами графа есть простая цепь.
Всякий цикл наименьшей длины при заданной вершине является простым.

Если маршрут рассматривать с учетом ориентации ребер (может быть и по звеньям), то получим соответствующие определения:
ориентированный маршрут (ормаршрут);
ориентированная цепь (орцепь) – путь;
простая орцепь – простой путь.

Задачи о маршрутах
В теории рассматривается ряд задач и алгоритмов определения свойств маршрутов:
существование маршрутов заданной длины;
достижимость вершин;
число маршрутов заданной длины;
компоненты связности и бисвязности;
кратчайшие цепи/пути;
кратчайшие цепи/пути на взвешенных графах.

Существование маршрутов
Рассматривается неориентированный (маршрут не предполагает ориентации) униграф (важен лишь факт смежности вершин).
Такой граф можно рассматривать как симметричное бинарное отношение и его можно задать матрицей смежности R, элементы rij которой – булевы. rij =1, если вершины смежны; из вершины xi существует маршрут длины 1 в вершину xj.
Элемент матрицы R2
определяет существование
маршрута длины 2 между этими вершинами. Далее по индукции:
(*)

и вершины xk и xj смежны.
Для маршрутов других видов задаются соответствующие матрицы смежности.

Нахождение маршрутов
Длина 1
a1a
a2b
b2a
b3c
b4c
c3b
c4b
Длина 2
a1a1a
a1a2b
a2b2a
a2b3c
a2b4c
b2a1a
b2a2b
b3c3b
…
Длина 3

Число маршрутов

Число различных маршрутов длины 2 из вершины xi в вершину xj
через вершину xk есть
Далее по индукции.
Здесь сложение и умножение – обычные арифметические
операциии.

Пример
Для орграфов изменяется только матрица R.

c

Достижимость

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

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

Компоненты и бикомпоненты

Отношение «быть в одной компоненте » для ребер – эквивалентность,
как и для вершин.

Для ориентированных графов

Граф называется сильно связным, если он состоит из единственной
бикомпоненты.
Множество вершин, достижимых из вершины x, обозначим Д(x)
Теорема Вершины x и y взаимодостижимы тогда и только
тогда, когда Д(x) = Д(y).
⇒ Если x и y взаимодостижимы, то для любой вершины z∈V
ввиду транзитивности отношения взаимодостижимости,
из z∈ Д(x) следует z ∈Д(y), а из z ∈Д(y) следует z∈
Поэтому Д(x) = Д(y).
⇐ Пусть Д(x) = Д(y). Так как x∈ Д(x) и y ∈Д(y), то из равенства
Д(x) = Д(y) следует, что y ∈Д(x) и x∈ Д(y), т.е. вершины x и y
взаимодостижимы. 

Фрагмент программы выглядит так:
Пример (компоненты)
1
2
3
4
5
6
(**)

Пример (бикомпоненты, матрица достижимости)
1
2
3
5
4

Фрагмент программы:
for k=1 to n
for i=1 to n (***)
for j=1 to n
{r[i,j]:=r[i,j]∨r[i,k] ∧ r[k,j];}

Ахо А., Хопкрофт Д., Ульман Д. (стр. 194-195)
Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. — М. : Из-
дательский дом "Вильямс", 2000. — 384 с.
Алгоритм работает «на месте» -- матрица Rk записывается на месте матрицы R.

Пример (алгоритм Уоршалла)

Warshall Stephen (1935 – 2006)
https://en.wikipedia.org/wiki/Stephen_Warshall
Warshall carried out research and development in operating systems, compiler design, language design, and operations research.
Known for Floyd–Warshall algorithm

2.3. Кратчайшие цепи

Волновой алгоритм

1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
8
8
8
0
Пример 2. Волновой алгоритм прокладки проводов на плате (алгоритм Ли)

Взвешенный граф

Пример

Алгоритм Беллмана - Форда

+

0a
∞a
∞a
10 a
∞a
∞a
∞a
1 a
17b
12b
3 d
9 d
7 d
16 e
5 b
8 e
13 c
Пример

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

В таком представлении алгоритм Беллмана — Форда более пригоден
для «ручного» исполнения.
Пусть вершины пронумерованы V={1,2,…,n} и начальная вершина
s =1. Метка вершины L(x)=[l(x),p(x)], где l(x) – метка расстояния
i
j
k
Для нахождения кратчайших цепей/путей между всеми парами вер-шин нужно выполнить цикл по i.

Пример
1
2
3
4
⊗
=

БЕЛЛМАН, Ричард (1920- 1984) – «отец «динамического программирования» - американский математик. Опубликовал 619 статей и 39 книг. Один из наиболее цитируемых математиков в мире.
В расцвете творческой жизни после удаления опухоли на позвоночнике 11 лет был прикован к инвалидному креслу, но сохранил полную работоспособность .
ФОРД, Лестер младший (1927 - 2017) – американский математик. Независимо от Беллмана в 1956 г. предложил алгоритм нахождения кратчайшего пути в графе, вместе с Фалкерсоном доказал теорему о наибольшем потоке в сети.

Алгоритм Дейкстры

0a
∞a
∞a
∞a
∞a
∞a
10a
1a
3d
9d
7d
5b
8e
14e
13c

Иллюстрация работы алгоритма Дейкстры

в

Обобщения
1. Алгоритмы Беллмана – Форда и Дейкстры легко распространяются на случай ориентированных (частично ориентированных) графов, при этом каждое неориентированное ребро представляется двумя дугами, ориентированными в разные стороны. Более того, веса (длины) этих дуг могут быть различными.
2. В алгоритме Беллмана – Форда допускаются отрицательные веса ребер, такие постановки задачи иногда полезны в приложениях. Этим он принципиально отличается от алгоритма Дейкстры, где отрицательные веса невозможны. Но «всеядность» алгоритма Беллмана – Форда оплачивается его более высокой трудоемкостью.

ДЕЙКСТРА, Эдсгер (Edsger Dijkstra, 1930-2002). Нидерландский учёный, труды которого оказали большое влияние на развитие информатики; один из авторов языка Алгол и концепции структурного программирова-ния. По образованию физик-теоретик. Во второй половине 1950-х годов в поисках путей оптимизации разводки печатных плат разработал алгоритм поиска кратчайшего пути на графе.

Алгоритм Беллмана--Форда 2
(все пары вершин)

А. Шимбел предложил такую операцию умножения матриц:
суммирование заменяется на min,
умножение на арифметическое сложение

Элемент, например, матрицы будет
Это означает, что при при просмотре
троек вершин с
нашлась такая вершина , что путь
через нее на расстоянии 2
(по числу ребер) короче, чем путь
на расстоянии 1 (по ребрам) .

Алгоритм Флойда
Замечание. В алгоритме Флойда, так же как и в алгоритме Беллмана – Форда, нет ограничений на неотрицательность длин ребер, как будет показано в примере.

for i=1 to n
for j=1 to n
p[i,j]:=i;
Инициализация
Основной цикл
Алгоритм работает «на месте»: старые значения элементов матриц
C и P заменяются на новые; по завершению цикла по k (k=n)
C становится матрицей длин кратчайших цепей/путей, а P -- матрицей
самих цепей/путей.

Фрагмент программы:
for k=1 to n
for i=1 to n for j=1 to n
{ s:=c[i,k]+c[k,j];
if s
{c[i,j]:=s; p[i,j]:=p[k,j];}
}
c[i,j]:=min(c[i,j],c[i,k]+c[k,j])
k
(Флойд1)

4
4

4
4

-1
4
4

Замечание. Алгоритмы Беллмана – Форда и Флойда работают кор-
ректно, если в графе нет циклов отрицательной длины (сумма длин
которых отрицательна). В противном случае длина кратчайшей цепи/
пути уменьшается до -∞ (программа зацикливает). Это обнаруживается,
когда некоторые диагональные элементы становятся отрицательными.

ФЛОЙД, Роберт В (Robert W Floyd, 1936 – 2001) — американский учёный в области теории вычислительных систем. Лауреат премии Тьюринга. Роберт окончил школу в возрасте 14 лет, перепрыгнув три класса. Флойд не имел титула PhD.
В Стэнфорде Флойд тесно работал с Дональдом Кнутом, в том числе в качестве главного редактора серии его знаменитых книг «Искусство программирования».