Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T+(xi) – это множество вершин, в которые есть пути из вершины xi, а T–(хj) – множество вершин, из которых есть пути в xj , то T+(xi) T–(xj)– множество вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от xi к xj . Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин xi и xj . Все остальные вершины графа называются несущественными или избыточными, поскольку их удаление не влияет на пути от xi к xj .
Рис. 4.2. Орграф
Так для графа на рис. 4.2 нахождение вершин, входящих в путь, например из вершины х2 в вершину х4 , сводится к нахождению Т+( х2) ={ х2, х3, х4, х5, х6}, Т-( х4) ={ х1, х2, х3, х4, х5}, и их пересечения T+(х2) T–(х4) ={ х2, х3, х4, х5}.