传递闭包矩阵怎么算

传递闭包、即在数学中，在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。例如，如果X是(生或死)人的集合而R是关系“为父子”，则 R 的传递闭包是关系“x 是 y 的祖先”。再比如，如果X是空港的集合而关系 xRy 为“从空港 x 到空港 y 有直航”，则R的传递闭包是“可能经一次或多次航行从x飞到 y”。

对于任何关系 R，R 的传递闭包总是存在的。传递关系的任何家族的交集也是传递的。进一步的，至少存在一个包含 R 的传递关系，也就是平凡的: X × X。R 传递闭包给出自包含 R 的所有传递关系的交集。

形式上写为：

容易检查出关系 T 是传递的并且包含 R。进一步的，任何包含 R 的传递关系也包含 T，所以 T 是 R 的传递闭包。

有关概念：

关系 R 的传递简约是有 R 作为它的传递闭包的最小关系。一般的说它不是唯一的。

证明%

设 A 是任何元素的集合。

假定: GA 传递关系 RAGA TAGA。所以 (a，b)GA(a，b)TA. 所以，特定的 (a，b)RA。

现在通过 T 的定义，我们知道了 n (a，b)RnA。接着，i， in eiA。所以，有从 a 到 b 路径如下: (n-1)RAb。

但是，通过 GA 在 RA 上的传递性，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 的最小传递闭包。