Связность графов. Маршруты, цепи, циклы

Содержание

Слайд 2

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

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

Слайд 3

 

Маршруты

Маршруты

Слайд 4

Цепи и циклы

 

Цепи и циклы

Слайд 5

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

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

Доказательство

 

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

Слайд 6

Пример

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

Пример Маршрут a 1 b 2 c 3 d 4 b 5
содержит простую цепь a 1 b 5 e.

Следствие Всякий кратчайший маршрут между двумя заданными вершинами графа есть простая цепь.
Всякий цикл наименьшей длины при заданной вершине является простым.

Слайд 7

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

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

ориентированный маршрут (ормаршрут);
ориентированная цепь (орцепь) – путь;
простая орцепь – простой путь.

Слайд 8

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

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

Слайд 9

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

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

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

Такой граф можно рассматривать как симметричное бинарное отношение и его можно задать матрицей смежности R, элементы rij которой – булевы. rij=1, если вершины смежны; из вершины xi существует маршрут длины 1 в вершину xj.

Элемент матрицы R2

 

определяет существование

маршрута длины 2 между этими вершинами. Далее по индукции:

 

(*)

Слайд 10

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

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

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

Слайд 11

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

 

Длина 1

a1a
a2b
b2a
b3c
b4c
c3b
c4b

Длина 2

a1a1a
a1a2b
a2b2a
a2b3c
a2b4c
b2a1a
b2a2b
b3c3b

Длина 3

 

 

Нахождение маршрутов Длина 1 a1a a2b b2a b3c b4c c3b c4b Длина

Слайд 12

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

 

 

 

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

Слайд 13

 

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

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

Далее по индукции.

Здесь сложение и умножение – обычные арифметические
операциии.

Слайд 14

Пример

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

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

Слайд 16

 

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

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

Слайд 17

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

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

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

Слайд 18

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

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

Слайд 19

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

 

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

Слайд 20

 

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

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

Слайд 21

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

 

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

Слайд 22

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

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

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

Слайд 25

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

Пример (компоненты)

1

2

3

4

5

6

(**)

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

Слайд 27

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

 

 

1

2

3

5

4

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

Слайд 28

 

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

Фрагмент программы: 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];}

 

Слайд 29

 

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

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

Алгоритм работает «на месте» -- матрица Rk записывается на месте матрицы R.

Слайд 30

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

 

 

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

Слайд 31

Warshall Stephen (1935 – 2006)

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

Warshall carried out research and development in operating

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

Слайд 32

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

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

Слайд 33

 

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

 

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

Слайд 35

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. Волновой алгоритм прокладки проводов на плате (алгоритм Ли)

1 1 1 1 1 1 1 1 2 2 2 2

Слайд 36

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

 

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

Слайд 37

Пример

 

 

Пример

Слайд 38

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

 

 

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

Слайд 42

0a

∞a

∞a

10 a

∞a

∞a

∞a

1 a

17b

12b

3 d

9 d

7

0a ∞a ∞a 10 a ∞a ∞a ∞a 1 a 17b 12b
d

16 e

5 b

8 e

 

13 c

Пример

Слайд 43

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

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

Иллюстрация работы алгоритма Форда

Слайд 44

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

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

i

j

k

 

 

 

 

Для нахождения кратчайших цепей/путей между всеми парами вер-шин нужно выполнить цикл по i.

Слайд 45

Пример

1

2

3

4


=

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

Слайд 46

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

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

ФОРД, Лестер младший (1927 - 2017) – американский математик. Независимо от Беллмана в 1956 г. предложил алгоритм нахождения кратчайшего пути в графе, вместе с Фалкерсоном доказал теорему о наибольшем потоке в сети.

Слайд 47

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

 

 

 

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

Слайд 50

0a

∞a

∞a

∞a

∞a

∞a

10a

1a

3d

9d

7d

5b

8e

14e

13c

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

Слайд 51

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

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

Слайд 53

Обобщения

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

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

Слайд 54

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

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

Слайд 55

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

 

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

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

Слайд 56

 

 

 

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

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

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

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

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

Слайд 57

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

Фрагмент программы: for k=1 to n for i=1 to n for j=1
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)

Слайд 61

 

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

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

Слайд 63

ФЛОЙД, Роберт В  (Robert W Floyd, 1936 – 2001) — американский учёный в области теории

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