Практикум по дисциплине «Дискретная математика»



бет11/25
Дата10.01.2020
өлшемі0,98 Mb.
#55624
түріПрактикум
1   ...   7   8   9   10   11   12   13   14   ...   25
Байланысты:
[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:




D1:



D2:




D3:






Достарыңызбен бөлісу:
1   ...   7   8   9   10   11   12   13   14   ...   25




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет