Матрицы достижимостей и контрадостижимостей

Матрица достижимостей определяется следующим образом:

Множество вершин графа , достижимых из заданной вершины , состоит из таких элементов , для которых -й элемент в матрице равен 1. Это множество можно представить в виде

.

Матрица контрадостижимостей (обратных достижимостей) определяется следующим образом:

Аналогично построению достижимого множества можно сформировать множество , используя следующее выражение:

.

Из определений следует, что -й столбец матрицы совпадает с -й строкой матрицы , т. е. , где – матрица, транспонированная к матрице .

Пример 2. Найти матрицы достижимостей и контрадостижимостей для графа, приведенного на рис. 5.

°

°

°

°

°

°

°

Рис. 5.

Определим множества достижимостей для вершин графа:

,

,

,

,

,

,

.

Следовательно, матрицы достижимостей и контрадостижимостей имеют вид:

, .

Так как – множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от к , то вершины этого множества называются существенными или неотъемлемыми относительно концевых вершин и . Все остальные вершины называются несущественными или избыточными, поскольку их удаление не влияет на пути от к .

Можно определить также матрицы ограниченных достижимостей и контрдостижимостей, если потребовать, чтобы длины путей не превышали некоторого заданного числа. Тогда будет верхней границей длины допустимых путей.

Граф называют транзитивным, если из существования дуг и следует существование дуги . Транзитивным замыканием графа является граф , где – минимально возможное множество дуг, необходимых для того, чтобы граф был транзитивным. Очевидно, что матрица достижимостей графа совпадает с матрицей смежности графа , если в матрице на главной диагонали поставить единицы.