找到一個序集的子集

問題的最大因素是：給定一個序集的子集S找到S.找到一個序集的子集

的最大元素例如，考慮偏序集的HASS圖中http://ndp.jct.ac.il/tutorials/Discrete/node34.html。鑑於它的一個子集，例如：{12,2,8}，最大元素是12和8.

我不知道我是否會精確地描述問題。我認爲這個問題可能涉及到傳遞閉包的一些排序或計算，但我有點困惑。

你能給我一些快速算法的方法嗎？我想保留在O（n^2）

謝謝。

稍作澄清。我的應用程序正在使用RDF圖。如果存在代表<關係的特定邊，則兩個節點具有可比性。如果存在這樣的顯式關係或隱式傳遞關係，那麼兩個節點可能是可比較的。

因此，假設hass圖正好是我的RDF圖。如果我從2開始深入優先搜索，我怎麼知道8和12是不可比的？他們可能並不明確，但可能是隱含的。

2012-04-13 Alex

如果兩個節點是可比較的wrt。訂貨關係，那麼他們中至少有一個必須有一個「轉讓」訂貨關係的後繼節點，對吧？ – 2012-04-13 14:38:48

是的，這是正確的。但是如果你有路徑a-b-c，a和c是「隱含」可比的。基於此，我懷疑我必須計算子集中每個節點的傳遞閉包，並對可比元素進行「清理」。 – Alex 2012-04-13 15:30:03

假設a-b意味着a 2012-04-13 16:15:05

如果您知道排序關係的最小子集，則可以在線性時間內執行此操作：將其視爲DAG，然後執行深度優先遍歷以查找所有沒有後繼的頂點。

2012-04-13 12:23:30

回答