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

Вершина графа называется достижимой из вершины того же графа, если существует по крайней мере один путь из в .

Множество вершин R(v_i), достижимых из некоторой вершины , определяется следующим выражением:

2.9

Действительно, первым элементом множества является вершина , которая достижима из себя самой с помощью пути длины нуль; Г(v_i) – множество вершин v_j, достижимых из v_i с использованием путей длины единица; Г²(v_i) – множество вершин, достижимых из v_i с использованием путей длины два; - множество вершин, достижимых из v_i с использованием путей длины p. Таким образом, множество R(v_i) получается путем последовательного выполнения слева направо операции объединения в выражении (2.9) до тех пор, пока мощность текущего множества не перестанет увеличиваться при очередной операции объединения. С этого момента последующие операции объединения не будут давать новых элементов множеству R(v_i). Число объединений, которые необходимо выполнить, зависит от графа G. Но если граф конечен, то p<n, где n – число вершин графа.

Матрицей достижимостей называется квадратная матрица порядка n, элемент которой

Пример. Построить матрицу достижимостей графа G, представленного на рис. 2.6.

Рис. 2.6

Решение. X={x₁, x₂, x₃, x₄}; Г(х₁)={x₂}; Г(х₂)={x₃}; Г(х₃)={x₄}; Г(х₄)={x₃}.

;

;

;

.

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

.

Очевидно, что элементы d_i,i=1, i=1, 2, …, n, так как каждая вершина достижима из себя самой.

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

2.10

где Q(v_i) – множество таких вершин v_iÎV, что из любой вершины этого множества можно достигнуть вершину v_i:

2.11

где - множество вершин, из которых достижима вершина v_i с использованием пути длины единица; ) – множество вершин, из которых достижима вершина v_i с использованием пути длины два и т.д. Операция объединения в выражении (2.10) выполняется слева направо до тех пор, пока очередное объединение не перестанет изменять “текущее множество”.

Пример. Построить матрицу контрдостижимостей Q для графа G рис. 2.6.

Решение.

Матрица контрдостижимостей будет иметь вид:

.

Из определения матриц D и Q следует, что Q=D^T. Так как D(v_i) является множеством вершин, достижимых из , а Q(v_j) – множество вершин, из которых достижима вершина v_j, то D(v_i) - множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от v_i к v_j. Эти вершины называются существенными (неотъемлемыми) относительно двух концевых вершин v_i и v_j. Вершины называются несущественными (избыточными), так как их удаление не влияет на пути от v_i к v_j.