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

Если 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 = ai1b1j ∨ = ai2b2j ∨ … ∨ 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.