Структурные матрицы и операции с ними
Для структурного анализа сетей (нахождения путей, сечений и их характеристик) целесообразно использовать структурные матрицы и некоторые операции, основанные на применении математического аппарата булевой алгебры. Каждый путь μ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/ – в полном объеме.