組合數(shù)學(xué)第二章_第1頁(yè)
已閱讀1頁(yè),還剩45頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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ì)算

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論