組合數(shù)學3

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

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

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

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

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

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

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

8、紅色邊少于3條，即至多有2條，這時從v1引出的藍色邊至少會有6條,不妨設為(v1, v2), (v1, v3), …, (v1, v7) 。,10,再看 v1, v2, v3, v4, v5, v6所成完全圖K6，由定理1， 其中若有紅色三角形，則結論已真；若K6中有藍色三角形，則其3個頂點連同v1即構成一藍色完全四邊形，結論亦真。  由（1）及（2）， 定理得證。  注意：當n

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

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

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

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

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

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

15、 r(m, n) = r( n, m),18,例：在K4中，我們用紅,藍兩種顏色涂色。要求 要么其中一種顏色只涂一條邊，例如用紅色涂一條邊，正好是紅K2，要么另一種顏色涂所有的邊，正好是藍K4 ；,,,,,,,v3,v2,v4,v1,,,,,,,v3,v2,v4,v1,19,關于平凡Ramsey數(shù)r(m, n)的一些已知結論可列 表如下： 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或藍K4r(4,5)=r(5,4)=25;用兩種顏色涂K25 能得到K4或K5 43≤ r(5, 5) ≤55;,21,Ramsey定理還可以推廣到任意多種顏色的情 況，如果n1,n2,n3是大于2的三個整數(shù)，則存在一個整數(shù)p使得:

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

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

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

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

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

23、)≤ r ( a －1 , b )＋ r ( a , b－1 )成立 證：對r ( a －1 , b )＋ r ( a , b－1 ) 個頂點的完全圖紅藍２著色．任取其中一點 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)個

24、頂點的完全圖中有一個紅Ka－1 ?,有藍Kb,紅Ka或藍Kb,v與這a－1個點構成紅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有 ( )條邊，對邊紅藍２著色有2 種方案．其中同色Ka的方案數(shù)不超過,n2,Ka的個數(shù),可紅可藍,可任意著色邊數(shù),同色邊數(shù),,,,,,,31,這是一個上界．Kn中含Ka的

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