跳至內容

傳遞閉包

維基百科,自由的百科全書


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

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

存在性和描述

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

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

x0Rx1, x1Rx2, …, xn−1RxnxnRy

形式上寫為

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

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

A 是任何元素的集合。

假定: GA 傳遞關係 RAGA TAGA。所以 (a,b)GA(a,b)TA. 所以,特定的 (a,b)RA

現在通過 T 的定義,我們知道了 n (a,b)RnA。接着,i, in eiA。所以,有從 ab 路徑如下: aRAe1RA...RAe(n-1)RAb

但是,通過 GARA 上的傳遞性,i, in (a,ei)GA,所以,(a,e(n-1))GA (e(n-1),b)GA,所以通過 GA 的傳遞性,我們得到了 (a,b)GA矛盾於 (a,b)GA

因此,(a,b)AA, (a,b)TA (a,b)GA。這意味着 TG,對於任何包含 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

外部連結