主题
Search

传递约简

一个二元关系 R 在一个集合 X 上的传递约简是最小关系 R^' 在 X 上，且具有与 R 相同的传递闭包。 因此，对于 X 的任何元素 a 和 b，如果 aRb 成立，且不存在 X 的元素 c 使得 aRc 和 cRb 成立，则 aR^'b 成立。

一个图 G 的传递约简是最小的图 R(G)，使得 C(G)=C(R(G))，其中 C(G) 是 G 的传递闭包 (Skiena 1990, p. 203)。

另请参阅

自反约简, 传递闭包

使用 Wolfram|Alpha 探索

参考文献

Aho, A.; Garey, M. R.; and Ullman, J. D. "The Transitive Reduction of a Directed Graph." SIAM J. Comput. 1, 131-137, 1972.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

在 Wolfram|Alpha 中引用

传递约简

请按如下方式引用

Weisstein, Eric W. "传递约简。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/TransitiveReduction.html

主题分类