Связность графов

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

Маршруты

Цепи и циклы

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

Пример

Маршрут a 1 b 2 c 3 d 4 b 5

Если маршрут рассматривать с учетом ориентации ребер (может быть и по

Задачи о маршрутах
В теории рассматривается ряд задач и алгоритмов определения

Существование маршрутов

Рассматривается неориентированный (маршрут не предполагает ориентации) униграф (важен лишь факт

и вершины xk и xj смежны.

Для маршрутов других видов задаются соответствующие

Нахождение маршрутов

Зададим граф общего вида тройками вида (x,v,y), где x,y∈V, v

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

Число различных маршрутов длины 2 из вершины xi в вершину xj

Пример

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

c

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

Ориентированные маршруты

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

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

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

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

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

Множество вершин, достижимых из вершины x, обозначим Д(x).

Теорема Вершины x и

Алгоритм работает «на месте» -- матрица Rl+1 записывается на месте матрицы

Фрагмент программы выглядит так:

Пример (для компонент)

(**)

1

2

3

5

4

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

Фрагмент программы:
for k=1 to n
for i=1 to n (***)

Ахо А., Хопкрофт Д., Ульман Д. (стр. 194-195)
Структуры данных и алгоритмы.

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

Warshall Stephen (1935 – 2006)

https://en.wikipedia.org/wiki/Stephen_Warshall

Warshall carried out research and development in

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

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

0

1

2

3

3

4

4

5

6

7

Пример 1. Задача о Волке, Козе (Кз) и Капусте (Кп), которых

https://www.youtube.com/watch?v=YDX-ohCVtxY

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

∞b

∞c

10 a

∞f

∞d

∞e

1 a

17b

12b

3 d

9

Если метка у вершины не меняется, клетка в следующей строке данного

В таком представлении алгоритм Беллмана — Форда более пригоден
для «ручного» исполнения.

Пример

1

2

3

4

⊗

БЕЛЛМАН, Ричард (1920- 1984) – «отец «динамического программирования» - американский математик.

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

0a

∞b

∞c

∞d

∞e

∞f

10a

1a

3d

9d

7d

5b

8e

14e

13c

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

Обобщения

1. Алгоритмы Беллмана – Форда и Дейкстры легко распространяются на случай

ДЕЙКСТРА, Эдсгер (Edsger Dijkstra; 1930-2002). Нидерландский учёный, труды которого оказали большое

Алгоритм Флойда

Замечание. В алгоритме Флойда, так же как и в алгоритме

for i=1 to n
for j=1 to n
p[i,j]:=i;

Инициализация

Основной цикл

Алгоритм работает «на месте»:

Фрагмент программы:
for k=1 to n
for i=1 to n

4

4

4

4

-1

4

4

Замечание. Алгоритмы Беллмана – Форда и Флойда работают кор-
ректно, если в