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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Таким образом в столбце T
+
(х
2
) стоят числа равные длине пути от
вершины х
2
к соответствующим вершинам графа. Путь от х
2
к х
3
равный 3
показан штриховой линией на рис.11,б. В столбце T
+
( х
2
) отмечены все
вершины, достижимые из вершины х
2
, следовательно они входят в T
+
( х
2
).
T
+
( х
2
) = { х
1
, х
2
, х
3
, х
4
, х
5
}.
Во втором столбце показано построение прямого транзитивного замыкания
вершины х
1
- T
+
( х
1
).
T
+
( х
1
) = { х
1
, х
2
, х
3
, х
4
, х
5
}.
Нахождение обратного транзитивного замыкания по матрице смежности
показано на рис.11,в. Рассмотрим нахождение обратного транзитивного
замыкания вершины х
3
- T
-
( х
3
), которое начинается с занесения 0 в 3-ю клетку
строки T
-
( х
3
). На 1-м шаге алгоритма, помеченного стрелкой с цифрой 1
просматриваем 3-й столбец матрицы А. Определяем элементы, равные 1, то
есть а
13
=1 и а
43
=1. Следовательно в графе из вершин х
1
и х
4
есть дуги в вершину
х
3
. Заносим 1 в 1-ю и 4-ю клетки T
-
(х
3
). На втором шаге просматриваем 1-й и 4-й
столбец матрицы A. Находим a
51
=1, a
61
=1, a
54
=1 и проставляем 2 (так как длина
пути от этих вершин до вершины x
3
равна 2) в свободные клетки T
-
(x
3
) , т.е. в 5-ю
и 6-ю клетки. 3-й шаг заключается в просмотре 5-го и 6-го столбца матрицы
A. Элементы a
25
=1, a
65
=1, a
66
=1 позволяют поставить 3 во 2-ю клетку строки T
-
( x
3
)
. 4-й шаг просмотра 2-го столбца дает элементы a
12
= 1 и a
22
= 1, уже вошедшие
в T
-
(x
3
). Итак сформировано обратное транзитивное замыкание для вершины х
3
.
T
-
( х
3
) = { х
1
, х
2
, х
3
, х
4
, х
5
, х
6
}.
Числа, стоящие в клетках T
-
( х
3
), показывают длину кратчайшего пути от
соответствующих вершин до вершины х
3
.
Во второй строке показано формирование обратного транзитивного
замыкания вершины х
1
.
T
-
( x
1
) = { х
1
, х
2
, х
5
, х
6
}.
На основе рассмотренного метода был разработан алгоритм,
реализованный программно. Блок-схема алгоритма построения транзитивного
замыкания (прямого или обратного) и программа приведены в прил. 2. 
      Таким образом в столбце T+(х2) стоят числа равные                    длине    пути   от
вершины х2 к соответствующим вершинам графа. Путь от х2 к х3 равный                        3
показан    штриховой        линией        на    рис.11,б. В столбце T+ ( х2 )   отмечены все
вершины, достижимые из вершины х2, следовательно они входят в T+ ( х2 ).
      T+ ( х2 ) = { х1, х2, х3, х4, х5 }.
      Во втором столбце показано построение прямого транзитивного замыкания
вершины х1 - T+ ( х1 ).
      T+ ( х1 ) = { х1, х2, х3, х4, х5 }.
      Нахождение обратного транзитивного замыкания по матрице смежности
показано    на     рис.11,в.      Рассмотрим        нахождение    обратного     транзитивного
замыкания вершины х3 - T- ( х3 ), которое начинается с занесения 0 в 3-ю клетку
строки T- ( х3 ). На 1-м шаге алгоритма, помеченного стрелкой с цифрой 1
просматриваем 3-й столбец матрицы А. Определяем элементы, равные 1, то
есть а13=1 и а43=1. Следовательно в графе из вершин х1 и х4 есть дуги в вершину
х3. Заносим 1 в 1-ю и 4-ю клетки T-(х3). На втором шаге просматриваем 1-й и 4-й
столбец матрицы A. Находим a51=1, a61=1, a54=1 и проставляем 2 (так как длина
пути от этих вершин до вершины x3 равна 2) в свободные клетки T- (x3) , т.е. в 5-ю
и 6-ю клетки. 3-й шаг заключается в просмотре 5-го и 6-го столбца матрицы
A. Элементы a25=1, a65=1, a66=1 позволяют поставить 3 во 2-ю клетку строки T-( x3 )
. 4-й шаг просмотра 2-го столбца дает элементы a12 = 1 и a22 = 1, уже вошедшие
в T- (x3). Итак сформировано обратное транзитивное замыкание для вершины х3.
      T- ( х3 ) = { х1, х2, х3, х4, х5, х6 }.
      Числа, стоящие в клетках T-( х3 ), показывают длину кратчайшего пути от
соответствующих вершин до вершины х3.
      Во второй         строке          показано   формирование обратного транзитивного
замыкания вершины х1.
      T- ( x1 ) = { х1, х2, х5, х6 }.
      На     основе       рассмотренного           метода   был    разработан       алгоритм,
реализованный программно. Блок-схема                   алгоритма построения транзитивного
замыкания (прямого или обратного) и программа приведены в прил. 2.

Страницы