Достижимостей с помощью матрицы смежности

Матрица смежности, как отмечалось выше, полностью определяет структуру графа. Возведем матрицу смежности в квадрат. Пусть элемент d⁽²⁾_ik матрицы А² определяется по формуле

(2.7)

Слагаемое (d_ijd_jk) в уравнении (2.7) отлично от нуля тогда и только тогда, когда оба числа d_ij и d_jk отличны от нуля, в противном случае слагаемое равно 0. Поскольку из соотношений d_ij ¹ 0, d_jk ¹ 0 следует существование путей длиной 2 из вершины x_i к вершине x_k, проходящих через вершину x_j, то d⁽²⁾_ik равно числу путей, идущих из x_i в x_k.

Аналогично, если d^(p)_ik является элементом матрицы A^р, то d^(p)_ik равно числу путей длиной р, идущих от x_i к x_k.

Однако надо подчеркнуть, что в матрицах достижимостей и обратных достижимостей не требуется учета числа путей из вершины x_i в вершину x_j. В матрицах отмечается лишь то, что есть такой путь или его нет, т.е. необходима операция нормализации. С учетом последнего замечания формула для определения матрицы достижимостей R на основе матрицы смежности А имеет вид

R = (E + A + A² + … + A^p) //норм. (2.8)

Здесь Е – единичная матрица, а «норм» означает операцию нормализации, заключающуюся в том, что элементы матрицы R, не равные нулю, заменяются на 1.

Таким образом, матрица R может быть получена последовательно выполняемой (слева направо) операцией суммирования указанных в (2.7) матриц до тех пор, пока «текущая» матрица не перестанет изменяться при очередной операции суммирования. Для получения матрицы ограниченных достижимостей значение р должно быть ограничено.

С учетом определения (2.4) матрицу обратных достижимостей можно определить с помощью матрицы смежности по формуле

Q = (E + A^T + (A^T)² + … + (A^T)^P) // норм. (2.9)

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

Формулы (2.8) и (2.9) справедливы как для одноуровневых (вершины задаются одним индексом), так и для многоуровневых (вершины задаются несколькими индексами) графов. Так, для многоуровневого графа (рис. 2.3) матрицa достижимостей , вычисленная на основе формулы (2.8) , имеет вид

R(2,2)={r }=

		k=1	k=1	k=1	k=2	k=2	k=2
		l=1	l=2	l=3	l=1	l=2	l=3
i=1	j=1
i=1	j=2
i=1	j=3
i=2	j=1
i=2	j=2
i=2	j=3