АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Компоненты сильной связности ориентированного графа

С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.

Cоставляем матрицу смежности A (D) размерности (n − количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин, из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины v_i и входящая в v_j, то элемент матрицы смежности, стоящий на пересечении i -той строки и j -того столбца равен 1, иначе – 0.).

Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T (D) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S (D) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.

Алгоритм выделения компонент сильной связности

1. Присваиваем p =1 (p − количество компонент связности), .

2. Включаем в множество вершин V_p компоненты сильной связности D_p вершины, соответствующие единицам первой строки матрицы S_p. В качестве матрицы A (D_p) возьмем подматрицу матрицы A (D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V_p.

3. Вычеркиваем из S_p строки и столбцы, соответствующие вершинам из V_p. Если не остается ни одной строки (и столбца), то p - количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как S_p+1, присваиваем p=p +1 и переходим к п. 2.

Пример

Выделим компоненты связности ориентированного графа, изображенного на рис. 6. В данной задаче количество вершин n= 5.

Рис. 6.

Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом

.

Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:

, ,

,

Следовательно,

.

Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:

.

Присваиваем p =1 и составляем множество вершин первой компоненты сильной связности D ₁: это те вершины, которым соответствуют единицы в первой строке матрицы S (D). Таким образом, первая компонента сильной связности состоит из одной вершины .

Вычеркиваем из матрицы S ₁(D) строку и столбец, соответствующие вершине v ₁, чтобы получить матрицу S ₂(D):

.

Присваиваем p =2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S ₂(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A (D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V ₂:

.

Вычеркиваем из матрицы S ₂(D) строки и столбцы, соответствующие вершинам из V ₂,чтобы получить матрицу S ₃(D), которая состоит из одного элемента:

и присваиваем p =3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .

Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:

D 1:

D 2:

D 3:

Дата добавления: 2015-09-27 | Просмотры: 1520 | Нарушение авторских прав