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

Обратным транзитивным замыканием некоторой вершины х_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^-(х₁) = х₁ { х₅ } { х₂, х₄ } { х₁ } { х₅ } = {х₁, х₂, х₄, х₅}.