組合數(shù)學(xué)3

1、1,中國(guó)余數(shù)定理是說(shuō)明： 一個(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問(wèn)題可以看成是鴿巢原理的推廣下面舉例說(shuō)明Ramsey問(wèn)題。例1　6 個(gè)人中至少存在３人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)。證:這個(gè)問(wèn)題與K6的邊２著色存在同色三角形等價(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條邊分配成2種顏色，至少有：[(5-1)/2]+1=３條邊同色?，F(xiàn)將證明過(guò)程用判斷樹表示如下：,,,,,,,,,,,,,,,,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,定理說(shuō)明：六點(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í)。上述問(wèn)題，可用圖論的方法予以解決。 即將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)２兩種著色，必有紅色三角 形或藍(lán)色K4。同理可證 K9的紅、藍(lán)２著色，必有藍(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 將上述的問(wèn)題一般化：給定一對(duì)正整數(shù)m, n,存在一個(gè)最小的正整數(shù)p ,對(duì)p個(gè)頂點(diǎn)的完全圖的邊任意紅、藍(lán)２著色，存在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就是說(shuō)，如果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條邊染為紅色?？疾靨1, 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é)論也可以用判斷樹來(lái)證：證:設(shè)三色為 r ,b ,g．則對(duì)K17的任一頂點(diǎn)v 有　dr(v) + db(v) + dg(v) = 16；因［16/3］+1 =6 ,故任一頂點(diǎn)與其他頂點(diǎn)的連線中，至少有６條同色．

21、不妨設(shè)dr(v1)≥6, (v1v2) ,(v1v3), …,(v1v7) 都是紅邊。從而可得如下判斷樹。,25,K6(v2···v7)中無(wú)紅邊 ?,K6(v2···v7)中有紅邊,K6(v2···v7)中藍(lán)、綠２著色,有藍(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 ≥２時(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)２著色．任取其中一點(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 ≥３，則 r ( a , a) > 2,a2,,證：Kn有 ( )條邊，對(duì)邊紅藍(lán)２著色有2 種方案．其中同色Ka的方案數(shù)不超過(guò),n2,Ka的個(gè)數(shù),可紅可藍(lán),可任意著色邊數(shù),同色邊數(shù),,,,,,,31,這是一個(gè)上界．Kn中含Ka的

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