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

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

Определение матриц достижимостей и обратных достижимостей с помощью матрицы смежности

Матрица смежности, как отмечалось выше, полностью определяет структуру графа. Возведем матрицу смежности в квадрат. Пусть элемент 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}=.