Проектирование элементов информационного обеспечения и оценка функционирования АСОУ. Косников Ю.Н. - 18 стр.

                                                                                       18

     Для выявления основных свойств графов, кроме матрицы A,
используются матрицы A L , полученные возведением A в степень L, а
также матрица достижимости D, образованная их суммированием:
                                        N
                                  D = ∑AL .                                           (4)
                                        L =1

Они показаны на рисунке 2,б. Матрица A L показывает, сколько путей
длиной в L тактов (шагов продвижения информации от вершины к вершине
графа) имеется между двумя любыми вершинами x i , x j . Количество этих

путей определяется цифрой на пересечении i–той строки и j–того столбца
A L . Матрица D определяет, сколько всего путей, независимо от их длины,
соединяет две любые вершины графа. Так, по матрице D графа на
рисунке 2,б видно, что вершины 2 и 5 соединены двумя путями, а матрицы
A 1 , A 2 показывают, что один из этих путей имеет длину в один такт, а
другой — в два такта.
    Для конкретного графа значение N, равное количеству матриц A L ,
определяется его порядком, который зависит от порядка элементов графа.
Порядок Pj элемента x j формально определяется соотношением:

                    Pj = L при σ j (L ) > 0 и σ j (L + 1) = 0 ,                       (5)
где σ j (L ) — сумма элементов j-го столбца матрицы A L .

Физический смысл порядка элемента таков: это номер такта, на котором
элемент готов к своему формированию, то есть поступили все нужные для
этого компоненты. Входные (исходные) элементы графа имеют нулевой
порядок. На первом такте из них образуются элементы первого порядка.
На втором такте из элементов нулевого и первого порядка образуются
элементы второго порядка и т.д.
    Порядок    информационного           графа       совпадает           с   максимальным
порядком его элементов:                           N = max
                                                       j
                                                          Pj .

Для N справедливо соотношение:                  A N ≠ 0 , A N +1 = 0 ,
например, для графа на рисунке 2,а             N = 2.