Задание 1. Расстояния в ориентированном графе
С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.
Пусть 
ориентированный граф с n³2 вершинами и v, w (v ¹ w) – заданные вершины из V.
Алгоритм поиска минимального пути из 
в 
в ориентированном графе
(алгоритм фронта волны).
1) Помечаем вершину 
индексом 0, затем помечаем вершины Î образу вершины индексом 1. Обозначаем их FW 1 (v). Полагаем k =1.
2) Если 
или k = n -1, и одновременно 
то вершина 
не достижима из . Работа алгоритма заканчивается.
В противном случае продолжаем:
3) Если 
, то переходим к шагу 4.
В противном случае мы нашли минимальный путь из 
в и его длина равна k. Последовательность вершин
есть этот минимальный путь. Работа завершается.
4) Помечаем индексом k +1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k +1 обозначаем 
. Присваиваем k:= k +1 и переходим к 2).
Замечания
· Множество 
называется фронтом волны k го уровня.
· Вершины 
могут быть выделены неоднозначно, что соответствует случаю, если 
несколько минимальных путей из в .
Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу минимальных расстояний R (D)между его вершинами. Это квадратная матрица размерности 
, элементы главной диагонали которой равны нулю (
, i =1,.., n).
Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (
, если 
). Далее построчно заполняем матрицу следующим образом.
Рассматриваем первую строку, в которой есть единицы. Пусть это строка − i -тая и на пересечении с j -тым столбцом стоит единица (то есть 
). Это значит, что из вершины 
можно попасть в вершину 
за один шаг. Рассматриваем j -тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент 
. Тогда из вершины в вершину 
можно попасть за два шага. Таким образом, можно записать 
. Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.
|
|
Примечание: В контрольной работе самый длинный путь найти при помощи алгоритма фронта волны.
Пример1
Найдем расстояния в ориентированном графе D, изображенном на рис. 7. В данной задаче количество вершин n= 7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа D будут иметь размерность 7×7.
Рис.7.
Матрица смежности:
.
Начинаем заполнять матрицу R (D) минимальных расстояний: сначала ставим нули по главной диагоналии rij = aij, если aij =1, (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать 
. Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит, 
, 
. Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому 
. В итоге получаем следующую матрицу:
|
|
Таким образом, диаметром исследуемого ориентированного графа будет 
.
Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше 
: r (vi) − максимальное из расстояний, стоящих в 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.
Значит, радиусомграфа G будет 
Соответственно, центрами графа G будут вершины v 5 и v 6, так как величины их эксцентриситетов совпадают с величиной радиуса 
.
Опишем теперь нахождение минимального пути из вершины v 3 в вершину v 6 по алгоритму фронта волны. Обозначим вершину v 3 как V 0, а вершину v 6 - как W (см. рис. 8). Множество вершин, принадлежащих образу V 0, состоит из одного элемента - это вершина v 4, которую, согласно алгоритму, обозначаем как V 1: FW 1(v 3)={ v 4}. Поскольку искомая вершина не принадлежит фронту волны первого уровня 
, продолжаем работу алгоритма. Строим фронт волны второго уровня - это множество вершин, принадлежащих образу вершины V 1: FW 2(v 3)={ v 7}, обозначаем v 7≡ V 2. В образ вершины V 2 входят две вершины - v 5 и v 4, но, так как v 4 уже была помечена как V 0, то фронт волны третьего уровня состоит из одного элемента: 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, которая входит в образ вершины 
, то есть FW 5(v 3)={ v 6≡ W }, работа алгоритма закончена. Минимальный путь (5 шагов) из вершины v 3 в вершину v 6 выглядит так: v 3 v 4 v 7 v 5 v 1 v 6.
Рис.8.