傳遞閉包

  此條目介紹的是二元關係的傳遞閉包。關於集合的傳遞閉包，請見「傳遞集合」。

數學中，集合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 .