С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры
Примечание: самый длинный путь в графе найти при помощи алгоритма фронта волны.
Решение
Количество вершин N=7, значит, матрица смежности, и матрица минимальных расстояний между вершинами графа будут иметь размерность 7х7
Матрица смежности имеет вид
А=0100110001000010000001000010010101000010010001010
Заполним матрицу R - минимальных расстояний – ставим нули по главной диагонали и переносим 1 из матрицы смежности.
А=010011001110110110110110
Рассмотрим первую строку – здесь есть три единицы, это значит, из первой вершины можно попасть за один шаг в вершины 2, 5 и 6
Из вершины 2 за один шаг можно попасть в вершину 3, тогда r13==2
Из вершины 5 можно попасть за 1 шаг в вершины 3, 4 и 6
. вершину 3 рассмотрели, в вершину 6 можно попасть за 1 шаг, а в вершину 4 можно попасть из вершины 1 за 2 шага, значит r14==2
Из вершины 6 можно попасть за 1 шаг в вершину 7. в вершину 7 можно попасть из вершины 1 за 2 шага, значит r17==2
Заполним верхнюю строку
А=012211201110110110110110
Рассмотрим вторую строку.
Из вершины 2 попадаем в вершину 3 за 1 шаг.
Из вершины 3 попадаем за 1 шаг в вершины 1 и 4, значит расстояние от вершины 2 до вершин 4 и 1 равно 2 тогда r21=2 r24=2
Из вершины 1 попадаем в вершину 5 и 6 за 1 шаг, тогда из вершины 2 до вершины 5 и 6 попадаем за 2+1=3 шага r25=3 r26=3
Из вершины 4 попадаем в вершину 7 за 1 шаг, тогда из вершины 2 до вершины 7 попадаем за 2+1=3 шага r27=3
Заполняем вторую строку матрицы расстояний
А=01221122012333110110110110110
Продолжая заполнение матрицы построчно, получим
А=0122112201233314243231320313210121220212210221210
Диаметр данного графа d=4
Для каждой вершины найдем максимальное удаление
R(v1)=2 R(v2)=3 R(v3)=2 R(v4)=4 R(v5)=2 R(v6)=4 R(v7)=3
Радиус – минимальное из максимальных удалений равен 2, центрами графа будут вершины V1, V3 и V5
Найдем самый длинный путь по алгоритму фронта волны из вершины V4 в вершину V1