《鸽巢原理》PPT课件

第二章 鸽巢原理简单形式之一n如果有许多鸽子飞进不足够多的鸽巢内，那么如果有许多鸽子飞进不足够多的鸽巢内，那么至少一个鸽巢内被两个或两个以上的鸽子占据至少一个鸽巢内被两个或两个以上的鸽子占据n鸽巢原理简单形式之一：定理2.1.1 如果如果n+1件物体被放件物体被放入入n个盒子，则至少有一个个盒子，则至少有一个盒子含有两件或更多物体盒子含有两件或更多物体简单应用n在13个人中必有两个人是同一个月份出生n设有n对夫妇，为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人？n+1简单形式之二、三n如果将n个物体放入n个盒子，并且没有一个盒子为空，那么每个盒子恰好包含一个物体n如果将n个物体放入n个盒子，并且没有一个盒子中放入多于一个的物体，那么每个盒子恰好包含一个物体鸽巢原理的抽象描述鸽巢原理的抽象描述令X和Y为两个有限集合，并有函数f:XYn如果|X|Y|，则f就不是一对一的；n如果|X|Y|，且f是映上的，则f就是一对一的；n如果|X|Y|，且f是一对一的，则f就是映上的复杂应用n给定m个整数a1,a2,am，则存在整数k和l，满足0k n-1nr(m,2)=?r(m,2)=mnr(m,n)=r(n,m)已探明的Ramsey数或它的界Ramsey定理的更一般形式n把两种颜色，推广到n种颜色：对m12，m22，mk2这k个都是整数，存在p，使得KpKm1,Km2,Kmk成立即：存在一个整数p，如果Kp的每条边都涂为c1,ck等k种颜色之一，那么或者存在一个颜色为c1的Km1，或者,或者存在一个颜色为ck的Kmk r(3,3,3)=17Ramsey定理的更更一般形式n给定整数t 2，对m1 t，m2 t，mk t这k个都是整数，存在p，使得KpKtm1,Ktm2,Ktmk成立。其中，Ktm表示m个元素的集的t个元素的子集的集合 即：存在p个元素的集，如果将集合的每一个t子集涂为c1,ck等k种颜色中的一种，那么或者存在m1个元素，这些元素的t子集都被涂为c1色，或者,或者存在mk个元素，这些元素的t子集都被涂为ck色nRamsey数：rt(m1,mk)命题推广n存在一个集合S，如果将集合的每一个t子集分为c1,ck等k类中的一种，那么只要|S|rt(m1,mk)，就满足：或者存在m1个元素，这些元素的t子集都是c1类，或者,或者存在mk个元素，这些元素的t子集都是ck类.Ramsey定理是鸽巢原理的推广n当t=1，即：存在p个元素的集，如果将集合的每一个元素边涂为c1,ck等k种颜色中的一种，那么或者存在m1个元素，这些元素的都被涂为c1色，或者,或者存在mk个元素，这些元素都被涂为ck色.nr1(m1,mk)=?r1(m1,mk)=m1+m2+mk-k+1Ramsey定理的意义n不可能存在完全无序的系统 在某种条件下，无论对一个大系统（结构）如何进行分割，总是能够得到人们预期想要得到的子系统（结构）意义n这里的系统即由相互关联的事物所组成，要研究这种系统可以通过很多种方式进行探讨，但是“图”是表达这种系统的最佳工具，因为图论正是讨论“事物”及其“关系”的一个数学工具。所以图论理所当然地成为研究Ramsey理论的一个最重要的表达工具。Ramsey定理的应用应用应用应用nr4(5,m)，