dzrr.net
当前位置:首页 >> rAmsEy定理 >>

rAmsEy定理

定理1R(a,b)=R(b,a), R(a,2)=a定理2对任意整数a,b>=2, R(a,b)存在。定理3对所有的整数a,bR(a,b)=2,若R(a,b-1)和R(a-1,b)是偶数,则R(a,b)=2,有R(a,b)

一对常数a和b,对应于一个整数r,使得r个人中或有a个人相互认识,或有b个人互不认识;或有a个人互不认识,或有b个人相互认识。这个数r的最小值用R(a,b)来表示,也就是R(a,b)个顶点的完全图。用红蓝两种颜色进行着色,无论何种情况必至少存在以下...

友谊定理的主要内容如下:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识的人,这群人中总有一人是所有人都认识的。 主要内容 从图论的角度来说,一幅图,若每个顶点都跟另一个顶点刚好只有一个共同相邻的顶点,这幅图中总有一个顶...

证明如下:首先,把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设:如果两个人认识,则设这两个人组成的线段为红色;如果两个人不认识,则设这两个人组成的线段为蓝色。由抽屉原理可知:这五条线段中至少有...

(1)对6个顶点的完全图的边用红、蓝二色任意着色,结果至少有两个同色的三角形。(2)证明10个人中若不是3个人互不认识,则必有4个人互相认识,同样,10个人中若不是3个人互相认识,则必有4个人互不认识。(3)18个人中至少有4个人或互相认识或...

其实就是广义抽屉原理,国内翻译为拉姆齐定理。 在组合数学上,拉姆齐(Ramsey)定理是要解决以下的问题:要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识。 这个定理以弗兰克·普伦普顿·拉姆齐命名,1930年他在论文On a Proble...

Ramsey(1903~1930)是英国数理逻辑学家,他把抽屉原理加以推广,得出广义抽屉原理,也称为Ramsey定理。 中文名 :广义抽屉原理,外文名 :Ramsey定理 ,别称 抽屉原理,表达式:任意六个人中至少三个人认识或不认识。

拉姆齐二染色定理,在组合数学上,拉姆齐(Ramsey)定理是要解决以下的问题:要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识。

Ramsey定理 http://wenku.baidu.com/view/0f23ab661ed9ad51f01df213.html 自己看吧。。。

所谓的拉姆赛数(Ramsey Number),用图论的语言有两种描述: 对于所有的N顶图,包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆赛数,记作r(k,l); 在着色理论中是这样描述的:对于K_n的任意一个2边着色(e_1,e_2),使得K...

网站首页 | 网站地图
All rights reserved Powered by www.dzrr.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com