Структурные матрицы и операции с ними

Для структурного анализа сетей (нахождения путей, сечений и их характеристик) целесообразно использовать структурные матрицы и некоторые операции, основанные на применении математического аппарата булевой алгебры. Каждый путь μhst (сечение σlst) будем представлять произведением (конъюнкцией) символов ребер, образующих этот путь (сечение), а множество путей (сечений) - дизъюнкцией (логической суммой) этих произведений.

Так, для сети, изображенной на рис. 2, запишем:

; .

Структурной матрицей В сети G с N узлами будем называть квадратурную матрицу порядка N, в которой каждому узлу аi, соответствуют i-я строка и i-й столбец:

.

Здесь i, j = 1, N. Вхождения βij определяются по следующему правилу:

βij = 1 при i = j
bij (или соответственно буквенные символы: с при i<j и при i>j) в случае, если есть непосредственная связь (ребро, линия, канал) от узла ai к узлу аj)
0, если такой непосредственной связи нет.

Если все ребра не направлены, то матрица будет симметричной по отношению к главной диагонали, а если есть направленные ребра, то несимметричной. Для сети, изображенной на рис. 6 структурная матрица будет иметь вид:

.

Структурную матрицу можно рассматривать как булеву матрицу и применять к ней аппарат булевой алгебры (алгебры логики); в частности, может быть применен аппарат преобразования булевых матриц и булевых определителей. Не останавливаясь подробно на этом аппарате, отметим только некоторые особенности, связанные с интерпретацией сети булевыми матрицами

Рис. 6. Пример сети

В булевой алгебре, в которой переменные и функции могут принимать только два значения (0 и 1), используются три операции: логическое произведение (конъюнкция, обычно обозначаемая точкой, которая может опускаться, а иногда знаком ), логическое сложение (дизъюнкция, для которой будем применять символ V, хотя иногда используется знак +) и инверсия (черта над переменной или функцией).

В отличие от «обычной» алгебры, в булевой алгебре 1V1 = 1, а отсюда вытекают и некоторые особые преобразования:

Aa = a; aVa = a; 1a = a; 1Va = 1; a(aVb) = a; aVab = a;

a = 0; aV = 1.

Произведение двух булевых квадратных матриц и порядка N приводит к квадратной матрице С = АВ = того же порядка, вхождения которой γij равны сумме (дизъюнкции) почленных произведений i-й строки матрицы А и i-го столбца матрицы В:

.

При возведении структурной матрицы в квадрат получим новую структурную матрицу С = В2 с единицами по главной диагонали, а ее вхождения γ2ij будут включать в виде суммы как не посредственное ребро bij (если оно было в сети), так и все пути ранга 2 (проходящие через один узел) от узла аi к узлу aj вида bilblj (если они есть в сети).

Так, при возведении в квадрат матрицы В1соответствующей сети рис. 6, для вхождения γ215 получим (выписываем первую строку и пятый столбец и производим перемножение)

1 a 0 0 b
γ215 = b c f h 1
b V ac V 0 V 0 V b = b V ac,

т.е. от узла 1 к узлу 5 имеются прямое ребро b и путь ас ранга 2 (через узел 2). Проведя расчет, получим следующую матрицу В21 путей ранга r ≤ 2:

.

Для возведения в третью степень перемножаются матрицы В2 и В. Так, для определения вхождения γ314 перемножаем первую строку матрицы В2 и четвертый столбец матрицы В:

1 a b adVb bVac
0 d g 1
γ314 = 0 V ad V b g V adVb V b Vac = adV b Vb gVac
                       

Возведение структурной матрицы в q-ю степень приводит к тому, что каждое вхождение новой матрицы будет содержать все пути от узла ai к узлу аj, ранга не более q, т. е. . Имеется некоторое qmax, такое, что дальнейшее возведение матрицы в степень не меняет ее вхождений, т. е.

.

Матрица Мхар = называется характеристической или матрицей всех путей, содержит все возможные в сети пути между узлами. Поскольку максимальный ранг пути не может превышать N-1, то qmax ≤ N-1. Аналогично могут быть составлены матрицы М* путей, обладающих свойством *, для которых вхождениями будут множества т*ij.

Остановимся на некоторых правилах вычисления определителей (детерминантов) булевых матриц. Вычисление (раскрытие) таких определителей производится по методам, аналогичным методам вычисления определителей в обычной алгебре, с той разницей, что все члены, появляющиеся в процессе вычисления, берутся только со знаком V и производятся преобразования, вытекающие из законов булевой алгебры. Отметим некоторые особенности булевых определителей: а) если в определителе в каждой строке и столбце имеется хотя бы одна единица, то определитель тождественно равен 1; б) если в определителе какой-либо ряд (строка или столбец) состоит из одних нулей, то определитель тождественно равен нулю; в) если перед определителем имеется множитель х, то во всех вхождениях определителя х может быть заменен единицей, а - нулем.

Вычисление определителей производится разложением определителя по вхождениям какого-либо ряда (строки или столбца), что дает возможность при каждой операции снизить порядок определителя на единицу. При этом для уменьшения операций по «поглощению» лишних слагаемых рекомендуется раскладывать по ряду, в котором нет единиц.

Разложение определителя матрицы А ранга N с вхождениями aij по i-й строке будет иметь вид:

,

где |Ajj|-определитель матрицы дополнения, полученной из матрицы А вычеркиванием i-й строки и j-го столбца.

Для определителей третьего и второго порядка можно применить обычную процедуру раскрытия по диагонали, считая bijbji = 0 или a = 0.

Задание на самоподготовку:

1. Ознакомиться с указанной литературой: /1, 2, 3, 4/ – в полном объеме.

Наши рекомендации