Прямое транзитивное замыкание

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

T⁺(х_i) = х_i Г⁺¹ (х_i) Г⁺²(х_i) ...

Многозначные отображения находятся до тех пор, пока в них добавляются новые вершины.

Так, для графа на рис. 3.1.

Г⁺¹ (х₁) = { х₂, х₃ }, Г⁺²(х₁) = { х₃, х₅ }, Г⁺³(х₁) = { х₃, х₁ }, Г⁺⁴(х₁) = {х₂, х₃}.

Отображение четвертого порядка содержит те же элементы, что и отображение 1-го порядка, следовательно, других элементов в последующих отображениях не появится. Транзитивное замыкание для вершины х₁получается следующим образом:

T⁺(х₁) = х₁ { х₂, х₃ } { х₃, х₅ } { х₃, х₁ } = { х₁, х₂, х₃, х₅ }.

Проанализировав множество вершин, входящих в T⁺(х_i), можно сделать вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути из вершины х_i. Таким образом, можно дать второе определение T⁺(х_i).

Прямое транзитивное замыкание некоторой вершины х_i T⁺(х_i)– это множество вершин, достижимых из вершины х_i, т. е. T (х_i) = { х_j | путь из х_i в х_j }.