Булевы матрицы и операции над ними

Если G – граф (ориентированный или нет) без кратных дуг, то его матрица смежности A является булевой, то есть состоит из нулей и единиц. Для произвольной матрицы X = (xij) с неотрицательными элементами будем обозначать через sign(X) булеву матрицу, полученную из X заменой всех ее положительных элементов единицами. Например,

1 2 0 

 

1 1 0 

2 1   0

1 1 .

1 0 

Равенство sign(X) = X означает, что матрица X булева. Легко

видеть, что

sign(X + Y) = sign(sign(X) + sign(Y)), sign(X · Y) = sign(sign(X)·sign(Y))

в случае, когда X и Y неотрицательные матрицы, для которых

определены соответствующие матричные операции. Далее, если матрицы X и Y имеют одинаковую размерность, то

sign(X + Y) = sign(X) ∨ sign(Y) (дизъюнкция булевых матриц вычисляется поэлементно).

Пусть A и B – булевы матрицы. Матрицу sign(A · B) будем называть их булевым произведением и обозначать через A ∗ B. В соответствии с определением sign(A · B) = A ∗ B. Если A = (aij) и B = (bij), то элементы булева произведения A ∗ B = (cij) определяются формулами

cij = ai 1 b 1 j ∨ = ai 2 b 2 j ∨ … ∨ ainbnj,

где n – число столбцов матрицы A и число строк матрицы B. Положим A [ k ] = sign(Ak) и будем называть матрицу A [ k ] булевой степенью матрицы A.

Если A – матрица смежности графа G, то на месте (i, j) матрицы A [ k ] находится 1, если на графе G существует путь длины k из i в j, и 0 в противном случае. Пусть n – число вершин графа G. Тогда матрица

E ∨ A ∨ A [ k ] ∨…∨ A [ n –1]

содержит 1 на месте (i, j) в том и только том случае, когда на графе G имеется хотя бы один путь из вершины i в вершину j.

Не нашли, что искали? Воспользуйтесь поиском: