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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

противном случае) совпадает со строкой x
i
матрицы R, т.е Q = R
T
, где R
T
-
матрица, транспонированная к матрице достижимостей R.
Матрица контрдостижимостей показана на рис.12 ,г.
Следует отметить, что поскольку все элементы матриц R и Q равны 1 или
0, то каждую строку можно хранить в двоичной форме, экономя затраты памяти
ЭВМ. Матрицы R и Q удобны для обработки на ЭВМ, так как с вычислительной
точки зрения основными операциями являются быстродействующие логические
операции.
Алгоритм построения матриц достижимостей и контрдостижимостей приведен в
прил.3.
. Упражнения 2.3 .
1. Для графа построить матрицу
достижимости R и
контрдостижимости Q.
Ответ:
Матрица достижимости
R=
Матрица контрдостижимости
Q=
2. Для графа, приведенного на
рисунке, найти матрицы
достижимости и
контрдостижимости.
Ответ:
X
1
X
2
X
3
X
4
X
5
X
1
X
2
X
3
X
4
X
5
X
1
X
2
X
3
X
4
X
5
X
1
X
2
X
3
X
4
X
5
x
8
x
3
x
5
x
7
x
6
x
4
x
2
x
1 
противном случае) совпадает со строкой xi матрицы R, т.е Q = RT, где RT -
матрица, транспонированная к матрице достижимостей R.
          Матрица контрдостижимостей показана на рис.12 ,г.
          Следует отметить, что поскольку все элементы матриц R и Q равны 1 или
0, то каждую строку можно хранить в двоичной форме, экономя затраты памяти
ЭВМ. Матрицы R и Q удобны для обработки на ЭВМ, так как с вычислительной
точки зрения основными операциями являются быстродействующие логические
операции.
Алгоритм построения матриц достижимостей и контрдостижимостей приведен в
прил.3.
.         Упражнения 2.3                                            .
1. Для графа построить матрицу
достижимости R и
контрдостижимости Q.
Ответ:
Матрица достижимости

                  X1   X2   X3   X4   X5
            X1
     R=     X2
            X3
            X4
            X5
          Матрица контрдостижимости

                 X1 X2 X3 X4 X5
          X1
    Q=    X2
          X3
          X4
          X5
2. Для графа, приведенного на
рисунке, найти матрицы                          x1                  x2
достижимости и
контрдостижимости.
                                                          x7   x5
Ответ:                                     x8                             x3


                                                                          x4
                                                     x6

Страницы