Теория графов. 02 Теория графов. 2. теория графов общие понятия теории графов

• Название: 2. теория графов общие понятия теории графов
• Анкор: Теория графов
• Дата: 30.09.2022
• Размер: 1.41 Mb.
• Имя файла: 02 Теория графов.pdf
• Тип: Документы; #706797
• страница: 6 из 8

Замечания
Множество
)
(v
FW
k
называется фронтом волны k-го уровня.
Вершины
1 3
2 1
−
k
w
w
w
w
могут быть выделены неоднозначно, что соответствует случаю, если существует несколько минимальных путей из v в w.
Пример
Найдем расстояния в орграфе D (рис.
2.35). n
=
7, значит, матрицы A(D) и M(D)будут иметь размерность 7×7.
Рис. 2.35. Пример орграфа для нахождения метрических характеристик и минимального расстояния
Матрица смежности:






















=
0 0
1 1
0 0
0 1
0 1
0 0
0 0
0 0
0 1
1 1
1 1
0 0
0 0
0 0
0 0
0 1
0 0
0 0
0 0
0 1
0 1
0 1
0 0
0 1
0
)
(D
A
Начинаем заполнять матрицу M(D): ставим нули по главной диагоналии m
ij
=
a
ij
, если a
ij
=
1, (т.
е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы,

49 т.
е. из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью
(путь в первую вершину нас не интересует), следовательно, необходимо записать m
13
=
2. Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит, m
15
=
2, m
17
=
2. Подобным образом находим все пути за 2 шага и расставляем все двойки в матрицу M(D).
Теперь ищем маршруты, исходящие из первой вершины, состоящие из трех шагов: за два шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому m
14
=
3. Заполняем все тройки, затем четверки и т. д., пока не заполним всю матрицу M(D).
В итоге получим следующую матрицу:






















=
0 3
1 1
2 2
2 1
0 1
2 2
2 2
2 2
0 1
1 1
1 1
4 2
0 3
3 3
2 5
3 1
0 4
4 3
2 3
2 1
0 1
2 1
2 3
2 1
0
)
(D
M
Согласно формулам подглавы 2.5 и матрице M(D) диаметр орграфа равен
5
)
,
(
max
)
(
,
=
=
∈
w
v
d
D
d
V
w
v
Для каждой вершины орграфа по матрице M(D) найдем максимальное удаление (эксцентриситет) от данной вершины с помощью формулы
)
,
(
max
)
(
w
v
d
v
r
i
V
w
i
∈
=
: r(v
i
) – максимальное из расстояний, стоящих в i-й строке. Имеем
r(v
1
)
=
3, r(v
2
)
=
3, r(v
3
)
=
5, r(v
4
)
=
4, r(v
5
)
=
2, r(v
6
)
=
2, r(v
7
)
=
3.
Значит, радиусорграфа равен
2
)
(
min
)
(
=
=
∈
v
r
G
r
V
v
Соответственно, центрами орграфабудут вершины v
5
и v
6
, так как величины их эксцентриситетов совпадают с величиной радиуса
)
(D
r
Опишем теперь нахождение минимального пути между наиболее удаленными вершинами (из вершины v
3
в вершину v
6
) по

50 алгоритму фронта волны. Обозначим вершину v
3
как V
0
, а вершину v
6
− как W (рис.
2.36).
Множество вершин, принадлежащих образу V
0
, состоит из одного элемента − это вершина v
4
, которую, согласно алгоритму, обозначаем как V
1
: FW
1
(v
3
)
=
{v
4
}.
Рис. 2.36. Применение алгоритма фронта волны для нахождения минимального пути в орграфе
Поскольку искомая вершина не принадлежит фронту волны первого уровня
)
(
3 1
6
v
FW
v
W
∉
=
, то продолжаем работу алгоритма.
Строим фронт волны второго уровня − это множество вершин, принадлежащих образу вершины V
1
: FW
2
(v
3
)
=
{v
7
}, обозначаем
v
7
≡
V
2
. В образ вершины V
2
входят две вершины − v
5
и v
4
, но так как
v
4
уже была помечена как V
1
, то фронт волны третьего уровня состоит из одного элемента: FW
3
(v
3
)
=
{v
5
}, v
5
≡
V
3
. Из непомеченных вершин в образ вершины V
3
входят v
1
и v
2
, соответственно, FW
4
(v
3
)
=
{v
1
, v
2
},
v
1
≡
V
4
, v
2
≡
V
4
Теперь помечены все вершины, кроме v
6
, которая входит в образ вершины
( )
3 4
1
v
FW
v ∈
, т.
е. FW
5
(v
3
)
=
{v
6
≡
W}, работа алгоритма закончена.
Минимальный путь (5 шагов) из вершины v
3
в вершину v
6
:
v
3
v
4
v
7
v
5
v
1
v
6
2.7.3. Минимальный путь в нагруженном орграфе
1) Найти минимальный путь в нагруженном орграфе из вершины
2
v в вершину
6
v по алгоритму Форда–Беллмана.
Рассмотрим сначала общую задачу – нахождение минимального пути из вершины v
нач в v
кон
Пусть D = (V,
X) – нагруженный орграф, V = {v
1
,…,v
n
}, n > 1.
Введем величины
( )
k
i
λ
, где i = 1,…,n, k = 0,1,2,…,n – 1.

51
Для каждого фиксированного i и k величина
( )
k
i
λ
равна длине минимального пути среди путей из v
нач в v
i
, содержащих не более
k дуг. Если путей нет, то
( )
∞
=
λ
k
i
Положим также
( )
( )
нач
0 0
нач остальных для
,
0
v
v
i
i
≠
∞
=
λ
=
λ
Составляем матрицу длин дуг C(D) = [c
ij
] порядка n:
(
) (
)
(
)



∉
∞
∈
=
,
,
,
,
,
,
X
v
v
X
v
v
v
v
l
c
j
i
j
i
j
i
ij
Утверждение
При i = 2,…,n, k
≥
0 выполняется равенство
(
)
( )
{
}
ji
k
j
n
j
k
i
c
+
λ
=
λ
≤
≤
+
1 1
min
Алгоритм Форда–Беллмана
( )
k
i
λ
записываем в виде матрицы, i – строка, k – столбец.
1. Составляем таблицу
( )
k
i
λ
, i = 1,…,n, k = 0,…,n – 1. Если
(
)
∞
=
λ
−1
кон
n
, то пути из v
нач в v
кон нет. Конец алгоритма.
2. Если
(
)
∞
<
λ
−1
кон
n
, то это число выражает длину любого минимального пути из v
нач в v
кон
. Найдем минимальное k
1
≥
1, при котором
( )
(
)
1 1
−
λ
=
λ
n
i
k
i
. По определению
( )
k
i
λ
получим, что k
1
– минимальное число дуг в пути среди всех минимальных путей из
v
нач в v
кон

52
Затем определяем номера i
2
,…,
1 1
+
k
i
такие, что
(
)
( )
1 2
1 2
,
1
k
i
i
i
k
i
c
λ
=
+
λ
−
,
(
)
(
)
1
,
2 1
2 2
3 1
3
−
−
λ
=
+
λ
k
i
i
i
k
i
c
,
K
K
K
K
K
K
K
( )
( )
1
,
0 1
1 1
1 1
1
k
k
k
k
i
i
i
i
c
λ
=
+
λ
+
+
, т.
е. восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из v
нач в v
кон
Заметим, что алгоритм Форда–Беллмана позволяет найти минимальные пути из заданной вершины во все остальные.
Пример
Найдем минимальный путь из вершины v
2
в v
6
в нагруженном орграфе D (рис.
2.37). n = 7, следовательно, матрица длин дуг графа D будет иметь размерность 7×7.
Рис. 2.37. Пример нагруженного орграфа для алгоритма Форда
–
Беллмана
Матрица длин дуг для данного графа:






















∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
=
5 17 6
4 7
3 2
13 7
9 1
6 12 15 8
11 1
)
(D
C

53
Согласно алгоритму составляем таблицу стоимости минимальных путей из вершины v
2
в вершину v
i
не более чем за
k шагов, k = 0,…n – 1 (n = 7, следовательно, k = 0,…6).
Как было определено выше,
( )
0 0
2
=
λ
, и
( )
∞
=
λ
0
i
для всех остальных вершин v
i
≠ v
2
, т.
е. первый столбец таблицы состоит из элементов, равных
∞
, кроме элемента
( )
0 0
2
=
λ
Второй столбец таблицы повторяет вторую строку матрицы стоимости, поскольку представляет собой стоимость возможных путей из вершины v
2
за один шаг. Далее по формуле утверждения 8 находим по столбцам все оставшиеся элементы таблицы. Например, чтобы найти элемент
( )
2 1
λ
, складываем элементы столбца
( )
1
i
λ
и первого столбца матрицы стоимости и выбираем минимальное из получившихся чисел:
( )
{
}
15
,
7
,
,
,
12
,
15 0
,
15
min
2 1
=
∞
+
∞
+
∞
∞
+
∞
∞
+
∞
∞
+
+
∞
+
=
λ
В конечном итоге получаем следующую таблицу:
16 16 16 16 21 21 21 23 23 13 13 13 13 13 18 18 18 18 18 12 12 12 12 12 12 0
0 0
0 0
0 0
15 15 15 15 15 15 7
6 5
4 3
2 1
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
)
0
(
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
λ
λ
λ
λ
λ
λ
λ
v
v
v
v
v
v
v
i
i
i
i
i
i
i
Теперь необходимо по построенной таблице и матрице C(D) восстановить минимальный путь из вершины v
2
в v
6
, который будет строиться с конца, т.
е. начиная с вершины v
6
. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v
6
в таблице. Это число 21 – длина минимального искомого пути.
В первый раз такая длина была получена при количестве шагов, равном 4.
В вершину v
6
можно попасть за один шаг из вершин v
1
и v
7
(длины соответствующих дуг 8 и 5, соответственно, – данные из матрицы C(D)). Выбираем минимальную по длине из этих дуг. Далее,

54 в вершину v
7
можно попасть из v
4
и v
5
(длины соответствующих дуг 7 и 3 соответственно). Продолжая аналогичным образом, найдем искомый путь за четыре шага минимальной длины из вершины v
2
в вершину v
6
:
v
2
v
3
v
5
v
7
v
6 2) Найти все минимальные пути из вершины
2
v нагруженного орграфа по алгоритму Дейкстры.
Алгоритм Дейкстры в отличие от алгоритма Форда–Беллмана не допускает ребра с отрицательным весом и также решает задачу о кратчайших путях из одной вершины v
нач во все оставшиеся для нагруженного орграфа D = (V,X), V = {v
1
,…,v
n
}, n > 1. Пусть в общем случае необходимо определить минимальный путь из v
нач в v
z
Алгоритм Дейкстры
1. Каждой вершине из множества V в ходе реализации алгоритма присваивается число d(v
i
), равное длине кратчайшего пути из вершины v
нач в вершину v
i
и включающем только пройденные вершины. Полагается d(v
нач
) = 0 и d(v
i
) = ∞ для всех остальных вершин графа. Проходится вершина v
нач и полагается v
j
= v
нач
, где
v
j
– последняя пройденная вершина.
2. Для каждой непройденной вершины v
i
пересчитывается величина
d(v
i
) по формуле:
d(v
i
) = min{d(v
i
); d(v
j
) +
(
)
i
j
v
v
l
,
}.
3. Если d(v
i
) = ∞ для всех непройденных вершин, то алгоритм заканчивается, так как отсутствуют пути из вершины v
нач в непройденные вершины. Иначе обозначается пройденной та вершина, для которой величина d(v
i
) является минимальной.
Обозначается и дуга, инцидентная этой вершине, в соответствии с формулой шага 2, и полагается v
j
= v
i
4. Если v
j
= v
z
, то кратчайший путь из v
нач в v
z
найден. Иначе переходим к шагу 2.
Пример
Найдем все минимальные пути из вершины v
2
в нагруженном орграфе D (рис.
2.38).

55
Рис. 2.38. Пример нагруженного орграфа для алгоритма Дейкстры
В графе семь вершин, следовательно, матрица длин дуг будет подобна предыдущему случаю:






















∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
=
5 6
2 3
2 13 7
6 12 1
8 11
)
(D
C
Согласно алгоритму зададим начальные условия: d(v
2
) = 0,
d(v
i
) = ∞. Проходим вершину v
2
, v
j
= v
2
. Находим ближайшую вершину к пройденной, используя формулу:
d(v
i
) = min{d(v
i
); d(v
j
) + l(v
j
, v
i
)}:
d(v
1
) = min{d(v
1
); d(v
2
) + l(v
2
, v
1
)} = min{∞; 0 + 1} = 1;
d(v
3
) = min{d(v
3
); d(v
2
) + l(v
2
, v
3
)} = min{∞; 0 + 12} = 12;
d(v
4
) = min{d(v
4
); d(v
2
) + l(v
2
, v
4
)} = min{∞; 0 + ∞} = ∞;
d(v
5
) = min{d(v
5
); d(v
2
) + l(v
2
, v
5
)} = min{∞; 0 + ∞} = ∞;
d(v
6
) = min{d(v
6
); d(v
2
) + l(v
2
, v
6
)} = min{∞; 0 + ∞} = ∞;
d(v
7
) = min{d(v
7
); d(v
2
) + l(v
2
, v
7
)} = min{∞; 0 + ∞} = ∞.
Минимальную длину имеет путь от вершины v
2
до вершины v
1
d(v
1
) = 1. Включаем вершину v
1
в текущее ориентированное дерево, а также дугу, инцидентную этой вершине. Согласно выражению это дуга (v
2
,v
1
). Далее повторяем процедуру, исключая вершину v
1
, теперь v
j
= v
1

56
d(v
3
) = min{d(v
3
); d(v
1
) + l(v
1
, v
3
)} = min{12; 1 + 12} = 12;
d(v
4
) = min{d(v
4
); d(v
1
) + l(v
1
, v
4
)} = min{∞; 1 + ∞} = ∞;
d(v
5
) = min{d(v
5
); d(v
1
) + l(v
1
, v
5
)} = min{∞; 1 + 11} = 12;
d(v
6
) = min{d(v
6
); d(v
1
) + l(v
1
, v
6
)} = min{∞; 1 + 8} = 9;
d(v
7
) = min{d(v
7
); d(v
1
) + l(v
1
, v
7
)} = min{∞; 1 + ∞} = ∞.
Минимальную длину имеет путь от вершины v
1
до вершины v
6
d(v
6
) = 9. Включаем вершину v
6
в текущее ориентированное дерево, а также дугу (v
1
,v
6
), инцидентную этой вершине. Далее повторяем процедуру, исключая вершину v
6
, теперь v
j
= v
6
d(v
3
) = min{d(v
3
); d(v
6
) + l(v
6
, v
3
)} = min{12; 9 + ∞} = 12;
d(v
4
) = min{d(v
4
); d(v
6
) + l(v
6
, v
4
)} = min{∞; 9 + ∞} = ∞;
d(v
5
) = min{d(v
5
); d(v
6
) + l(v
6
, v
5
)} = min{12; 9 + 2} = 11;
d(v
7
) = min{d(v
7
); d(v
6
) + l(v
6
, v
7
)} = min{∞; 9 + ∞} = ∞.
Подобным образом получаем, что v
j
= v
5
, d(v
5
) = 11.
d(v
3
) = min{d(v
3
); d(v
5
) + l(v
5
, v
3
)} = min{12; 11 + 2} = 12;
d(v
4
) = min{d(v
4
); d(v
5
) + l(v
5
, v
4
)} = min{∞; 11 + ∞} = ∞;
d(v
7
) = min{d(v
7
); d(v
5
) + l(v
5
, v
7
)} = min{∞; 11 + 3} = 14.
Теперь v
j
= v
3
, d(v
3
) = 12.
d(v
4
) = min{d(v
4
); d(v
3
) + l(v
3
, v
4
)} = min{∞; 12 + 6} = 18;
d(v
7
) = min{d(v
7
); d(v
3
) + l(v
3
, v
7
)} = min{14; 12 + 3} = 14.
Далее v
j
= v
7
, d(v
7
) = 14.
d(v
4
) = min{d(v
4
); d(v
7
) + l(v
7
, v
4
)} = min{18; 14 + ∞} = 18.
И последнее v
j
= v
4
, d(v
4
) = 18.
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине v
2
для исходного графа
d(v
1
) = 1, путь v
2
v
1
;
d(v
2
) = 0, путь v
2
;
d(v
3
) = 12, путь v
2
v
3
;
d(v
4
) = 18, путь v
2
v
3
v
4
;
d(v
5
) = 11, путь v
2
v
1
v
6
v
5
;
d(v
6
) = 9, путь v
2
v
1
v
6
;
d(v
7
) = 14, путь v
2
v
1
v
6
v
5
v
7

57
Рис. 2.39. Ориентированное дерево кратчайших путей из вершины v
2