Достижимость и обратная достижимость вершин графа

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

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

Матрица достижимостей R[1,1] = {r_ij} и матрица обратных достижимостей Q[1,1] = {q_ij} определяется следующим образом:

r_{ij= {} 1, если вершина x_j достижима из x_i, (2.3)

0 в противном случае;

q_{ij= {} 1, если из вершины x_j можно достигнуть (2.4)

вершину x_i, 0 в противном случае.