傳遞閉包

數學中，集合X上的二元關係 R 的傳遞閉包是包含R的X上的最小的遞移關係。

例如，如果 X 是由人組成的集合（不論人活著與否）而R是關係「為父子」，則 R 的傳遞閉包是關係「x 是 y 的祖先」。再比如，如果 X 是空港的集合而關係 xRy 為「從空港 x 到空港 y 有直航」，則 R 的傳遞閉包是「可能經一次或多次航行從 x 飛到 y」。

存在性和描述

對於任何關係 R，R 的傳遞閉包總是存在的。傳遞關係的任何家族的交集也是傳遞的。進一步地，至少存在一個包含 R 的傳遞關係，也就是平凡的: X × X。R 傳遞閉包給出自包含 R 的所有傳遞關係的交集。

我們可以用更具體術語來描述 R 的傳遞閉包如下。定義在 X 上的一個關係 T，稱 xTy 若且唯若存在有限的元素(x_i)序列，使得 x = x₀ 並且

x₀Rx₁, x₁Rx₂, …, x_n−1Rx_n 和 x_nRy

形式上寫為

T=\bigcup _{i\in \omega }R^{i}

容易檢查出關係 T 是傳遞的並且包含 R。進一步地，任何包含 R 的傳遞關係也包含 T，所以 T 是 R 的傳遞閉包。

證實 T 是包含 R 的最小傳遞關係

設 A 是任何元素的集合。

假定: $\exists$ G_A 傳遞關係 R_A $\subseteq$ G_A $\wedge$ T_A $\not \subseteq$ G_A。所以 $\exists$ (a,b) $\not \in$ G_A $\wedge$ (a,b) $\in$ T_A. 所以，特定的 (a,b) $\not \in$ R_A。

現在通過 T 的定義，我們知道了 $\exists$ n $\in \mathbb {N}$ (a,b) $\in$ Rⁿ_A。接著， $\forall$ i $\in \mathbb {N}$ , i $<$ n $\Rightarrow$ e_i $\in$ A。所以，有從 a 到 b 路徑如下: aR_Ae₁R_A...R_Ae_(n-1)R_Ab。

但是，通過 G_A 在 R_A 上的傳遞性， $\forall$ i $\in \mathbb {N}$ , i $<$ n $\Rightarrow$ (a,e_i) $\in$ G_A，所以，(a,e_(n-1)) $\in$ G_A $\wedge$ (e_(n-1),b) $\in$ G_A，所以通過 G_A 的傳遞性，我們得到了 (a,b) $\in$ G_A。矛盾於 (a,b) $\not \in$ G_A。

因此， $\forall$ (a,b) $\in$ A $\times$ A, (a,b) $\in$ T_A $\Rightarrow$ (a,b) $\in$ G_A。這意味著 T $\subseteq$ G，對於任何包含 R 的傳遞的 G。所以，T 是包含 R 的最小傳遞閉包。

推論

如果 R 是傳遞的，則 R = T。

用途

注意兩個傳遞關係的併集不必須是傳遞的。為了保持傳遞性，必須採用傳遞閉包，例如在取兩個等價關係或預序的並的時候。為了獲得新的等價關係或預序，必須選用傳遞閉包（自反性和對稱性在等價關係的情況下是自動的）。

有向無環圖(DAG)的傳遞閉包是 DAG 的可到達性關係和一個嚴格偏序。

與複雜性的關係

在計算複雜性理論中，複雜度類 NL 嚴格對應於可使用一階邏輯和傳遞閉包表達的邏輯句子的集合。這是因為傳遞閉包性質有密切關係於 NL-完全問題 STCON，找到在一個圖中的有向路徑。類似的，類 L 是一階邏輯帶有交換傳遞閉包。在向二階邏輯增加了傳遞閉包的時候，我們得到 PSPACE。

有關概念

關係 R 的傳遞簡約是有 R 作為它的傳遞閉包的最小關係。一般來說它不唯一。

算法

計算圖的傳遞閉包的有效算法可見於 here （頁面存檔備份，存於網際網路檔案館）。最簡單的技術是Floyd-Warshall算法。

引用

Lidl, R. and Pilz, G., 1998, Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics, Springer, ISBN 0-387-98290-6

外部連結

"Transitive closure and reduction （頁面存檔備份，存於網際網路檔案館）", The Stony Brook Algorithm Repository, Steven Skiena .