-
狄爾沃斯定理
鎖定
- 中文名
- 狄爾沃斯定理
- 外文名
- Dilworth's theorem
- 所屬學科
- 數學(組合設計)
- 別 名
- Dilworth定理
- 簡 介
- 關於偏序集的極大極小的定理
狄爾沃斯定理基本介紹
定理 對偏序集<A,≤>,設A中最長鏈的長度是n,則將A中元素分成不相交的反鏈,反鏈個數至少是n。
證明施歸納於n。
假設對於n=k,結論成立。考慮n=k+1的情況,當A中最長鏈的長度為k+1時,令M為A中極大元的集合,顯然M是一條反鏈。而且A-M中最長鏈的長度為k。由歸納假設,可以把A-M分成至少k個不相交的反鏈,加上反鏈M,則A可分成至少k+1條反鏈。
這個定理稱為狄爾沃斯(Dilworth)定理或偏序集的分解定理,這是組合學三大存在性定理之一,有廣泛的應用。這種分解是所有分解方法中反鏈個數最少的一種分解方法,因為A不可能分解成n-1條反鏈。假若只有n-1條反鏈,那麼最長鏈的n個元素中必有2個元素被分到同一個反鏈,顯然這與反鏈的定義矛盾。
有窮偏序集分解成n條反鏈的過程可以採用下面的方法去做。
算法 偏序集反鏈分解算法:
輸入:偏序集A.
輸出:A中的反鏈
.
1.i←1
2.
的所有極大元的集合(顯然
是一條反鏈)
3.令
.
4.if A≠∅
5.
6.轉2
注意:從A中去掉Bi中的元素時,同時去掉連接這些元素與被它覆蓋的元素之間的邊,行2~3每執行一次,最長鏈的長度減少l,同時產生一條新的反鏈。因為最長鏈長度為n,恰好執行n次,算法結束,並得到n條反鏈。
[3]
狄爾沃斯定理相關介紹
組合數學中有很多存在性定理,其中三大基本定理是經常使用的工具:一是1935年P.Hall提出的“相異代表組定理”;二是1950年R.P.Dilworth發現的“偏序集分解定理(狄爾沃斯定理)”;三是1930年F.P.Ramsey發表的“廣義鴿洞原理”
[4]
。
關於R.P.Dilworth的狄爾沃斯定理的相關介紹:
大家知道,許多離散事物對象之間存在着種種“次序”關係,例如一組事物的排隊,某些現象出現的先後,生物的代代相傳等,但也不是任何一類事物間都有同一種“序”的關係,因此近代數學從無數具體的對象關係裏抽象出來的“偏序集”(即半序集)概念,就顯得更加重要而有用,現代組合數學中的若干重要理論就是建立在偏序集概念的基礎上的。
由有限個元素(離散事物)所構成的有限偏序集往往可分解成若干條“鏈”(即有起始元的全序子集),位於不同鏈上的元素之間可以沒有序關係,這些沒有序關係的元素叫作“無序元”,由無序元所作成的子集叫作無序子集,那麼,把一個偏序集分解成鏈的最少條數m和該偏序集所含最大無序子集的元素個數M之間有什麼關係呢?Dilworth發現它們之間恰好具有相等關係:m=M。這個定理也是利用精細的歸納法證明的,它不僅對一般組合數學十分重要,而且對生物科學也有很大用處。例如,由這個定理可以推斷:在mn+1個實驗用的小鼠中,要麼有m+1個是代代相傳的,要麼有n+1個是彼此沒有親緣關係的。”(這裏可把上下代關係看作序的關係,故mn+1個小鼠作成一個偏序集)
[4]
。