正文描述:《如果G没有大的团.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、RamseyTheorem如果G没有大的团,是否有大的独立集?Ramsey证明:对于任意正整数r,s,存在一个最小整数R(r,s)使得任意具有R(r,s)个结点的图或者有一个r个结点的团或者有s个结点的独立集。或者说:对于任意有R(r.s)个结点的完全图,用红、蓝两种颜色给边着色,必然存在一个红色的Kr或者一个蓝色的Ks例如,R(1,s)=R(r,1)=1,R(2,s)=s,R(r,2)=rR(3,3)=6Ramsey定理Ramsey数111111111234567896914182328361825s:1234
2、56789r1234CurrentknownRamseynumbersRamsey定理证明对于r+s使用归纳法。只需证明[定理]对于任意正整数r2,s2,R(r,s)R(r-1,s)+R(r,s-1).如果R(r-1,s)和R(r,s-1)均是偶数,则不等号成立。[证明]设G是一个具有R(r,s-1)+R(r-1,s)个结点的图,v是一个结点.将其他结点分为两组:S(与v不相邻的结点)和T(与v相邻的结点)。则有R(r,s-1)+R(r-1,s)=
3、S
4、+
5、T
6、+1根据抽屉原则,
7、S
8、R(r,s-1)或者
9、
10、T
11、R(r-1,s),即分两种情况(1)v至少与R(r,s-1)个结点的集合S不邻接,或者(2)v至少与R(r-1,s)个结点的集合T邻接;否则,G的结点数
12、理成立.当R(r,s-1)和R(r-1,s)均为偶数时,一个具有R(r,s-1)+R(r-1,s)-1(奇数)个结点的图必有一个偶数度结点v.以上两种情况仍然成立,因为v不可能正好与R(r-1,s)-1个结点相邻.故有R(r,s)<=R(r,s-1)+R(r-1,s)-1.例如,R(3,3)R(2,3)+R(3,2)=6R(3,3)>5R(3,3)>5R(3,4)8R(3,4)>8(r,s)Ramsey图:具有R(r,s)-1个结点,不存在r-图,不存在s独立集
13、Ramsey定理推广R(3,3,3)=17,在17个(以上)的完全图中,用三种颜色给所有的边着色,则必存在同色的K3可以推广到任意中颜色的情况:R(r1,r2,…,rk).
显示全部收起