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