Практикум по дисциплине «Дискретная математика»
Решение контрольных задач
жүктеу/скачать 0,98 Mb.
|
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)
- Бұл бет үшін навигация:
- Алгоритм выделения компонент сильной связности
2. Решение контрольных задач 2.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.
 .
Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:  ,  ,
жүктеу/скачать 0,98 Mb. Достарыңызбен бөлісу:
|