Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 21 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

Г
-1
( х
1
) = { х
5
}
Г
-2
( х
1
) = { х
2
, х
4
}
Г
-3
( х
1
) = { х
1
}
Г
-4
( х
1
) = { х
5
}
T
-
( х
1
) = х
1
∪ { х
5
} ∪ { х
2
, х
4
} ∪ { х
1
} ∪ { х
5
} = { х
1
, х
2
, х
4
, х
5
}
2.2.3.Нахождение транзитивных замыканий по матрице смежности.
Рассмотрим метод нахождения прямого транзитивного замыкания по матрице
смежности, показанной на рис.11,а для вершины х
2
графа , изображенного на
рис.11,б. Вторая клетка уже занята нулем, поэтому 1 не заносим. 2-й шаг
начинается просмотром 5-й строки матрицы смежности, соответствующий
вершине х
5
графа. Находим, что элементы а
51
=1 и а
54
=1, то есть из вершины х
5
имеются дуги в вершины х
1
и х
4
или иначе из вершины х
2
имеются пути длиной 2 в
вершины х
1
и х
4
. Длину пути 2 заносим в 1-ю и 4-ю клетки столбца T
+
(х
2
). На 3-
м шаге анализируются 1-я и 4-я строки матрицы смежности А. Находим
элементы а
12
=1, а
13
=0, а
43
=1. В соответствующие свободные клетки столбца T
+
(х
2
)
заносим длину пути от вершины х
2
,равную 3.Это возможно сделать только для
вершины х
3
, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м
шаге показывает, что из вершины х
3
нет исходящих дуг, следовательно процесс
формирования прямого транзитивного замыкания завершен.
x
1
x
2
x
3
x
4
x
5
x
6
T
+
(x
2
) T(x
1
)
x
1
0 1 1 0 0 0 2 x
1
0
x
2
0 1 0 0 1 0 0 x
2
1
A= x
3
0 0 0 0 0 0 3 x
3
1
x
4
0 0 1 0 0 0 2 x
4
3
x
5
1 0 0 1 0 0 1 x
5
2
x
6
1 0 0 0 1 1 x
6
x
1
x
2
x
3
x
4
x
5
x
6
x
1
x
2
x
3
x
4
x
5
x
6
x
1
0 1 1 0 0 0
x
2
0 1 0 0 1 0
x
3
0
0
0
0
0
0
4 2
3 3
1
3
1
4
3
2
2
0
1
3
2
1
x
2
a)
2 
Г-1 ( х1 ) = { х5 }
Г-2 ( х1 ) = { х2, х4 }
Г-3 ( х1 ) = { х1 }
Г-4 ( х1 ) = { х 5 }
T- ( х1 ) = х1 ∪ { х5 } ∪ { х2, х4 } ∪ { х1 } ∪ { х5 } = { х1, х2, х4, х5 }

      2.2.3.Нахождение транзитивных замыканий по матрице смежности.


Рассмотрим метод нахождения прямого транзитивного замыкания по матрице
смежности, показанной на рис.11,а для вершины х2 графа , изображенного на
рис.11,б. Вторая клетка уже занята нулем, поэтому 1 не заносим. 2-й шаг
начинается просмотром 5-й строки матрицы смежности, соответствующий
вершине х5 графа. Находим, что элементы а51=1 и а54=1, то есть из вершины х5
имеются дуги в вершины х1 и х4 или иначе из вершины х2 имеются пути длиной 2 в
вершины х1 и х4. Длину пути 2 заносим в 1-ю и 4-ю клетки столбца T+(х2). На 3-
м шаге анализируются 1-я и 4-я строки                           матрицы        смежности А. Находим
элементы а12=1, а13=0, а43=1. В соответствующие свободные клетки столбца T+(х2)
заносим длину пути от вершины х2,равную 3.Это возможно сделать только для
вершины х3, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м
шаге показывает, что из вершины х3 нет исходящих дуг, следовательно процесс
формирования прямого транзитивного замыкания завершен.


                            x1        x2   x3   x4    x5        x6             T+(x2)              T(x1)
  3                    x1   0         1    1    0     0         02             2         x1        0
      1                                                         0
                       x2   0         1    0    0     1         0 1            0         x2        1
 4
                A=     x3   0         0    0    0     0         03             3         x3        1
      3                                                          2
2                      x4   0         0    1    0     0         0              2         x4        3
                                                                 1
                       x5   1         0    0    1     0         0              1         x5        2
                       x6   1         0    0    0     1         1                        x6

                                      a)




                                                                     2    4    1    2         3        3

                                                                     x1   x2   x3   x4        x5       x6
                                                                     x1   x2   x3   x4        x5       x6
                                 x2                        x1        0    1    1    0         0        0
                                                           x2        0    1    0    0         1        0

Страницы