您现在的位置是:首页 > 理科知识查询 > 数理化学

拉姆赛定理的

编辑:chaxungu时间:2022-09-28 08:31:43分类:数理化学

所谓的拉姆赛数(ramseynumber),用图论的语言有两种描述:

对于所有的n顶图,包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数n就称为一个拉姆赛数,记作r(k,l);
在着色理论中是这样描述的:对于<math>k_n</math>的任意一个2边着色<math>(e_1,e_2)</math>,使得<math>k_n[e_1]</math>中含有子图<math>k_k</math>,<math>k_n[e_1]</math>含有子图<math>k_l</math>,则称满足这个条件的最小的n为一个拉姆赛数。(注意:<math>k_i</math>按照图论的记法表示i阶完全图)
而按照通俗的话说就是要找这样一个最小的数n,使得n个人中有k个人相识或l个人不相识。

ramsey已经证明,对与给定的自然数k及l,r(k,l)是唯一确定的。