偏序集反鏈分解演算法

㈠ 最長不降子序列的長度等於不升子序列的數目

這么來說吧
對於一個序列 不斷做最長不升序列 每次將結果中的數去掉 這個序列能做多少次 這個次數等於最長不降子序列的長度

以前VIJOS上有道叫 導彈攔截的題要用這個

㈡ 反鏈的離散數學

設<A>是一個偏序集合，在A的一個子集中，如果每兩個元素都是有關系的，則稱這個子集為鏈。在A的一個子集中，如果每兩個元素都是無關的，則稱這個子集為反鏈。
我們約定，若A的子集只有單個元素，則這個子集既是鏈又是反鏈。
例如A表示一個單位里所有工作人員的集合， 表示領導關系，則<A，>為一偏序集，其中部份工作人員之間有領導關系的組成一個鏈。還有部份工作人員沒有領導關系的組成一個反鏈。

㈢ noip1999提高組

dilworth定理，最小鏈劃分 = 最長反鏈。

隨便找一本離散數學和組合數學的書都有證明

演算法，粘給你吧

導彈攔截是一個經典問題：求一個序列的最長不上升子序列，以及求能最少劃分成幾組不上升子序列。第一問是經典動態規劃，第二問直接的方法是最小路徑覆蓋，但是二分圖匹配的復雜度較高，我們可以將其轉化成求最長上升子序列，其最大值即等於不上升子序列的最小劃分數。這就涉及到組合數學中偏序集的Dilworth定理。（第二問的貪心方法其實就是這個定理的證明過程）

先介紹一下偏序關系：
偏序是在集合X上的二元關系≤（這只是個抽象符號，不是「小於或等於」），它滿足自反性、反對稱性和傳遞性。即，對於X中的任意元素a,b和c，有:
自反性：a≤a;
反對稱性：如果a≤b且b≤a，則有a=b;
傳遞性：如果a≤b且b≤c，則a≤c 。

帶有偏序關系的集合稱為偏序集。
令(X,≤)是一個偏序集，對於集合中的兩個元素a、b，如果有a≤b或者b≤a，則稱a和b是可比的，否則a和b不可比。

在X中，對於元素a，如果任意元素b，由b≤a得出b=a，則稱a為極小元。
一個反鏈A是X的一個子集，它的任意兩個元素都不能進行比較。
一個鏈C是X的一個子集，它的任意兩個元素都可比。

下面是兩個重要定理：
定理1 令（X,≤）是一個有限偏序集，並令r是其最大鏈的大小。則X可以被劃分成r個但不能再少的反鏈。
其對偶定理稱為Dilworth定理：
定理2 令（X,≤）是一個有限偏序集，並令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。
雖然這兩個定理內容相似，但第一個定理證明要簡單一些。此處就只證明定理1。
證明：設p為最少反鏈個數
(1)先證明X不能劃分成小於r個反鏈。由於r是最大鏈C的大小，C中任兩個元素都可比，因此C中任兩個元素都不能屬於同一反鏈。所以p>=r。
(2)設X1＝X，A1是X1中的極小元的集合。從X1中刪除A1得到X2。注意到對於X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中極小元的集合，從X2中刪除A2得到X3……最終，會有一個Xk非空而X(k+1)為空。於是A1,A2,…,Ak就是X的反鏈的劃分，同時存在鏈a1<=a2<=…<=ak，其中ai在Ai內。由於r是最長鏈大小，因此r>=k。由於X被劃分成了k個反鏈，因此r>=k>=p。因此r=p，定理1得證。

回過頭來看導彈攔截第二問。我們定義偏序關系≤：a≤b表示a出現不遲於b且a的值不小於b的值。這個偏序集的最長反鏈即最長上升子序列，它的不上升子序列是偏序集的鏈。由Dilworth定理可知，不上升子序列的最小劃分數＝最長上升子序列的長度。

p.s. 這里的貪心方法是，每次選出所有的在它前面沒有大於或等於它的數作為一組。其實我們每次選的是偏序集的最小元，因此我們最終得到的答案就是上面的k。由r<=p及r>=k>=p可以得到r=k=p，因此貪心正確。

㈣ 設偏序集<A，R>，其中A=｛2，3，4，.....，1000｝，R表示整除關系，那麼該偏序集的所

{x|x∈A , 500＜x≤1000}

㈤ 設<A,R>為一個偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除關系。

先求出關系矩陣

1 1 1 1 1 1 1 1

0 1 0 1 1 0 1 1

0 0 1 0 1 1 1 1

0 0 0 1 0 0 1 0

0 0 0 0 1 0 1 1

0 0 0 0 0 1 0 1

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

（1）R出的哈斯圖如下：

(5)偏序集反鏈分解演算法擴展閱讀：

哈斯圖得名於Helmut Hasse；依據Birkhoff，這么叫是因為Hasse有效的利用了它們。但是Hasse不是第一個使用它們的人，它們早就出現在如Vogt (1895)中。盡管哈斯圖被設計為手工繪制偏序集合的技術，最近已經使用圖繪制技術自動來生成它們了。

術語「哈斯圖」還可以稱呼作為抽象有向無環圖的傳遞簡約，獨立於這個圖的任何繪制形式。但是這里不採用這種用法。

圖中的每個結點表示集合A中的一個元素，結點的位置按它們在偏序中的次序從底向上排列。即對任意a，b屬於A，若a≤b且a≠b,則a排在b的下邊。如果a≤b且a≠b，且不存在c∈A滿足a≤c且c≤b，則在a和b之間連一條線。這樣畫出的圖叫哈斯圖，又稱偏序集合圖。

㈥ 偏序問題

偏序集的兩個定理：
定理1> 令(X,≤)是一個有限偏序集,並令r是其最大鏈的大小,則X可以被劃分成r個但不能再少的反鏈.
其對偶定理稱為Dilworth定理：
定理2> 令(X,≤)是一個有限偏序集，並令m是反鏈的最大的大小,則X可以被劃分成m個但不能再少的鏈.

說二元的吧,三元給你思考的空間
根據定理二,(X,Y,<=)的反鏈,就是X1<X2 &&Y1>Y2或者X1>X2&&Y1<Y2,他們是對稱的,求出哪一個結果都可以.如果是X1<X2 &&Y1>Y2,就是求出point{X,Y}按照x單調遞增,y單調遞減的最長子序列.
關於如何求最長單調遞減(增)子序列,可以參考我的博客(參考資料).

㈦ 用C++實現偏序集的反鏈分解演算法。 求高手解答。

o(）＾）)o 唉，網上就你一個問這個問題的，坐等答案啊

㈧ 對於任意性和存在性問題怎樣解釋

根據規則對人們行為規定和限定的范圍和程度的不同，分強行性規則和任意性規則。 a.強行性規則是指內容規定具有強制性質，不允許人們隨便加以更改的法律規則。 b.任意性規則是指規定在一定范圍內，允許人們自行選擇或者協商確定為與不為、為的方式以及法律關系中的權利義務內容的法律規則。 權利性規則，大多為任意性規則，但也存在強行性規則；職權性規則和義務性規則通常屬於強行性規則。存在性定理是一類定性描述。要把某種離散對象按某個確定的約束條件進行安排，如果這種特定的安排是否存在還不確定，就需要首先討論這種特定安排的存在性問題。是關於偏序集的極大極小的定理，該定理斷言：對於任意有限偏序集，其最大反鏈中元素的數目必等於最小鏈劃分中鏈的數目。