История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2018-01-05 | 169 |
5.00
из
|
Заказать работу |
|
|
Задание 1. Компоненты сильной связности ориентированного графа.
С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.
Cоставляем матрицу смежности A (D) размерности (n − количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин, из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины vi и входящая в vj, то элемент матрицы смежности, стоящий на пересечении i -той строки и j -того столбца равен 1, иначе – 0.).
Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T (D) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S (D) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.
Алгоритм выделения компонент сильной связности
1. Присваиваем p =1 (p − количество компонент связности), .
2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A (Dp) возьмем подматрицу матрицы A (D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.
3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p - количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp+1, присваиваем p=p +1 и переходим к п. 2.
Пример
Выделим компоненты связности ориентированного графа, изображенного на рис. 6. В данной задаче количество вершин n= 5.
|
Рис. 6.
Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом
.
Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:
, ,
,
Следовательно,
.
Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:
.
Присваиваем p =1 и составляем множество вершин первой компоненты сильной связности D 1: это те вершины, которым соответствуют единицы в первой строке матрицы S (D). Таким образом, первая компонента сильной связности состоит из одной вершины .
Вычеркиваем из матрицы S 1(D) строку и столбец, соответствующие вершине v 1, чтобы получить матрицу S 2(D):
.
Присваиваем p =2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S 2(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A (D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V 2:
.
Вычеркиваем из матрицы S 2(D) строки и столбцы, соответствующие вершинам из V 2,чтобы получить матрицу S 3(D), которая состоит из одного элемента:
и присваиваем p =3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .
Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:
D 1: | D 2: | D 3: |
Задание 2. Расстояния в ориентированном графе
С помощью алгоритма фронта волны найти расстояния в ориентированном графе 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 -тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.
Примечание: В контрольной работе самый длинный путь найти при помощи алгоритма фронта волны.
Пример
Найдем расстояния в ориентированном графе 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.
Задание 3. Минимальный путь в нагруженном ориентированном графе
|
Найти минимальный путь в нагруженном ориентированном графе из вершины в вершину по методу Форда-Беллмана.
Рассмотрим сначала общую задачу – нахождения минимального пути из вершины vнач в vкон.
Пусть D =(V, X) – нагруженный ориентированный граф, V ={ v 1,…, vn }, n >1. Введем величины , где i =1,…, n, k =0,1,2,…, n– 1.
Для каждого фиксированного i и k величина равна длине минимального пути среди путей из vнач в vi содержащих не более k дуг. Если путей нет, то .
Положим также .
Составляем матрицу длин дуг C (D)=[ cij ] порядка n:
Утверждение. При i =2,…, n, k ³0 выполняется равенство
. (3.1)
Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе D из vнач в vкон.(vнач ≠ vкон).
( записываем в виде матрицы, i - строка, k -столбец).
1) Составляем таблицу , i =1,…, n, k =0,…, n -1. Если , то пути из vнач в vкон нет. Конец алгоритма.
2) Если то это число выражает длину любого минимального пути из vнач в vкон. Найдем минимальное k 1³1, при котором . По определению получим, что k 1- минимальное число дуг в пути среди всех минимальных путей из vнач в vкон.
3) Затем определяем номера i 2,…, такие, что
,
,
,
то есть восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из vнач в vкон.
Пример
Найдем минимальный путь из вершины v 2 в v 6 в ориентированном нагруженном графе D, изображенном на рис. 9. В рассматриваемом графе количество вершин n= 7, следовательно, матрица длин дуг ориентированного графа D будет иметь размерность 7×7.
Рис. 9.
Матрица длин дуг для рассматриваемого графа будет выглядеть следующим образом:
.
Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v 2 в вершину vi не более, чем за k шагов, k =0,… n -1 (n =7, следовательно, k =0,…6). Как было определено выше, , и для всех остальных вершин vi ≠ v 2, то есть первый столбец таблицы состоит из элементов, равных , кроме элемента . Второй столбец таблицы повторяет вторую строку матрицы стоимости, поскольку представляет собой стоимость возможных путей из вершины v 2 за один шаг. Далее по формуле (3.1) находим по столбцам все оставшиеся элементы таблицы. Например, чтобы найти элемент , складываем элементы столбца и первого столбца матрицы стоимости и выбираем минимальное из получившихся чисел: .
В конечном итоге получаем следующую таблицу:
Теперь необходимо по построенной таблице и по матрице C (D) восстановить минимальный путь из вершины v 2 в v 6, который будет строиться с конца, то есть, начиная с вершины v 6. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v 6 в таблице. Это число – 21 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 4. В вершину v 6 мы можем попасть за один шаг из вершин v 1 и v 7 (длина соответствующих дуг 8 и 5 соответственно – данные из матрицы C (D)). Выбираем минимальную по длине из этих дуг. Далее, в вершину v 7 можно попасть из v 4 и v 5(длина соответствующих дуг 7 и 3 соответственно). Продолжая аналогичным образом, найдем искомый путь за 4 шага минимальной длины из вершины v 2 в v 6: v 2 v 3 v 5 v 7 v 6.
|
Задание 4. Эйлеровы циклы и цепи
Найти Эйлерову цепь в неориентированном графе.
Исходя из утверждений 1 и 2, чтобы найти Эйлерову цепь, нужно соединить две вершины с нечетными степенями фиктивным ребром. Тогда задача сводится к нахождению Эйлерова цикла по приведенному ниже алгоритму. Из найденного цикла удаляется фиктивное ребро, тем самым находится искомая Эйлерова цепь.
|
|
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!