Заметим, что нас не интересует число путей любой конкретной длины из вершины vi в вершину vj. Эта информация, получаемая в процессе вычисления степеней A, далее игнорируется. Для того, чтобы сократить объем вычислений, можно отказаться от получения указанной информации и использовать в вычислениях просто реализуемые булевские матричные операции, которые мы определим согласно.
Обозначим булевскую сумму C двух матриц A и B размера n*n как С=АÈВ, а булевское произведение – D=AÇB.
Элементы матриц C и D задаются соотношениями
Заметим, что элемент dij легко получается путем просмотра i-й строки матрицы A слева направо и одновременно j-го столбца матрицы B сверху вниз. Если k-й элемент в строке матрицы A и k-й элемент в столбце матрицы B равны 1 для какого-нибудь k, то dij=1. В противном случае dij=0.
Булевы матрицы более экономичны в вычислительном отношении, чем целочисленные. Действительно, запоминание булевой матрицы требует меньшего объема оперативной памяти ЭВМ по сравнению с целочисленной матрицей той же размерности. Кроме того, выполнение на компьютере логических операций над булевыми матрицами требует меньшего объема вычислений, чем над целочисленными матрицами тех же размерностей.
|
|
Матрица смежностей, так же как и путевая матрица, является булевской матрицей. Заметим, что .
Единственная разница между A2 и A(2) заключается в том, что A(2) является булевской матрицей и элемент на пересечении i-й строки и j-го столбца A(2) равен 1 в том случае, когда существует по крайней мере один путь длины 2 из vi в vj. Аналогичное положение имеет место для A3 и A(3) и в общем случае для Ar и A(r) при любом целом положительном r. Из этих рассуждений ясно, что матрица достижимости P задается выражением
Например, если
то
Данный метод получения матрицы достижимости ориентированного графа называется алгоритмом Уоршалла (Warshall S.A. A Theorem on Boolean Matrices. - J.ACM, 1962, 9, pp.11-12).
Тема 5. Функции и отображения. Инъекция, сюръекция, биекция. Представление функций в ЭВМ. Операции. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева и справа. Способы задания операций. Таблица Кэли.