定義
對于任何關系R,R的傳遞閉包總是存在的。傳遞關系的任何家族的交集也是傳遞的。進一步的,至少存在一個包含R的傳遞關系,也就是平凡的。R傳遞閉包給出自包含R的所有傳遞關系的交集。
算法
針對在已有傳遞閉包的基礎上新增序偶後的傳遞閉包求解問題,提出了一種基于新增序偶的傳遞閉包求解算法,并給出了詳細證明過程。該算法在已有的傳遞閉包基礎上,通過把新增序偶及該序偶的所有派生間接指向序偶添加到已有的傳遞閉包中實現求解過程,從而使算法的時間複雜度降低為O(n2),并且不受稀疏矩陣或序偶鍊的鍊長等不确定因素影響,最後通過一個實例說明了該算法的執行過程。
用途
注意兩個傳遞關系的并集不必須是傳遞的。為了保持傳遞性,必須采用傳遞閉包。例如,這出現在取兩個等價關系或預序的并的時候。為了獲得新的等價關系或預序,必須選用傳遞閉包(自反性和對稱性在等價關系的情況下是自動的)。
複雜性關系
在計算複雜性理論中,複雜度類NL嚴格對應于可使用一階邏輯和傳遞閉包表達的邏輯句子的集合。這是因為傳遞閉包性質有密切關系于NL完全問題,找到在一個圖的有向路徑。類似的,L是一階邏輯帶有交換傳遞閉包。在向二階邏輯增加了傳遞閉包的時候,我們得到PSPACe。