Практикум по дисциплине «Дискретная математика»
жүктеу/скачать 0,98 Mb.
|
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)
| Примечание. Самый длинный путь найти при помощи алгоритма фронта волны.
Пример Найдем расстояния в ориентированном графе D, изображенном на рис. 7. В данной задаче количество вершин n=7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа D будут иметь размерность 7×7. 
Рис.7.
 .
Начинаем заполнять матрицу R(D) минимальных расстояний: сначала ставим нули по главной диагонали и rij=aij, если aij=1, (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать  . Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит,  ,  . Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому  . В итоге получаем следующую матрицу:
 .
Таким образом, диаметром исследуемого ориентированного графа будет  .
Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше  : r(vi) − максимальное из расстояний, стоящих в i-той строке. Таким образом,
r(v1)=3, r(v2)=3, r(v3)=5, r(v4)=4, r(v5)=2, r(v6)=2, r(v7)=3. Значит, радиусом графа G будет 
Соответственно, центрами графа G будут вершины v5 и v6 , так как величины их эксцентриситетов совпадают с величиной радиуса  .
Опишем теперь нахождение минимального пути из вершины v3 в вершину v6 по алгоритму фронта волны. Обозначим вершину v3 как V0, а вершину v6 как W (см. рис. 8). 
Рис.8. Множество вершин, принадлежащих образу V0, состоит из одного элемента это вершина v4, которую, согласно алгоритму, обозначаем как V1: FW1(v3)={v4}. Поскольку искомая вершина не принадлежит фронту волны первого уровня  , продолжаем работу алгоритма. Строим фронт волны второго уровня это множество вершин, принадлежащих образу вершины V1: FW2(v3)={v7}, обозначаем v7≡V2. В образ вершины V2 входят две вершины v5 и v4, но, так как v4 уже была помечена как V0, то фронт волны третьего уровня состоит из одного элемента: FW3(v3)={v5}, v5≡V3. Из непомеченных вершин в образ вершины V3 входят v1 и v2, соответственно, FW4(v3)={v1, v2}, v1≡V4, v2≡V4. Теперь помечены все вершины, кроме v6, которая входит в образ вершины  , то есть FW5(v3)={v6≡W}, работа алгоритма закончена. Минимальный путь (5 шагов) из вершины v3 в вершину v6 выглядит так: v3 v4 v7 v5 v1 v6.
жүктеу/скачать 0,98 Mb. Достарыңызбен бөлісу:
|