Обратное транзитивное замыкание

Обратным транзитивным замыканием некоторой вершины х_i –T^-( х_i )является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n -го порядка, т. е.

T^-( х_i ) = х_i Г^-1(х_i ) Г^-2(х_i ) ...

Иначе, обратное транзитивное замыкание для некоторой вершины х_i – T^-( х_i )– это множество вершин, из которых достижима вершина х_i, т. е. T^-( х_i ) = { x_j | путь из x_j в х_i }.

Рассмотрим построение обратного транзитивного замыкания для графа на рис. 3.1.

Г^-1(х₁) = { х₅ }, Г^-2(х₁) = { х₂, х₄ }, Г^-3(х₁) = { х₁ }, Г^-4 (х₁) = { х₅ }, T^-(х₁) = х₁ { х₅ } { х₂, х₄ } { х₁ } { х₅ } = {х₁, х₂, х₄, х₅}.