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

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

Прочитайте:
  1. Aлгоритмы на графах
  2. Активные компоненты электронных преобразователей
  3. Вимкнути живлення.Переключити вхід осцилографа до виходу випрямляча.
  4. Відповідальність спеціалістів поліграфа
  5. Волновые процессы и разметка графа
  6. Выделение цитокинов могут вызывать компоненты микробных клеток
  7. Дополнительные компоненты лечения
  8. Задання графа за допомогою матриці інцидентності.
  9. Задання графа за допомогою матриці суміжності.
  10. Задання графа за допомогою списку.

С помощью матрицы смежности найти компоненты сильной связности ориентированного графа 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:

 


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







При использовании материала ссылка на сайт medlec.org обязательна! (0.005 сек.)