2569
.pdfЗамкнутый маршрут, в котором попарно различны все вершины, кроме первой и последней, называется простым циклом (рис. 50) в неорграфе и про-
стым контуром (рис. 51) в орграфе.
υ2 |
2 |
υ3 |
υ2 |
2 |
υ3 |
1 |
3 |
1 |
3 |
5 |
|
4 |
|
5 |
4 |
υ1 |
υ5 |
υ4 |
υ1 |
υ5 |
υ4 |
Рис. 50. Простой цикл |
Рис. 51. Простой контур |
8.2.Выявление маршрутов в графе заданной длины
Спомощью матрицы смежности можно найти в графе маршруты заданной длины. Это отражено в следующей теореме.
Теорема 8.1. Если В – матрица смежности графа G без петель, то элемент
βij матрицы BK ( K N ) равен количеству маршрутов длины К от вершины υi к вершине υj .
Пример 8.1. Вычислить количество циклических маршрутов длины 3 в графе, изображённом на рис. 52, и показать их.
υ1
υ2 υ5
υ4υ3
Рис. 52. Неорграф
41
Решение. Составим матрицу смежности данного неорграфа.
|
υ1 |
υ2 |
υ3 υ4 |
υ5 |
|
|||
υ1 |
|
0 |
1 |
|
0 |
0 |
0 |
|
υ2 1 0 0 1 |
1 |
|||||||
B5×5 =υ3 |
0 |
0 |
|
0 |
1 |
1 . |
||
υ4 |
0 |
1 |
1 |
0 1 |
||||
υ |
|
0 |
1 |
|
1 |
1 |
0 |
|
5 |
|
|
|
|
|
|
|
|
Для того чтобы найти все маршруты в графе длины 3, необходимо его матрицу смежности возвести в третью степень, т.е. найти B3 = B B B .
Сначала вычислим B2 :
|
|
0 1 |
0 0 0 0 1 |
0 0 0 1 0 0 1 1 |
|
|||||||||||||||||||
B2 |
|
1 0 0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 3 2 1 1 |
|
|||||||||||||
= B B = |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
= |
0 2 2 |
1 |
1 |
, |
||||||||
|
|
|
0 |
1 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 1 |
|
1 1 1 3 |
2 |
|
||||||||
|
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 1 1 |
2 3 |
|
||||||||||
а затем B3 : |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
1 |
0 0 1 1 0 1 |
0 |
0 0 0 |
3 |
2 |
1 1 |
|
|||||||||||||||
B3 |
= B2 |
0 3 2 1 1 |
1 0 0 1 1 |
3 |
2 |
2 |
6 |
6 |
|
|||||||||||||||
B = |
0 2 2 1 1 |
|
0 0 0 1 1 |
= |
2 |
2 |
2 |
5 |
5 . |
|||||||||||||||
|
|
|
1 |
1 1 3 2 |
|
0 1 |
1 |
0 1 |
|
1 |
6 |
5 |
4 |
5 |
|
|||||||||
|
|
1 |
1 1 2 3 |
0 1 |
1 |
1 |
0 |
1 |
6 |
5 |
5 4 |
|
Чтобы найти в графе (см. рис. 52) все циклические маршруты длины 3, требуется сложить элементы, стоящие на главной диагонали матрицы B3 :
β11 + β22 + β33 + β44 + β55 = 0 + 2 + 2 + 4 + 4 =12 .
Таким образом, циклических маршрутов длины 3 с начальной вершиной υ1 не существует (см. рис. 52), с начальной вершиной υ2 и υ3 по два
(υ2 −υ5 −υ4 −υ2 , υ2 −υ4 −υ5 −υ2 и υ3 −υ5 −υ4 −υ3 , υ3 −υ4 −υ5 −υ3 ), а с на-
чальной вершиной υ4 и υ5 по четыре (υ4 −υ2 −υ5 −υ4 , υ4 −υ5 −υ2 −υ4 ,
42
υ4 −υ3 −υ5 −υ4 , υ4 −υ5 −υ3 −υ4 |
и υ5 −υ2 −υ4 −υ5 , υ5 −υ4 −υ2 −υ5 , |
υ5 −υ3 −υ4 −υ5 , υ5 −υ4 −υ3 −υ5 ). |
|
Пример 8.2. Вычислить количество маршрутов длины 2, 3 и 4 в графе, изображённом на рис. 53, из вершины υ3 в υ2 и показать их.
υ1υ2
υ4 υ3
Рис. 53. Орграф
Решение. Как и в примере 8.1, сначала составим матрицу смежности:
|
|
|
|
υ1 υ2 υ3 |
υ4 |
|
||
|
|
υ1 |
|
0 |
1 |
0 |
0 |
|
B |
= |
υ2 0 |
0 |
0 |
0 |
, |
||
4×4 |
|
υ3 |
1 |
1 |
0 |
0 |
|
|
|
|
υ4 |
|
1 |
1 |
1 |
0 |
|
а затем найдем B2 , B3 и B4 , так как нам необходимо вычислить количество маршрутов длины 2, 3 и 4.
Итак, вычислим B2 :
0 |
1 |
0 |
0 0 |
1 |
0 |
0 0 |
0 |
0 |
0 |
||||
B2 = B B = 0 |
0 |
0 |
0 0 |
0 |
0 |
0 |
= 0 |
0 |
0 |
0 . |
|||
|
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
2 |
0 |
0 |
Так как в матрице B2 элемент β32 =1, то из этого следует, что существует |
|||||||||||||
только один маршрут длины 2 из вершины υ3 в υ2 |
(υ3 −υ1 −υ2 ). |
|
Теперь найдем B3 :
43
0 |
0 |
0 |
0 0 |
1 |
0 |
0 0 |
0 |
0 |
0 |
||||
B3 = B2 B = 0 |
0 |
0 |
0 0 |
0 |
0 |
0 |
= 0 |
0 |
0 |
0 . |
|||
|
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
2 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
Элемент β32 матрицы B3 равен нулю. Следовательно, маршрутов длины 3 из вершины υ3 в υ2 не существует (вообще в данном орграфе существует только один маршрут длины 3: υ4 −υ3 −υ1 −υ2 ).
Наконец, вычислим матрицу B4 : |
|
|
|
|
|
|
|
|
|||||
0 |
0 |
0 |
0 0 1 |
0 |
0 0 |
0 |
0 |
0 |
|||||
B4 = B3 B = 0 |
0 |
0 |
0 0 |
0 0 |
0 |
= 0 |
0 |
0 |
0 . |
||||
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
0 |
0 |
Так как B4 – нулевая матрица, то маршрутов длины 4 в орграфе нет.
Из теоремы 8.1 вытекают два следствия.
Следствие 8.1. В графе G с n вершинами существует маршрут из вершины υi в вершину υj (υi ≠υj ) тогда и только тогда, когда элемент tij матрицы
T = B + B2 +…+ Bn−1 не равен нулю.
Следствие 8.2. В графе G с n вершинами тогда и только тогда существует
цикл, содержащий вершину υ |
, когда элемент t |
матрицы T = B + B2 +…+ Bn |
|||||||||
i |
|
|
|
|
ii |
|
|
|
|
|
|
не равен нулю. |
|
|
|
|
|
|
|
|
|
|
|
Пример 8.3. Выяснить, существуют ли циклические маршруты в орграфе, |
|||||||||||
изображенном на рис. 53. |
|
|
|
|
|
|
|
|
|
|
|
Решение. Воспользуемся следствием |
|
8.2. |
Найдем |
матрицу |
|||||||
T = B + B2 + B3 + B4 . Так как матрицы B , B2 , |
B3 |
и B4 уже получены в примере |
|||||||||
8.2, то будем иметь |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 0 |
0 |
0 |
0 |
|
|||
T = B + B2 + B3 + B4 = 0 |
0 |
0 |
0 + 0 |
0 |
0 |
0 |
+ |
||||
|
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
1 |
1 |
1 |
0 |
|
1 |
2 |
0 |
0 |
|
|
|
|
|
44 |
|
|
|
|
|
|
|
0 |
0 |
0 |
0 0 |
0 |
0 |
0 0 |
1 |
0 |
0 |
|||||
+ 0 |
0 |
0 |
0 |
+ 0 |
0 |
0 |
0 |
= 0 |
0 |
0 |
0 . |
|||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
||
|
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
|
2 |
4 |
1 |
0 |
Так как элементы t11 , t22 , t33 и t44 все равны нулю, то это означает, что циклические маршруты в орграфе (см. рис. 53) не существуют.
8.3. Кратчайший путь в орграфе
Задача о кратчайшем пути, т.е. о нахождении пути минимальной длины в ориентированном графе, имеет несколько вариантов:
●найти кратчайший путь из заданной вершины s в заданную вершину t;
●найти кратчайшие пути из вершины s во все остальные вершины графа;
●найти кратчайшие пути между всеми упорядоченными парами вершин. Мы ограничимся первыми двумя вариантами, которые решаются практи-
чески одинаково.
I. Если граф не является взвешенным, то длина пути равна числу ребер в нем. Алгоритм нахождения кратчайшего пути для этого случая состоит из двух этапов.
1.Начальной вершине s присваиваем номер 0.
2.Всем вершинам, которые не имеют номера и в которые входят ребра из вершин номера i, присваиваем номер i +1.
Если требуется найти путь в заданную вершину t, то алгоритм останавливается, когда t получает номер. Если же нужно найти пути из s во все вершины, то алгоритм останавливается, когда номер получат все вершины. Номер вершины и есть длина пути в эту вершину. Доказательство очевидно, поскольку путь
влюбую вершину (i +1)-го номера на единицу длиннее пути в вершину i-го номера. Простота этого алгоритма обеспечивается тем, что номера, присваиваемые вершинам, остаются постоянными (не пересчитываются). Поэтому каждая вершина рассматривается только один раз.
|
Пример 8.4. Найти кратчайший путь от вершины s =υ1 до вершины t =υ6 |
|
в орграфе, изображенном на рис. 54. |
|
|
|
Решение. Используем алгоритм, описанный выше. Начальной вершине |
|
s =υ |
присваиваем номер 0. Из s =υ(0) (верхний индекс показывает, какой но- |
|
1 |
1 |
|
мер присвоен вершине) выходят ребра в вершины υ2 |
и υ3 . Следовательно, этим |
|
вершинам присваиваем номер 1. Из вершин υ2(1) |
и υ3(1) выходят ребра в |
|
|
45 |
|
υ2 |
υ4 |
s =υ1 |
t =υ6 |
υ3 |
υ5 |
|
Рис. 54. Орграф |
вершины υ4 и υ5 . Таким образом, вершинам υ4 и υ5 присваиваем номер 2.Наконец, из вершин υ4(2) и υ5(2) выходят ребра в вершину t =υ6 . Значит, вершине t =υ6 присваиваем номер 3. Искомая вершина t =υ6(3) получила номер,
следовательно, алгоритм остановлен. В данном графе имеется четыре пути от
вершины s =υ1 до вершины t =υ6 длины 3: υ1 −υ2 −υ4 −υ6 , υ1 −υ3 −υ5 −υ6 ,
υ1 −υ3 −υ4 −υ6 и υ1 −υ2 −υ5 −υ6 .
II. Во взвешенном графе каждому ребру присвоен положительный вес w(υi ,υj ), называемый его длиной. Длиной пути называется сумма длин, вхо-
дящих в него ребер. В этом случае задача нахождения кратчайшего пути из вершины s решается алгоритмом, который предложил голландский математик Эдсгер Дейкстра*. Его часто называют алгоритмом расстановки меток. В процессе работы этого алгоритма вершинам графа υi V приписываются числа
(метки) d (υi ), которые служат оценкой длины (веса) кратчайшего пути от вершины s к вершине υi . Если вершина υi получила на некотором шаге метку d (υi ), это означает, что в графе G существует путь из s в υi , имеющий длину (вес) d (υi ). Метки могут находиться в двух состояниях – быть временными
или постоянными. Превращение временной метки в постоянную означает, что кратчайшее расстояние от вершины s до соответствующей вершины найдено.
Алгоритм Дейкстры содержит одно ограничение – веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором строится сам путь от вершины s к вершине t. Опишем работу алгоритма Дейкстры.
* Биографические сведения см. в прил. 2.
46
Этап 1. Нахождение длины кратчайшего пути
Шаг 1. Присвоение вершинам начальных меток
Полагаем d (s)= 0* и считаем эту метку постоянной (постоянные метки будем помечать сверху звездочкой). Для остальных вершин υi V , υi ≠ s по-
лагаем d (υi )= ∞ и считаем эти метки временными. Пусть υ = s , где υ – обозначение текущей вершины.
Шаг 2. Изменение меток
Для каждой вершины υi с временной меткой, непосредственно следующей за вершиной υ, меняем ее метку в соответствии со следующим правилом:
dнов. (υi )= min{dстар. (υi ), d (υ)+ w(υ,υi )}, |
(8.1) |
где w(υ,υi ) – вес дуги, соединяющей вершины υ и υi .
Шаг 3. Превращение метки из временной в постоянную
Из всех вершин с временными метками выбираем вершину υi*0 с наименьшим значением метки:
( i0 ) |
|
{ |
i } |
|
d υ* |
= min |
|
d (υ ) , |
(8.2) |
где d (υi ) – временная метка (υi V ).
Превращаем эту метку в постоянную и полагаем υ =υi*0 .
Шаг 4. Проверка на завершение первого этапа
Если требуется найти кратчайший путь в вершину t, условием окончания алгоритма является пункт 4а. Если ищутся кратчайшие пути во все вершины, то условие окончания – 4б.
4а. Если υ =t , то d (υ) – длина кратчайшего пути от s до t. В противном
случае происходит возвращение ко второму шагу.
4б. Если все вершины имеют постоянные метки (значения этих меток будут показывать длины кратчайших путей), то необходимо закончить алгоритм. В противном случае вернуться ко второму шагу.
Этап 2. Построение кратчайшего пути
Шаг 5. Последовательный поиск дуг кратчайшего пути
Среди вершин, непосредственно предшествующих вершине υ с постоянными метками, находим вершину υi (удовлетворяющую соотношению):
47
d (υ)= d (υi ) + w(υi ,υ). |
(8.3) |
Включаем дугу, соединяющую вершины υi и υ, в искомый путь и полагаем υ =υi .
Шаг 6. Проверка на завершение второго этапа
Если υ = s , то кратчайший путь найден – его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.
Пример 8.5. По алгоритму Дейкстры найти кратчайший путь от вершины s =υ1 до вершины t =υ6 во взвешенном орграфе, заданном матрицей весов:
|
|
|
υ1 |
υ2 |
υ3 |
υ4 |
υ5 |
υ6 |
|
|
υ1 |
|
0 |
5 |
11 |
3 |
15 |
∞ |
|
|
|
|
∞ |
0 |
8 |
2 |
∞ |
∞ |
|
|
υ2 |
|
|||||||
W = |
υ3 |
|
∞ |
∞ |
0 |
1 |
∞ |
9 |
|
|
|
∞ |
∞ |
∞ |
0 |
6 |
20 |
. |
|
|
υ4 |
|
|||||||
|
υ5 |
|
∞ |
∞ |
1 |
∞ |
0 |
17 |
|
|
|
|
∞ |
∞ |
∞ |
∞ |
∞ |
0 |
|
|
υ6 |
|
Решение. Данный взвешенный орграф содержит шесть вершин: υ1,υ2,υ3,υ4,υ5, υ6 . Как видно из матрицы весов (по первой строке), вершина υ1
соединена с вершинами υ2,υ3,υ4 и υ5 и длины дуг, соединяющих вершину υ1 с υ2,υ3,υ4,υ5 , соответственно равны 5, 11, 3 и 15. Петли в вершине υ1 нет, так как элемент w11 = 0. Вершина υ1 с υ6 не соединена ( w16 = ∞). Аналогично рас-
суждая о значениях элементов в остальных строках, изобразим взвешенный орграф, соответствующий данной матрице весов (рис. 55).
υ2 |
8 |
υ3 |
9 |
t =υ6 |
|
2 |
|
1 |
|
5 |
1 |
|
17 |
|
11 |
|
|||
|
|
20 |
|
|
s =υ1 |
|
|
|
|
3 |
|
6 |
υ |
|
|
υ4 |
5 |
||
|
|
15
Рис. 55. Взвешенный орграф
48
Применим алгоритм Дейкстры.
Этап 1. Нахождение длины кратчайшего пути
Шаг 1. Присвоение вершинам начальных меток
Полагаем d (s)= 0* – постоянная метка, υ = s =υ1 – текущая вершина,
d (υ2 )= d (υ3 )= d (υ4 )= d (υ5 )= d (υ6 )= ∞ – временные метки.
Все результаты вычислений удобно приводить в виде таблицы. После первого шага получаем табл. 1.
Таблица 1
Вершины графа |
υ1 |
υ2 |
υ3 |
υ4 |
υ5 |
υ6 |
Метки вершин после первого шага |
0* |
∞ |
∞ |
∞ |
∞ |
∞ |
1-я итерация
Шаг 2. Изменение меток
Множество вершин, непосредственно следующих за υ = s =υ1 с временными метками V ={υ2,υ3,υ4,υ5}. Пересчитываем временные метки этих вершин:
|
d |
нов. |
(υ |
2 |
)= min |
{ |
d |
стар. |
(υ |
2 |
), d (υ)+ w(υ,υ |
2 |
) |
= min |
{ |
∞, 0* +5 |
= min{∞, 5}=5, |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
} |
|
||||||||||
d |
нов. |
(υ |
3 |
) |
= min |
{ |
d |
стар. |
(υ |
), d (υ)+ w(υ,υ |
) |
= min |
{ |
∞, 0* +11 |
= min{∞, 11}=11, |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
3 |
|
} |
|
|
|
|
} |
|
||||||||
|
d |
нов. |
(υ |
4 |
)= min |
{ |
d |
стар. |
(υ |
4 |
), d (υ)+ w(υ,υ |
4 |
) |
= min |
{ |
∞, 0* +3 |
= min{∞, 3}=3, |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
} |
|
||||||||||
d |
нов. |
(υ |
5 |
) |
= min |
{ |
d |
стар. |
(υ |
5 |
), d (υ)+ w(υ,υ |
) |
= min |
{ |
∞, 0* +15 |
= min{∞, 15}=15 . |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
} |
|
|
|
|
} |
|
Шаг 3. Превращение метки из временной в постоянную
Одна из временных меток превращается в постоянную
min{d (υ2 ), d (υ3 ), d (υ4 ), d (υ5 ), d (υ6 )}= min{5,11, 3,15, ∞} =3 = d (υ4 ),
принимаем за υ =υ4 .
Шаг 4. Проверка на завершение первого этапа
υ =υ4 ≠ t =υ6 ,
происходит возвращение на второй шаг.
49
Результаты вычислений оформим в виде табл. 2.
Таблица 2
Вершины графа |
υ1 |
υ2 |
υ3 |
υ4 |
υ5 |
υ6 |
Метки вершин после первого шага |
0* |
∞ |
∞ |
∞ |
∞ |
∞ |
Метки вершин после первой итерации |
– |
5 |
11 |
3* |
15 |
∞ |
2-я итерация
Шаг 2
Множество вершин, непосредственно следующих за υ =υ4 с временными метками V ={υ5,υ6}. Пересчитываем временные метки этих вершин:
dнов. (υ5 )= min{dстар. (υ5 ), d (υ)+ w(υ,υ5 )}= min{15, 3* +6}= min{15, 9}=9 ,
dнов. (υ6 )= min{dстар. (υ6 ), d (υ)+ w(υ,υ6 )}= min{∞, 3* + 20}= min{∞, 23}= 23.
Шаг 3
Одна из временных меток превращается в постоянную:
min{d (υ2 ), d (υ3 ), d (υ5 ), d (υ6 )}= min{5,11, 9, 23} =5 = d (υ2 ),
принимаем за υ =υ2 .
Шаг 4
υ =υ2 ≠ t =υ6 ,
происходит возвращение на второй шаг. Результаты вычислений приведем в табл. 3.
Таблица 3
Вершины графа |
υ1 |
υ2 |
υ3 |
υ4 |
υ5 |
υ6 |
Метки вершин после первого шага |
0* |
∞ |
∞ |
∞ |
∞ |
∞ |
Метки вершин после первой итерации |
– |
5 |
11 |
3* |
15 |
∞ |
Метки вершин после второй итерации |
– |
5* |
11 |
– |
9 |
23 |
3-я итерация
Шаг 2
Множество вершин, непосредственно следующих за υ =υ2 с временными метками V ={υ3} (у вершины υ4 есть постоянная метка). Пересчитываем временную метку этой вершины:
50