寻找偏序集子集的最大元素

Question

问题如下： 给定偏序集合S的子集，找到S的最大元素。

例如，考虑http://ndp.jct.ac.il/tutorials/Discrete/node34.html中偏序图的哈斯图。给定其子集{12, 2, 8}，则最大元素为12和8。

我不知道是否准确描述了问题。我认为该问题可能涉及一些排序或传递闭包的计算，但我有点困惑。

你能给我一些快速算法的方法吗？我希望将其保持在O(n^2)。

谢谢。

稍作说明。我的应用程序使用RDF图。如果存在表示<关系的特定边缘，则两个节点是可比较的。如果存在这样的显式关系或隐含的传递关系，则两个节点可能是可比较的。

因此，假设哈斯图正是我的RDF图。如果我从2开始进行深度优先搜索，如何知道8和12不可比较？它们可能不是明确的，但它们可能是隐含的。

- Alex

---

如果两个节点在排序关系上是可比较的，那么它们中至少有一个节点必须有一个后继节点来“传递”排序关系，对吗？ - Fred Foo

是的，没错。但是如果你有路径a-b-c，a和c是“隐式”可比较的。基于这一点，我怀疑我必须计算子集的每个节点的传递闭包，并清理可比元素。 - Alex

假设a-b表示a<b，则在这种情况下，c仍然是{a，b，c}的最大元素，因为它没有后继。a不是最大元素，因为它有一个后继b。 - Fred Foo

不用管我上次的评论。在这里，DFS遍历也可以找到正确答案，但是如果你只在子集{a,b,c,f}上运行它并忽略其余的后继关系，则无法找到正确答案。 - Fred Foo

Answer 1

如果您知道排序关系的最小子集，可以在线性时间内完成此操作：将其视为DAG，然后进行深度优先遍历以查找所有没有后继节点的顶点。

- Fred Foo