Контрольная работа по прикладной математике

1. С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.

Примечание: самый длинный путь в графе найти при помощи алгоритма фронта волны.
Решение:
Матрица смежности:
.
Начинаем заполнять матрицу R(D) минимальных расстояний: сначала ставим нули по главной диагонали и rij=aij, если aij=1, (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть три единицы, то есть из первой вершины за один шаг можно попасть во вторую, в пятую и шестую. Из второй вершины можно попасть за один шаг в третью, следовательно, можно записать . Из пятой вершины можем добраться за один шаг в третью и четвертую, значит, , . Из шестой вершины можем добраться за один шаг в седьмую, а значит, . В итоге получаем следующую матрицу:
.
Таким образом, диаметром исследуемого ориентированного графа будет .
Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше : r(vi) − максимальное из расстояний, стоящих в i-той строке. Таким образом,
r(v1)=2, r(v2)=3, r(v3)=2, r(v4)=4, r(v5)=2, r(v6)=4, r(v7)=3.
Значит, радиусом графа G будет
Соответственно, центрами графа G будут вершины v1 и v5 , так как величины их эксцентриситетов совпадают с величиной радиуса .
Опишем теперь нахождение минимального пути из вершины v4 в вершину v1 по алгоритму фронта волны. Обозначим вершину v4 как V0, а вершину v1  как W.

Множество вершин, принадлежащих образу V0, состоит из одного элемента  это вершина v7, которую, согласно алгоритму, обозначаем как V1: FW1(v4)={v7}. Поскольку искомая вершина не принадлежит фронту волны первого уровня , продолжаем работу алгоритма. Строим фронт волны второго уровня  это множество вершин, принадлежащих образу вершины V1: FW2(v7)={v5}, обозначаем v5≡V2. В образ вершины V2 входят три вершины  v2 и v3, то фронт волны третьего уровня состоит: FW3(v5)={v2 ,v3,v6}, v2≡V3 v3≡V3 v6≡V3. Теперь помечены все вершины, кроме v1, которая входит в образ вершины , то есть FW4(v3)={v1≡W}, работа алгоритма закончена. Минимальный путь (4 шага) из вершины v4 в вершину v1 выглядит так: v4 v7 v5 v3 v1.
 
2. Найти минимальный путь в нагруженном графе по методу Форда-Беллмана.

а) из вершины v1 в вершину v4
Решение:
шаг 1.
Матрица длин дуг для рассматриваемого графа будет выглядеть следующим образом:

Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v1 в вершину vi не более, чем за k шагов, k=0,…n-1 (n=7, следовательно, k=0,…6). Как было определено выше, , и для всех остальных вершин vi ≠ v2, то есть первый столбец таблицы состоит из элементов, равных , кроме элемента . далее находим остальные элементы таблицы по формуле:

В конечном итоге получаем следующую таблицу:



Теперь необходимо по построенной таблице и по матрице C(D) восстановить минимальный путь из вершины v1 в v4, который будет строиться с конца, то есть, начиная с вершины v4. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v4 в таблице. Это число – 15 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 2. В вершину v4 мы можем попасть за один шаг из вершины v5 (длина соответствующей дуги равна 9 соответственно – данные из матрицы C(D)). Далее, в вершину v5 можно попасть из v1 и v6 (длина соответствующих дуг 6 и 11 соответственно). Искомый путь за 2 шага минимальной длины из вершины v4 в v1: v4 v5 v1 .