Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




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

 


1 2 0 

 


1 1 0 

 
 


sign0


2 1   0


1 1 .


 
3 0 


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) будем называть их булевым произведением и обозначать через AB. В соответствии с определением sign(A · B) = AB. Если A = (aij) и B = (bij), то элементы булева произведения AB = (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. Тогда матрица

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

 

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

 






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

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных