Задание 1. Расстояния в ориентированном графе

При помощи метода фронта волны отыскать расстояния в направленном графе D: поперечник, радиус и центры.

Пусть направленный граф с n³2 верхушками и v,w (v¹w) – данные верхушки из V.

Метод поиска малого пути из в в направленном графе

(метод фронта волны).

1) Помечаем верхушку индексом 0, потом помечаем верхушки Î виду верхушки индексом Задание 1. Расстояния в ориентированном графе 1. Обозначаем их FW1 (v). Полагаем k=1.

2) Если либо k=n-1, и сразу то верхушка не достижима из . Работа метода завершается.

В неприятном случае продолжаем:

3) Если , то перебегаем к шагу 4.

В неприятном случае мы отыскали малый путь из в и его длина равна k. Последовательность вершин

есть этот малый путь Задание 1. Расстояния в ориентированном графе. Работа заканчивается.

4) Помечаем индексом k+1 все непомеченные верхушки, которые принадлежат виду огромного количества вершин c индексом k. Огромное количество вершин с индексом k+1 обозначаем . Присваиваем k:=k+1 и перебегаем к 2).

Замечания

· Огромное количество именуется фронтом волны kго уровня.

· Верхушки могут быть выделены разносторонне, что соответствует случаю, если несколько малых путей Задание 1. Расстояния в ориентированном графе из в .

Чтоб отыскать расстояния в направленном графе, нужно составить матрицу малых расстояний R(D)меж его верхушками. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю ( , i=1,..,n).

Поначалу составляем матрицу смежности. Потом переносим единицы из матрицы смежности в матрицу малых расстояний ( , если ). Дальше построчно заполняем матрицу последующим Задание 1. Расстояния в ориентированном графе образом.

Рассматриваем первую строчку, в какой есть единицы. Пусть это строчка − i-тая и на скрещении с j-тым столбцом стоит единица (другими словами ). Это означает, что из верхушки можно попасть в верхушку за один шаг. Рассматриваем j-тую сроку (строчку стоит вводить в рассмотрение, если она Задание 1. Расстояния в ориентированном графе содержит хотя бы одну единицу). Пусть элемент . Тогда из верхушки в верхушку можно попасть за два шага. Таким макаром, можно записать . Следует увидеть, что если в рассматриваемых строчках две либо более единиц, то следует прорабатывать все вероятные варианты попадания из одной верхушки в другую, записывая в матрицу длину наикратчайшего из их Задание 1. Расстояния в ориентированном графе.

Примечание: В контрольной работе самый длиннющий путь отыскать с помощью метода фронта волны.

Пример1

Найдем расстояния в направленном графе D, изображенном на рис. 7. В данной задачке количество вершин n=7, как следует, матрицы смежности и малых расстояний меж верхушками нацеленного графа D будут иметь размерность 7×7.

Рис.7.

Матрица смежности Задание 1. Расстояния в ориентированном графе:

.

Начинаем заполнять матрицу R(D) малых расстояний: поначалу ставим нули по главной диагоналии rij=aij, если aij=1, (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строчку. Тут есть две единицы, другими словами из первой верхушки за один шаг можно попасть во вторую и шестую. Из 2-ой верхушки можно попасть Задание 1. Расстояния в ориентированном графе за один шаг в третью (путь в первую верхушку нас не интересует), как следует, можно записать . Из 6-ой верхушки можем добраться за один шаг в пятую и седьмую, а означает, , . Сейчас ищем маршруты, исходящие из первой верхушки, состоящие из 3 шагов: за 2 шага идем в третью верхушку, оттуда за один шаг Задание 1. Расстояния в ориентированном графе попадаем в четвертую, потому . В конечном итоге получаем последующую матрицу:

Таким макаром, поперечником исследуемого нацеленного графа будет .

Для каждой верхушки данного нацеленного графа найдем наибольшее удаление (эксцентриситет) в графе G от верхушки нее по формуле, которая была приведена выше : r(vi) − наибольшее из расстояний, стоящих в i Задание 1. Расстояния в ориентированном графе-той строке. Таким макаром,

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 в Задание 1. Расстояния в ориентированном графе верхушку v6 по методу фронта волны. Обозначим верхушку v3 как V0, а верхушку v6 - как W (см. рис. 8). Огромное количество вершин, принадлежащих виду V0, состоит из 1-го элемента - это верхушка v4, которую, согласно методу, обозначаем как V1: FW1(v3)={v4}. Так как разыскиваемая верхушка не принадлежит фронту волны первого уровня Задание 1. Расстояния в ориентированном графе , продолжаем работу метода. Строим фронт волны второго уровня - это огромное количество вершин, принадлежащих виду верхушки V1: FW2(v3)={v7}, обозначаем v7≡V2. В образ верхушки V2 входят две верхушки - v5 и v4, но, потому что v4 уже была помечена как V0, то фронт волны третьего уровня состоит из 1-го Задание 1. Расстояния в ориентированном графе элемента: FW3(v3)={v5}, v5≡V3. Из непомеченных вершин в образ верхушки V3 входят v1 и v2, соответственно, FW4(v3)={v1, v2}, v1≡V4, v2≡V4. Сейчас помечены все верхушки, не считая v6, которая заходит в образ верхушки , другими словами FW5(v3)={v6≡W}, работа метода закончена. Малый Задание 1. Расстояния в ориентированном графе путь (5 шагов) из верхушки v3 в верхушку v6 смотрится так: v3 v4 v7 v5 v1 v6.

Рис.8.


zadachi-yarmarki-vistavki-sozdanie-uslovij-dlya-demonstracii-opita-raboti-pedagogov-psihologov-socialnih-pedagogov-pedagogov-dopolnitelnogo-obrazovaniya-pedagogov-organizatorov-obrazovatelnih-organizacij.html
zadachi-zaklyuchitelnoj-chasti-publichnoj-rechi.html
zadachi-zakrepit-znaniya-uchashihsya-o-predmetah-lichnoj-gigieni.html