寻找一个坐姿子集的最大元素 [英] Finding maximal elements of a poset's subset

问题描述

问题如下：
给定一个波姿的子集S找到S的最大元素。

The problem is the following: Given a poset's subset S find the maximal elements of S.

例如，考虑波幅的hass图 http://ndp.jct.ac.il/tutorials/Discrete/node34.html 。给定它的一个子集，例如：{12，2，8}，最大元素是12和8。

For example consider the hass diagram of the poset in http://ndp.jct.ac.il/tutorials/Discrete/node34.html. Given a subset of it ex: {12, 2, 8} the maximal elements are 12 and 8.

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

I do not know if I describe precisly the problem. I think the problem might involves some sorting or computation of transitive closure but I am a little confused.

您能给我一些快速算法的方法吗？我想保留在O（n ^ 2）

Could you give me some approach for a fast algorithm? I would like to keep it in O(n^2)

谢谢。

需要澄清一下。我的应用程序使用RDF图。如果存在表示<的特定边，则两个节点是可比较的。关系。如果存在这样的显式关系或隐式可传递关系，则两个节点可能是可比较的。

A little clarification. My application is using RDF graphs. Two nodes are comparable if there exists a specific edge that represent the < relation. Two nodes might be comparable if there is such an explicit relation or an implicit transitive one.

因此，假设hass图正是我的RDF图。如果我从2开始进行深度优先搜索，我怎么知道8和12没有可比性？它们可能不是显式的，但可能是隐式的。

So assume that the hass diagram is exactly my RDF graph. If I start from 2 doing a depth-first search how do I know that the 8 and 12 are not comparable? They might not be explicitly but they might be implicitly.

推荐答案

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

You can do this in linear time if you know a minimal subset of the ordering relation: regard it as a DAG, then do a depth-first traversal to find all vertices that have no successor.

这篇关于寻找一个坐姿子集的最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！