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

 

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

Так, для сети, изображенной на рис. 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 -го столбца матрицы В:

.

При возведении структурной матрицы в квадрат получим новую структурную матрицу С = В² с единицами по главной диагонали, а ее вхождения γ²_ij будут включать в виде суммы как не посредственное ребро b_ij (если оно было в сети), так и все пути ранга 2 (проходящие через один узел) от узла а_i к узлу a_j вида b_ilb_lj (если они есть в сети).

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

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). Проведя расчет, получим следующую матрицу В²₁ путей ранга r ≤ 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-ю степень приводит к тому, что каждое вхождение новой матрицы будет содержать все пути от узла a_i к узлу а_j, ранга не более q, т. е. . Имеется некоторое q_max, такое, что дальнейшее возведение матрицы в степень не меняет ее вхождений, т. е.

.

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

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

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

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

,

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

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

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

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