如果G没有大的团.ppt

《如果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使用归纳法。只需证明[定理]对于任意正整数r2,s2,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).