組合數(shù)學第二章

1、2024/3/19,計算機科學與技術(shù)學院,1,第二章 鴿巢原理和Ramsey定理,2.1 鴿巢原理的簡單形式 2.2 鴿巢原理的加強形式 2.3 Ramsey定理,2024/3/19,計算機科學與技術(shù)學院,2,鴿巢原理的簡單形式,組合存在性定理Ramsey定理（鴿巢原理為其最簡形式）偏序集分解定理（Dilworth定理）相異代表系存在定理（Hall定理）鴿巢原理是組合學中最簡單、最基本原理也叫抽屜原理或狄利克雷原理(Dir

2、ichlet(1805-1859)19世紀德國數(shù)學家)。,2024/3/19,計算機科學與技術(shù)學院,3,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,4,鴿巢原理的簡單形式,注意1，應(yīng)用時要分清物體與盒子以及物體總數(shù)與盒子總數(shù)。注意2，定理只是存在性定理，不能找出具體的物體。注意3，不能被推廣到只存在n個(或更少)物體的情形。,2024/3/19,計算機科學與技術(shù)學院,5,鴿巢原理的簡單形式,2024/3/19,計算

3、機科學與技術(shù)學院,6,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,7,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,8,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,9,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,10,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,11,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,12,鴿巢原理的簡單形

4、式,,,2024/3/19,計算機科學與技術(shù)學院,13,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,14,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,15,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,16,鴿巢原理的簡單形式,2024/3/19,計算機科學與技術(shù)學院,17,作業(yè),pp. 24，2.1, 2.3,2024/3/19,計算機科學與技術(shù)學院,18,鴿巢原理的加強形式,202

5、4/3/19,計算機科學與技術(shù)學院,19,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,20,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,21,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,22,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,23,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,24,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學

6、院,25,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,26,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,27,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,28,鴿巢原理的加強形式,2024/3/19,計算機科學與技術(shù)學院,29,鴿巢原理的加強形式,習題2.2 在一個邊長為1的正方形內(nèi)任取9個點，證明：以這些點為頂點的各個三角形中，至少有一個三角形的面積不大于1/8。,2024/3/1

7、9,計算機科學與技術(shù)學院,30,作業(yè),pp. 25，2.11, 2.12,2024/3/19,計算機科學與技術(shù)學院,31,Ramsey定理,核心思想是：“任何一個足夠大的結(jié)構(gòu)中必定包含一個給定大小的規(guī)則子結(jié)構(gòu)”1928年英國數(shù)學家、哲學家兼經(jīng)濟學家Frank Ramsey(1903-1930) 在倫敦數(shù)學會上宣讀一篇 “論形式邏輯中的一個問題”的論文，奠定了Ramsey理論的基礎(chǔ)。Ramsey定理已經(jīng)發(fā)展成為Ramsey理論并滲透到

8、諸多研究領(lǐng)域，而且仍然是研究熱點問題。1958年6-7月號美國《數(shù)學雜志》上登載著這樣一個有趣的問題：“任何一個6人聚會，必有3個人相互認識或者相互不認識”，這個問題實質(zhì)上就是一個Ramsey問題，,2024/3/19,計算機科學與技術(shù)學院,32,Ramsey定理,2024/3/19,計算機科學與技術(shù)學院,33,Ramsey定理,,,,,2024/3/19,計算機科學與技術(shù)學院,34,Ramsey定理,判斷樹,2024/3/19,計算

9、機科學與技術(shù)學院,35,Ramsey定理,2024/3/19,計算機科學與技術(shù)學院,36,Ramsey定理,2024/3/19,計算機科學與技術(shù)學院,37,Ramsey定理,,,,V1,V5,V3,V2,,V4,,,,V1,V5,V3,V2,,V4,,V7,,V6,2024/3/19,計算機科學與技術(shù)學院,38,Ramsey定理,2024/3/19,計算機科學與技術(shù)學院,39,Ramsey定理,對上面的幾個命題進行歸納，可以得出如下定義

10、：定義 2.5.1 對于任意給定的兩個正整數(shù)p和q，如果存在最小的正整數(shù)R(p,q)使得當N≥ R(p,q)時，對KN任意進行紅、藍兩邊著色，KN中均有紅色Kp，或藍色Kq，則R(p,q)稱為Ramsey數(shù). Ramsey數(shù)的簡單性質(zhì)定理 對任意正整數(shù)p，q，有（1） R(p,q) = R(q, p) （2） R(p,2) =p,2024/3/19,計算機科學與技術(shù)學院,40,Ramsey定理,2024/3/19,計算