組合數(shù)學(xué)第二章

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

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

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

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

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

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

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

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

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

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