2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩32頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、1,中國(guó)余數(shù)定理是說明: 一個(gè)整數(shù)x與兩個(gè)互質(zhì)的整數(shù)n,m相除,可以得到兩種表示結(jié)果: x = pm + a 和 x = qn+ b ,其中a 和 b 分別是小于除數(shù)m 和 n的余數(shù),例如: 19 = 9×2+1 = 3×5+4;其中m=2;n=5是互質(zhì) 而選擇n=4的話: 19 = 4×4+3=8×2+2=pm+2 只有一種表示形式。,2,Ramse

2、y問題可以看成是鴿巢原理的推廣下面舉例說明Ramsey問題。例1 6 個(gè)人中至少存在3人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)。證:這個(gè)問題與K6的邊2著色存在同色三角形等價(jià)。假定用紅藍(lán)兩種顏色對(duì)完全圖K6著色。,第二章鴿巢原理 2.2 Ramsey定理,3,設(shè)K6的頂點(diǎn)集為{v1 , v2 , ··· , v6 },dr(v)表示與頂點(diǎn) v 關(guān)聯(lián)的紅色邊的條數(shù),db(v)表示與 v 關(guān)聯(lián)的藍(lán)色邊的條數(shù)。在

3、K6 中,有:dr(v)+ db(v)=5,由鴿巢原理將5條邊分配成2種顏色,至少有:[(5-1)/2]+1=3條邊同色?,F(xiàn)將證明過程用判斷樹表示如下:,,,,,,,,,,,,,,,,v1,v6,v5,v4,v3,v2,4,dr(v1)≥3?,db(v1)≥3,設(shè)(v1v2) (v1v3) (v1v4)為紅邊,設(shè)(v1v2) (v1v3) (v1v4)為藍(lán)邊,△v2v3v4是紅△ ?,△v2v3v4是藍(lán)△ ?,設(shè)( v2v3 )

4、是藍(lán)邊,設(shè)( v2v3 )是紅邊,△v1v2v3是藍(lán)△,△v1v2v3是紅△,,,,,,,,,,√,√,Y,N,N,N,Y,Y,,,,,,,,,,,,,,,,,,,v6,v5,v4,v3,v2,v1,,5,定理說明:六點(diǎn)夠成的完全圖中,用紅、蘭兩種顏色對(duì)邊涂色,總能得到一個(gè)紅三角形或者是一個(gè)蘭三角形,注意: 6是染兩色時(shí)出現(xiàn)同色三角形的最小點(diǎn)數(shù)。若取5點(diǎn),則可舉出反例(如P22圖2.2 所示),圖中就沒有同色的三角形,即可使K5不存

5、在同色三角形。,v5,v4,v3,v2,v1,,,,,,,,,,,6,,例2 9人行,或有3人互相認(rèn)識(shí),或有4人互 不認(rèn)識(shí)。例3 18人行,定有4人或互相認(rèn)識(shí),或互不認(rèn)識(shí)。上述問題,可用圖論的方法予以解決。 即將n個(gè)人視為n個(gè)頂點(diǎn)(設(shè)n個(gè)頂點(diǎn)中任意3點(diǎn)不共線),并構(gòu)造n點(diǎn)完全圖Kn,對(duì)Kn中的邊染,7,以紅、藍(lán)兩種顏色,2人相識(shí)染紅色,不相識(shí) 染藍(lán)色, 最后求證圖中必存在同色三角形,或同色完全

6、四邊形。,例2證明 第一步:若將K9染色,則其中必存在一點(diǎn),從這點(diǎn)到其余8點(diǎn)的邊中,同色者不等于3。 設(shè)若不然,K9中每個(gè)點(diǎn)與其余8個(gè)頂點(diǎn)所成之邊都是恰染3條紅色(或藍(lán)色), 現(xiàn)從每個(gè)端點(diǎn)統(tǒng)計(jì)各,8,點(diǎn)引出的這些紅色(或藍(lán)色)邊的總數(shù)應(yīng)是 3×9=27, 但這是不可能的, 因每條邊關(guān)聯(lián)兩個(gè)端點(diǎn),對(duì)這種統(tǒng)計(jì), 所有點(diǎn)引出的紅色(或藍(lán)色)連邊的總數(shù)應(yīng)為偶數(shù)。結(jié)論是,必存在一點(diǎn), 從該點(diǎn)到其余各點(diǎn)的邊染紅色(

7、或藍(lán)色)者一定大于3或小于3。第二步:(1)設(shè)從v1向其余8點(diǎn)引出的邊中,染紅色者多于3條,即至少有4條,不妨設(shè)為:,9,(v1, v2), (v1, v3), (v1, v4), (v1, v5)。再看v2, v3, v4 , v5 所成完全圖K4,若有一紅色邊,則其兩端點(diǎn)連同 v1已構(gòu)成紅色三角形, 否則全為藍(lán)色,這時(shí)v2, v3, v4 , v5就構(gòu)成一藍(lán)色完全四邊形。(2)設(shè)從v1向其余8點(diǎn)引出的邊中,

8、紅色邊少于3條,即至多有2條,這時(shí)從v1引出的藍(lán)色邊至少會(huì)有6條,不妨設(shè)為(v1, v2), (v1, v3), …, (v1, v7) 。,10,再看 v1, v2, v3, v4, v5, v6所成完全圖K6,由定理1, 其中若有紅色三角形,則結(jié)論已真;若K6中有藍(lán)色三角形,則其3個(gè)頂點(diǎn)連同v1即構(gòu)成一藍(lán)色完全四邊形,結(jié)論亦真。  由(1)及(2), 定理得證。  注意:當(dāng)n

9、>9時(shí),定理2自然成立。但當(dāng)n=8時(shí),可舉出反例(如下圖所示),即可使其既無(wú)同色三角形,又無(wú)同色完全四邊形。,11,K8 二染色,12,,dr(v1)≥4?,db(v1)≥6,設(shè)(v1v2) (v1v3) (v1v4)(v1v5)是4紅邊,設(shè)(v1v2) ··· (v1v7)是6條藍(lán)邊,K4(v2v3v4v5)是藍(lán)K4 ?,K6(v2···v7)中有紅△ ?,設(shè)(v2v3)是紅

10、邊,△v1v2v3是紅△,設(shè)△v2v3v4是藍(lán)△,K4(v2v3v4v5)是藍(lán)K4,√,√,,,,,,,,,,,,Y,Y,Y,N,N,N,用判斷樹也可以進(jìn)行證明如下,13,,∴ K9的邊紅、藍(lán)2兩種著色,必有紅色三角 形或藍(lán)色K4。同理可證 K9的紅、藍(lán)2著色,必有藍(lán)色三角形或紅色K4 。 (紅△ ∨ 藍(lán)K4) ∧ (藍(lán)△∨ 紅K4)=存在同色K4或紅△及藍(lán) △=同色K4 ∨(紅△ ∧ 藍(lán)△ )兩個(gè)同色三角

11、形  同色完全四邊形,,,14,我們可以用下列形式表示Ramsey定理: K6 ? K3 , K3 而K5 ? K3 , K3 更一般地, Ramsey定理可敘述為: 如果m≥2及n≥2是兩個(gè)整數(shù),則存在一個(gè)正整數(shù)p使得Kp ? Km , Kn ,這還不是最一般的形式。 如果Kp ? Km , Kn

12、 , 那么對(duì)任何的q≥p 成立 Kq ? Km , Kn ,則 p是滿足要求的最小數(shù)。,,15,,,Ramsey數(shù),定義為:使得Kp ? Km , Kn 成立 的最小整數(shù)p, 稱為Ramsey數(shù); 記為:r(m,n) = p 將上述的問題一般化:給定一對(duì)正整數(shù)m, n,存在一個(gè)最小的正整數(shù)p ,對(duì)p個(gè)頂點(diǎn)的完全圖的邊任意紅、藍(lán)2著色,存在m個(gè)頂點(diǎn)的紅邊完全圖或n個(gè)頂點(diǎn)的藍(lán)邊完全圖。

13、 Ramsey數(shù)是相對(duì)完全圖Km , Kn而定義的。,16,Ramsey定理則斷言了Ramsey數(shù)的存在性。 例如我們已經(jīng)證明了:r( 3, 3) = 6等平凡Ramsey數(shù) r( 2, n)=n和r( m, 2)=m證明:假設(shè)1: r( 2, n) ≤ n 事實(shí)上,如果我們把Kn 的邊涂成紅色或者藍(lán)色,那么,或者Kn 的某條邊是紅色(因此我們就得到一個(gè)紅色的K2) ,或者Kn所有的邊都是藍(lán)色的(因此我們就

14、得到一個(gè)藍(lán)Kn ),17,這樣我們就得到最小的Ramsey數(shù)為n; 假設(shè)2: r( 2, n) > n-1事實(shí)上,如果我們把Kn-1 的邊都涂成藍(lán)色,那么,我們既得不到紅K2 ,也得不到藍(lán)Kn 。 用類似的方法可以證明另一個(gè)平凡Ramsey數(shù) r( m, 2) = m一般地,可以交換紅色和藍(lán)色的位置得到:

15、 r(m, n) = r( n, m),18,例:在K4中,我們用紅,藍(lán)兩種顏色涂色。要求 要么其中一種顏色只涂一條邊,例如用紅色涂一條邊,正好是紅K2,要么另一種顏色涂所有的邊,正好是藍(lán)K4 ;,,,,,,,v3,v2,v4,v1,,,,,,,v3,v2,v4,v1,19,關(guān)于平凡Ramsey數(shù)r(m, n)的一些已知結(jié)論可列 表如下: r(3, 3)=6 ;用兩種顏色涂K6 能得到K3或

16、K3 r(3, 4)=r(4, 3)=9;用兩種顏色涂K9 能得到K3或K4r(3,5)=r(5,3)=14;用兩種顏色涂K14 能得到K3或K5r(3,6)=r(6,3)=18;用兩種顏色涂K18 能得到K3或K6r(3,7)=r(7,3)=23;用兩種顏色涂K23 能得到K3或K7,20,r(3,8)=r(8,3)=28;用兩種顏色涂K28 能得到K3或K8r(3,9)=r(9,3)=36;用兩種顏色涂K36 能得到K3或

17、K9 40≤ r(3, 10)=r(10, 3) ≤43;r(4,4)=18;用兩種顏色涂K18 能得到紅K4或藍(lán)K4r(4,5)=r(5,4)=25;用兩種顏色涂K25 能得到K4或K5 43≤ r(5, 5) ≤55;,21,Ramsey定理還可以推廣到任意多種顏色的情 況,如果n1,n2,n3是大于2的三個(gè)整數(shù),則存在一個(gè)整數(shù)p使得:

18、 Kp ? Kn1 , Kn2, Kn3 記為:r (n1, n2, n3) = P就是說,如果Kp的每條邊涂上紅色、藍(lán)色、或綠色,那么或者存在一個(gè)紅Kn1或者存在一個(gè)藍(lán)Kn2或者存在一個(gè)綠Kn3。,22,使得該結(jié)論成立的最小整數(shù)p, 也稱為Ramsey數(shù); 例:若將K17的邊染以紅、藍(lán)、黃三色,則一定會(huì)出現(xiàn)一個(gè)同色三角形。 證明 設(shè)V={v0, v1, …, v16

19、}為K17的點(diǎn)集,任取一點(diǎn)v0,在v0與其余16點(diǎn)相連的邊中, 因染有三色,由鴿巢原理知至少有[16/3]+1=6條邊染以同色。不妨設(shè)(v0, v1), (v0, v2), …,(v0, v6)這6條邊染為紅色。考察v1, v2, v3, v4 v5, v6組成的完全圖K6,分兩種情況討論:,23,(1)如果該K6中有一條邊為紅色,設(shè)為(v1, v2),則v0, ,v1, v2所成三角形已是同色三角形, 定理得證;(2) 如果該K6中

20、沒有紅色邊, 即只染有黃、 藍(lán)兩色, 則由Ramsey定理這個(gè)K6中就有同色三角形,定理得證; 特別地,定理中的17點(diǎn)恰是染三色時(shí)的最少點(diǎn)數(shù),亦即 K16用三色涂染時(shí),可以構(gòu)造一種圖形,使得其中不存在同色三角形。,24,本結(jié)論也可以用判斷樹來證:證:設(shè)三色為 r ,b ,g.則對(duì)K17的任一頂點(diǎn)v 有 dr(v) + db(v) + dg(v) = 16;因[16/3]+1 =6 ,故任一頂點(diǎn)與其他頂點(diǎn)的連線中,至少有6條同色.

21、不妨設(shè)dr(v1)≥6, (v1v2) ,(v1v3), …,(v1v7) 都是紅邊。從而可得如下判斷樹。,25,K6(v2···v7)中無(wú)紅邊 ?,K6(v2···v7)中有紅邊,K6(v2···v7)中藍(lán)、綠2著色,有藍(lán)K3或綠K3,設(shè)(v2v3)為紅邊,△v1v2v3是紅色的,,,,,,原題得證.,Y

22、,N,26,若進(jìn)一步將用兩種、三種顏色擴(kuò)展到用任 意有限種顏色涂染完全圖的邊,則有: 一種顏色: r(m)= 3,兩種顏色r(m, n)=6, 三種顏色r(n1, n2, n3)=17; 也有人證明了r (n1,n2,n3 ,n4)= 65 。找出r的準(zhǔn)確值是件困難的事情,目前僅知道以上幾種。,27,Ramsey數(shù)的性質(zhì): 定理:當(dāng)a , b ≥2時(shí),有 r ( a , b

23、)≤ r ( a -1 , b )+ r ( a , b-1 )成立 證:對(duì)r ( a -1 , b )+ r ( a , b-1 ) 個(gè)頂點(diǎn)的完全圖紅藍(lán)2著色.任取其中一點(diǎn) v,有 dr(v) + db(v) = r( a -1 , b ) + r( a , b-1 )-1從而可得判斷樹如下.,28,,dr(v)≥r (a-1 , b) ?,db(v)≥r (a, b -1 ),與 v 以紅邊相連的r(a-1 , b)個(gè)

24、頂點(diǎn)的完全圖中有一個(gè)紅Ka-1 ?,有藍(lán)Kb,紅Ka或藍(lán)Kb,v與這a-1個(gè)點(diǎn)構(gòu)成紅Ka,,,,,,N,Y,Y,N,29,推論 r (a , b ) ≤ ( ),a + b-2 a-1,證: r ( a , b )≤ r ( a -1 , b )+ r ( a , b-1 ) ≤( )+( )

25、 =( ),a + b-2 a-1,a + b-3 a-2,a + b-3 a-1,30,定理 若 a ≥3,則 r ( a , a) > 2,a2,,證:Kn有 ( )條邊,對(duì)邊紅藍(lán)2著色有2 種方案.其中同色Ka的方案數(shù)不超過,n2,Ka的個(gè)數(shù),可紅可藍(lán),可任意著色邊數(shù),同色邊數(shù),,,,,,,31,這是一個(gè)上界.Kn中含Ka的

26、方案被重復(fù)計(jì)數(shù)。 若取n足夠小,便得,則必有Kn的一個(gè)2著色方案中無(wú)同色Ka,有r ( a ,a)定義可知,r (a , a)>n,所以r (a , a) > 2,a2,,32,總 結(jié),本次課我們學(xué)習(xí)了 Ramsey問題的基本原理和部分完全圖的多色涂色問題。由于Ramsey問題是鴿巢原理的推廣,我們的重點(diǎn)放在鴿巢原理的兩種形式上。,33,本次授課到此結(jié)束,作業(yè)如下:P26 15,

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝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ù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 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)論