Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная м...
Методическое пособие - Математика и статистика
Другие методички по предмету Математика и статистика
ного графа (она должна быть симметрической) по второй формуле из того же утверждения.
Алгоритм выделения компонент сильной связности
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.
Значит, для данного ориентированного графа матрица смежности будет иметь размерность 55 и будет выглядеть следующим образом
.
Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:
, ,
,
Следовательно,
.
Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:
.
Присваиваем p=1 и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины .
Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине v1, чтобы получить матрицу S2(D):
.
Присваиваем p=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D ? в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:
.
Вычеркиваем из матрицы S2(D) строки и столбцы, соответствующие вершинам из V2 ,чтобы получить матрицу S3(D), которая состоит из одного элемента:
и присваиваем p=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .
Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:
D1:
D2:
D3:
Задание 2. Расстояния в ориентированном графе
С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.
Пусть ориентированный граф с n2 вершинами и v,w (vw) заданные вершины из V.
Алгоритм поиска минимального пути из в в ориентированном графе
(алгоритм фронта волны).
- Помечаем вершину
индексом 0, затем помечаем вершины образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.
- Если
или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.
В противном случае продолжаем:
- Если
, то переходим к шагу 4.
В противном случае мы нашли минимальный путь из в и его длина равна k. Последовательность вершин
есть этот минимальный путь. Работа завершается.
- Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем
. Присваиваем k:=k+1 и переходим к 2).
- Множество
называется фронтом волны kго уровня.
- Вершины
могут быть выделены неоднозначно, что соответствует случаю, если несколько минимальных путей из в .
Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу минимальных расстояний R(D)между его вершинами. Это квадратная матрица размерности
Замечания
, элементы главной диагонали которой равны нулю (, i=1,..,n).
Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (, если ). Далее построчно заполняем матрицу следующим образом.
Рассматриваем первую строку, в которой есть единицы. Пусть это строка ? i-тая и на пересечении с j-тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем j-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.
Примечание: В контрольной работе самый длинный путь найти при помощи алгоритма фронта волны.
Пример
Найдем расстояния в ориентированном графе D, изображенном на рис. 7. В данной задаче количество вершин n=7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа D будут иметь размерность 77.
Рис.7.