离散数学r的自反闭包，传递闭包和对称闭包该怎么算

Python011

离散数学r的自反闭包，传递闭包和对称闭包该怎么算,第1张

自反闭包，是在原关系基础上，加上所有自反关系。

类似地，传递闭包，是在原关系基础上，补充符合传递性要求的关系。

对称闭包，是在原关系基础上，补充符合对称性要求的关系。

传递闭包,最简单的技术是采用 【弗洛伊德算法】

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

Floyd-Warshall算法的原理是动态规划。

设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

1.若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；

2.若最短路径不经过点k，则Di,j,k = Di,j,k − 1。

因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

代码请见：

关系的闭包 设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R¢表示，使得R¢具有关系的自反(对称、传递)性质，R¢就是R的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)。： Kenneth H.Rosen 第6版离散数学的定义：设R是非空集合A上的关系，在关系R中，可能有或无性质P，如自反(r)，对称(s)，传递(t)，若存在包含R，满足性质P的关系S，使得S是所有包含R，满足P的关系的子集，那么称S是R关于P的闭包（有时这样的闭包不存在）