5.5. Использование логических операций в теории графов

Логические операции используются в алгоритмах на графах, например, при поиске путей в графе. При этом матрица смежности графа умножается сама на себя. Умножение проводится по правилам обычной алгебры с тем исключением, что операция суммы заменяется дизъюнкцией, а операция умножения – конъюнкцией. Тогда квадрат матрицы смежности представляет матрицу всех путей длиной 2, куб – длиной 3 и т.д. Рассмотрим пример (рис. 36).

Рис. 36. Ориентированный граф и его матрица смежности

Найдем все пути длиной 2:

Получили матрицу M² всех путей в графе длиной 2. Процесс получения первой строки M² подробно рассмотрен в табл. 22.

Таблица 22

Вычисление первой строки M²

0		1		0	Первая строка М
Ù		Ù		Ù	Поразрядная конъюнкция
0		1		1	Первый столбец М
0	Ú	1	Ú	0	=1, т.е. имеется путь из x1bx1 по двум дугам: t1, t4
Дизъюнкция результатов