《鴿巢原理》ppt課件-全文預(yù)覽
【正文】 —— r(2,n) n1 ? r(m,2)=?? r(m,2)=m ? r(m,n) = r(n,m) 已探明的 Ramsey數(shù)或它的界 Ramsey定理的 更 一般形式 ? 把兩種顏色，推廣到 n種顏色 ： 對(duì) m1≥2， m2≥2， …… ， mk≥2這 k個(gè)都是整數(shù)，存在 p，使得 Kp?Km1, Km2, ……K mk成立 即： 存在一個(gè)整數(shù) p，如果 Kp的每條邊都涂為c1,…,c k等 k種顏色之一，那么或者 存在一個(gè)顏色為 c1的 Km1，或者 ,……, 或者 存在一個(gè)顏色為ck的 Kmk r(3,3,3) = 17 Ramsey定理的 更更 一般形式 ? 給定整數(shù) t ≥ 2，對(duì) m1 ≥ t， m2 ≥ t， …… ， mk ≥ t這 k個(gè)都是整數(shù)，存在 p，使得 Kp?Ktm1, Ktm2, ……K tmk成立。 v10)中有 藍(lán) K4？ K10( v1v2 , v6 }， dr(vi)表 示與 頂點(diǎn) vi 關(guān)聯(lián)的紅色邊的條數(shù)， db(vi)表 示與 vi 關(guān)聯(lián)的藍(lán)色邊的條數(shù)．在 K6 中，有 dr(vi)＋ db(vi)＝５，由鴿巢原理可知，至少 有３條邊同色． 現(xiàn)將證明過(guò)程用判斷樹表示如下 ： 證明 dr(v1)≥3? db(v1)≥3 設(shè) (v1v2) (v1v3) (v1v4)為紅邊 △ v2v3v4是紅△ ? △ v2v3v4是藍(lán)△ ? 設(shè) ( v2v3 )是紅邊 △ v1v2v3是藍(lán)△ △ v1v2v3是紅△ √ √ Y N N N Y Y 設(shè) (v1v2) (v1v3) (v1v4)為藍(lán)邊 設(shè) ( v2v3 )是藍(lán)邊 問(wèn)題 ? 在 5個(gè)人中，或者有 3個(gè)人，他們中的每?jī)蓚€(gè)人都互相認(rèn)識(shí)；或者有 3個(gè)人，他們中的每?jī)蓚€(gè)人都彼此不認(rèn)識(shí) K5→K 3， K3是否成立 ？？ n≥6，是否會(huì)有相似的結(jié)論？ 推論 ? K9 的邊 用 紅藍(lán)兩色任意著色，則必有 一個(gè) 紅 色K4或一個(gè)藍(lán)色 K3 ，或者，必有一個(gè)藍(lán)色 K4或一個(gè)紅色 K3 引理：存在一個(gè)頂點(diǎn) vi至少關(guān)聯(lián) 4條藍(lán)邊或者 6條紅邊 證明： 不妨設(shè) db(v1) ≥4，可得如下判斷樹證明結(jié)論 : 證明 db(v1)≥4? dr(v1)≥6 設(shè) (v1v2) (v1v3) (v1v4)(v1v5)是 4條藍(lán)邊 設(shè) (v1v2) 對(duì)否 ？ ? 一籃子水果有：蘋果、香蕉、橘子，已知籃子中每種水果的平均數(shù)目至少為 8個(gè)，那么
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1