Компоненты сильной связности ориентированного графа
С помощью матрицы смежности найти компоненты сильной связности ориентированного графа 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:
Дата добавления: 2015-09-27 | Просмотры: 1510 | Нарушение авторских прав
|