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

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

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

Поскольку является множеством таких вершин которые достижимы из с использованием путей длины 1 (т. е. такое множество вершин, для которых в графе существуют дуги и поскольку является множеством вершин, достижимых из с помощью путей длины 1, то множество состоит из вершин, достижимых из с использованием путей длины 2. Аналогично является множеством вершин, которые достижимы из с помощью путей длины

Так как любая вершина графа которая достижима из должна быть достижима с использованием пути (или путей) длины 0, или 1, или или (с некоторым конечным, но, возможно, достаточно большим значением то множество вершин, достижимых из можно представить в виде

Таким образом, множество может быть получено последовательным выполнением (слева направо) операций объединения в соотношении (2.1), до тех пор, пока «текущее» множество не перестанет увеличиваться по размеру при очередной операции объединения. С этого момента последующие операции не будут давать новых членов множеству и, таким образом, будет образовано достижимое множество Число объединений, которое нужно выполнить, зависит от графа, но, очевидно, что число меньше числа вершин в графе.

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

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

Контрадостижимым множеством графа является множество таких вершин, что из любой вершины этого множества можно достигнуть вершину Аналогично построению достижимого множества на основе соотношения (2.1) можно «сформировать» множество используя следующее выражение:

где

Операции выполняются слева направо до тех пор, пока очередная операция объединения не перестанет изменять «текущее» множество

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

2.1. Пример

Найти матрицы достижимостей и обратных достижимостей для графа приведенного на рис. 2.1. Матрица смежности графа

Рис. 2.1.

С имеет вид

Множества достижимостей находятся с помощью соотношения (2.1):

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

матрица обратных достижимостей такова:

Следует отметить, что поскольку все элементы матриц равны 1 или О, то каждую строку можно хранить в двоичной форме, используя одно (или больше) машинных слов. Таким

образом, нахождение матриц с вычислительной точки зрения является довольно простой задачей, поскольку объединение множеств в соответствии с выражениями (2.1) и (2.2) и сравнение «текущих» множеств после каждого объединения, проводимое для выяснения необходимости продолжения процесса построения соответствующих множеств, — все это можно осуществить на ЭВМ с помощью одной логической операции.

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

Матрицы достижимостей и обратных достижимостей, определенные выше, являются полными в том смысле, что на длины путей от к не накладывались никакие ограничения. С другой стороны, можно определить матрицы ограниченных достижимостей и контрадостижимостей — надо потребовать, чтобы длины путей не превышали некоторого заданного числа. Эти ограниченные матрицы тоже могут быть построены с помощью соотношений (2.1) и (2.2) — надо действовать точно так, как раньше, при нахождении «неограниченных» матриц, но только теперь будет верхней границей длины допустимых путей.

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