Второй этап. Шаг 4. Полагаем
6
x
x
Пусть S
- множество вершин, непосредственно предшествующих
,
5 3
x
x
S
x
Первая итерация.
,
ω
3 3
0
,
,
ω
5 4
0
6 5
5 6
6 3
3 6
x
x
x
d
x
d
x
d
x
x
x
d
x
d
x
d
Включаем дугу
6 5
, x
x
в кратчайший путь.
5
x
x
Возвращаемся на четвертый шаг.
Вторая итерация.
?
s
x
Нет.
,
,
ω
7 4
3
,
,
5 3
3 5
4 3
2
x
x
x
d
x
d
x
d
x
x
x
S
,
,
ω
6 4
3
5 2
2 5
x
x
x
d
x
d
x
d
,
ω
9 4
3
5 4
4 5
x
x
x
d
x
d
x
d
Включаем дугу
5 3
, x
x
в кратчайший путь.
3
x
x
Возвращаемся на четвертый шаг.
Третья итерация.
?
s
x
Нет.
,
4 2
x
x
S
,
,
ω
7 4
4
3 2
2 3
x
x
x
d
x
d
x
d
,
ω
8 4
4
4 3
4 3
x
x
x
d
x
d
x
d
Включаем дугу
4 3
, x
x
в кратчайший путь.
4
x
x
Возвращаемся на четвертый шаг.
Четвертая итерация.
?
s
x
Нет.
,
2 1
x
x
S
,
,
ω
6 0
4
4 1
1 4
x
x
x
d
x
d
x
d
,
ω
8 4
4
4 2
2 4
x
x
x
d
x
d
x
d
Включаем дугу
4 2
, x
x
в кратчайший путь.
2
x
x
Возвращаемся на четвертый шаг.
Пятая итерация.
?
s
x
Нет.
1
x
S
,
ω
4 0
4
2 1
1 2
x
x
x
d
x
d
x
d
Включаем дугу
2 1
, x
x
в кратчайший путь.
1
x
x
Возвращаемся на четвертый шаг.
Шестая итерация.
?
s
x
Да. Задача закончена. Искомый кратчайший путь от вершины
1
x до вершины
6
x имеет нулевой вес и состоит из следующих дуг
,
,
,
,
,
6 5
5 3
3 4
4 2
2 1
x
x
x
x
x
x
x
x
x
x
3.12. Алгоритм нахождения максимального пути
Для нахождения максимального пути граф G (сеть) должен быть ациклическим, ибо в противном случае может оказаться, что длины некоторых путей не ограничены сверху.
Если
n
G - ациклический граф, то для любых двух его вершин
j
i
x
x
выполняется одно из трех условий:
1)
i
x предшествует
j
x
,
j
предш
i
x
S
x
;
2)
i
x следует за
j
x
,
j
след
i
x
S
x
;
3) нет пути между
i
x и
j
x
Первое и второе условия одновременно не выполнимы из-за требуемой ацикличности графа.
Перед вычислением максимального пути в орграфе необходимо упорядочить вершины графа по алгоритму Фалкерсона. Сам алгоритм вычисления максимального пути чисто перечислительный. Он перебирает все возможные пути от текущей вершины до всех последующих вершин, достижимых из текущей вершины.
71
Пусть
j
d
- длина максимального пути от вершины
1
x до вершины
j
x
, тогда величина
j
d
удовлетворяет следующим рекуррентным соотношениям:
n
k
k
j
d
k
j
x
S
x
d
d
d
j
j
предш
i
ij
i
j
,...,
3
,
2
,
,
1
,...,
3
,
2
,
ω
max
,
0 1
(3.12.1)
Соотношения (3.12.1) позволяют легко вычислить длины максимальных путей от
1
x
s
до вершин, достижимых из вершины s . Сами пути могут быть построены методом последовательного возвращения (второй этап в алгоритме Дейкстры).
Пример 1. Граф (сеть, см. рис. 3.31) задан матрицей весов. Найти длину максимального пути из вершины
1
x в
6
x и сам этот путь.
2
x 8 4
x
4 6 6 9 6
x
1
x 7 8 5 3 3
x 7 5
x
Рис. 3.31.
Этот граф ациклический, поэтому возможно упорядочение его вершин по алгоритму
Фалкерсона. Сделаем это графическим способом.
/
3
x
/
4
x
6 2
x
4
x 9 3
x
5
x
1
x 4 8 8 7 3 6
x
7 5
I II III 6 IV V VI группы
Рис. 3.32.
Переобозначим две вершины:
4
x назовем
/
3
x
, а
3
x -
/
4
x и применим рекуррентные формулы (3.12.1). Тогда
Этап 1.
0 1
d
,
4 4
max
1 2
d
d
,
12 8
4
,
6 0
max
8
,
6
max
2 1
/
3
d
d
d
,
20 7
4
,
8 12
max
7
,
8
max
2
/
3
/
4
d
d
d
,
27 6
4
,
9 12
,
7 20
max
6
,
9
,
7
max
2
/
3
/
4 5
d
d
d
d
,
30 5
20
,
3 27
max
5
,
3
max
/
4 5
6
d
d
d
Итак, длина максимального пути из
1
x в
6
x равна 30.
Этап 2.
6
x :
3 27 3
30 5
6
d
d
- включаем дугу
6 5
, x
x
в максимальный путь,
5 20 5
30
/
4 6
d
d
5
x :
7 20 7
27
/
4 5
d
d
- включаем дугу
5
/
4
, x
x
в максимальный путь,
9 12 9
27
/
3 5
d
d
,
6 4
6 27 2
5
d
d
/
4
x :
8 12 8
20
/
3
/
4
d
d
- включаем дугу
/
4
/
3
, x
x
в максимальный путь,
7 4
7 20 2
/
4
d
d
3 9
8 5
7 6
8 7
6 4
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
72 / 3 x: 8 4 8 12 2 / 3 dd - включаем дугу / 3 2 , xx в максимальный путь, 6 0 6 12 1 / 3 dd2 x : 4 0 4 4 1 2 dd - включаем дугу 2 1 , xx в максимальный путь. Итак, искомый путь таков: 6 5 5 / 4 / 4 / 3 / 3 2 2 1 max , , , , , μ xxxxxxxxxx или в старых обозначениях 6 5 5 3 3 4 4 2 2 1 max , , , , , μ xxxxxxxxxx 3.13. Особенности алгоритмов теории графов Рассмотрение предыдущих задач позволяет сформулировать следующие свойства алгоритмов теории графов. 1) Каждый алгоритм состоит из совокупности конечного числа правил и предписаний. Действия над графом (матрицей), производимые в соответствии с правилами, должны быть достаточно просты. 2) Применение алгоритма совершается в дискретном времени; правила алгоритма применяются по шагам, число шагов – конечно. 3) Какое из правил будет применено на данном шаге или какое действие будет совершено в соответствии с некоторым правилом зависит только от результатов предыдущих шагов. 4) Алгоритмы обладают свойством локальности: действие в соответствии с правилом или установление непротиворечивости некоторого действия правилам алгоритма происходит на основе анализа дуг, инцидентных данной вершине, или вершин, смежных с данной. 5) Алгоритмы обладают свойством массовости: применяются либо для всех, либо для некоторого бесконечного множества графов. 3.14. Практическое занятие № 7. Нахождение минимальных и максимальных путей на орграфах 3.14.1. По заданной матрице весов графа G найти величину минимального пути и сам путь от вершины 1 xs до вершины 6 xt или 7 xt по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами: 1) - 9 - 10 8 - 6 3 5 - 13 9 8 - 13 10 5 - 6 5 4 3 2 1 6 5 4 3 2 1 xxxxxxxxxxxx 2) - 14 - 10 11 9 - 11 7 13 - 13 - 15 14 11 - 6 5 4 3 2 1 6 5 4 3 2 1 xxxxxxxxxxxx 3) - 11 - 8 7 6 - 12 10 17 - 11 - 18 7 8 5 - 6 5 4 3 2 1 6 5 4 3 2 1 xxxxxxxxxxxx4) - 9 - 7 6 - 11 4 7 - 8 15 7 9 - 10 11 8 6 - 6 5 4 3 2 1 6 5 4 3 2 1 xxxxxxxxxxxx 5) 19 23 8 16 11 22 11 7 13 9 18 14 7 15 11 7 6 5 4 3 2 1 7 6 5 4 3 2 1 xxxxxxxxxxxxxx 6) - 8 - 3 4 - 16 4 3 - 3 14 3 - 9 6 5 - 6 5 4 3 2 1 6 5 4 3 2 1 xxxxxxxxxxxx
73 7)
-
8
-
6 4
7
-
6 5
-
6 13 6
-
11 9
7
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
8)
-
18
-
15 14 13 17
-
21 19
-
16 7
-
14 15 7
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
9)
-
6
-
10 11
-
13 10
-
19 9
11
-
12 10
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
10)
14 15 5
13 8
8 16 9
6 6
11 15 20 19 7
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11)
-
5
-
3 5
-
11 3
1
-
2 6
-
13 2
7
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
12)
-
9
-
7
-
15 6
5
-
17 11 8
13
-
6 11 10
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
13)
-
10
-
5 7
14 6
-
8 4
6
-
6
-
12 9
6
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
14)
-
3
-
2 6
-
4 2
3
-
2
-
8 9
4
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
15)
9 8
21 13 6
14 11 6
5 9
4 7
12 8
10 5
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
16)
-
8
-
9 8
-
15 6
-
6 9
5
-
12 13 9
6
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
17)
-
11
-
13 9
-
7 12 10
-
12 9
10
-
10 8
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
18)
-
14
-
11 12
-
20 16 11
-
15 10 8
-
14 11
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
19)
-
12
-
10 8
-
7 6
-
5 15
-
13 7
9
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
20)
4 18 5
7 5
7 6
3 4
10 5
11 9
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
21)
-
7
-
5 2
4
-
3 4
-
3 10 3
-
8 4
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
22)
-
10
-
4 8
-
8 5
-
6 13 8
-
10 4
5
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
23)
-
12
-
6 11
-
10 7
-
8 15 7
10
-
11 10 12
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
24)
-
14
-
11 13
-
19 12 9
-
10 18 12
-
10 15
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
74 25)
6 9
5 8
4 6
5 4
5 13 6
10 12 7
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
26)
-
10
-
17 9
-
8 7
6
-
12 7
9
-
13 8
7
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
27)
-
8
-
6
-
18 7
6
-
5 3
11
-
11 10 5
4
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
28)
-
3
-
5 5
11 5
-
6 4
8
-
7
-
10 5
8
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
29)
-
3
-
7 5
-
12 6
5
-
8 8
6 4
-
3
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
30)
8 11 3
8 7
6 4
15 9
8 4
5 3
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
3.14.2. По заданной матрице весов
графа G найти минимальный путь по алгоритму Беллмана – Мура между начальной вершиной
1
x
s
и конечной вершиной
6
x
t
или
7
x
t
:
1)
6 5
5 9
7 10 3
2 4
2 6
4 10 12 15 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
2)
3 10 6
4 6
8 5
6 4
11 5
5 7
3 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
3)
3 5
3 11 8
4 4
7 6
3 2
10 4
2 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
4)
5 6
12 9
4 5
10 6
7 4
10 7
8 3
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
5)
-
7
-
6 8
-
5 6
-
7 10
-
11 7
8
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
6)
5 8
12 6
9 7
4 6
5 13 11 5
8 7
3 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
7)
6 5
12 5
3 10 7
8 10 3
11 6
14 7
4 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
8)
5 8
4 8
6 7
12 3
10 7
5 9
6 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
9)
5 8
6 10 7
3 7
4 4
12 10 6
8 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
75 10)
-
7
-
5 4
-
6
-
5 6
7 6
-
5 11 6
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
11)
6 7
18 16 7
6 10 4
7 9
5 8
15 4
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12)
6 8
15 5
7 6
9 5
13 5
3 16 12 6
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13)
6 21 7
5 8
10 9
8 7
7 18 15 5
10 11 3
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
14)
6 11 5
14 5
4 12 7
9 8
6 11 10 9
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
15)
-
8
-
9
-
2 4
3
-
10 9
13
-
8 7
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
16)
4 6
7 13 6
5 6
3 4
10 5
8 7
3 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
17)
6 16 7
5 8
7 10 4
20 18 11 5
15 6
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
18)
8 5
7 7
9 8
6 6
4 5
6 5
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
19)
6 18 4
9 5
6 5
8 7
11 7
6 15 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
20)
-
4
-
2 7
5
-
10 8
5
-
4 6
-
9 6
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
21)
8 8
27 16 5
12 9
17 5
15 8
12 5
11 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
22)
11 8
9 5
9 8
7 4
6 7
22 9
15 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
23)
4 13 7
7 11 9
8 5
8 12 6
10 4
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
24)
7 15 4
9 7
3 8
8 6
4 9
3 6
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
25)
-
6
-
5 8
10
-
4 6
8
-
9
-
6 7
-
6 5
4 3
2 1
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
26)
5 7
8 15 5
10 4
8 4
6 13 10 7
9 5
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
27)
5 6
7 12 7
9 10 4
13 8
6 15 5
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
76 28) 6 16 7 11 5 13 8 10 7 10 6 15 12 7 6 5 4 3 2 1 7 6 5 4 3 2 1 xxxxxxxxxxxxxx 29) 5 7 8 6 11 7 8 6 4 15 10 4 12 6 7 6 5 4 3 2 1 7 6 5 4 3 2 1 xxxxxxxxxxxxxx 30) - 6 - 4 8 - 6 3 - 4 8 - 9 5 7 - 6 5 4 3 2 1 6 5 4 3 2 1 xxxxxxxxxxxx |
Скачать 6.37 Mb.