Нахождение множества вершин, входящих в путь

Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T⁺(x_i) – это множество вершин, в которые есть пути из вершины x_i, а T–(х_j) – множество вершин, из которых есть пути в x_j, то T⁺(x_i) T–(x_j)– множество вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от x_i к x_j. Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин x_i и x_j. Все остальные вершины графа называются несущественными или избыточными, поскольку их удаление не влияет на пути от x_i к x_j.

Рис. 4.2. Орграф

Так для графа на рис. 4.2 нахождение вершин, входящих в путь, например из вершины х₂ в вершину х₄, сводится к нахождению Т⁺(х₂) ={ х₂, х₃, х₄, х₅, х₆}, Т^-(х₄) ={ х₁, х₂, х₃, х₄, х₅}, и их пересечения T⁺(х₂) T^–(х₄) ={ х₂, х₃, х₄, х₅}.