Прямым транзитивным замыканием некоторой вершины хi – T+( хi )является объединение самой вершины хiс прямыми отображениями 1-го порядка, второго порядка и т. д., т. е.
T+( хi ) = хi Г+1 ( хi ) Г+2( хi ) ...
Многозначные отображения находятся до тех пор, пока в них добавляются новые вершины.
Так, для графа на рис. 3.1.
Г+1 ( х1 ) = { х2, х3 }, Г+2( х1 ) = { х3, х5 }, Г+3( х1 ) = { х3, х1 }, Г+4( х1 ) = {х2, х3}.
Отображение четвертого порядка содержит те же элементы, что и отображение 1-го порядка, следовательно, других элементов в последующих отображениях не появится. Транзитивное замыкание для вершины х1получается следующим образом:
T+( х1 ) = х1 { х2, х3 } { х3, х5 } { х3, х1 } = { х1, х2, х3, х5 }.
Проанализировав множество вершин, входящих в T+( хi ), можно сделать вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути из вершины хi. Таким образом, можно дать второе определение T+( хi ).
Прямое транзитивное замыкание некоторой вершины хi T+( хi )– это множество вершин, достижимых из вершины хi, т. е. T ( хi ) = { хj | путь из хi в хj }.