如果G没有大的团.ppt

ID:52540402

大小:171.00 KB

页数:8页

时间:2020-04-09

如果G没有大的团.ppt_第1页
如果G没有大的团.ppt_第2页
如果G没有大的团.ppt_第3页
如果G没有大的团.ppt_第4页
如果G没有大的团.ppt_第5页
资源描述:

《如果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).

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《如果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).

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭