图论拉姆齐(Ramsey)理论

图论拉姆齐(Ramsey)理论拉姆齐理论 RamseyTheory 研究的是在足够大的结构中必然出现的模式

大家好,欢迎来到IT知识分享网。

图论拉姆齐(Ramsey)理论

  • 定义:拉姆齐理论也称为拉姆齐二染色定理,R(m,n)(其中m和n都是大于2的整数),表示晚会上每两个人是敌人或者是朋友,那么晚会上使得m个人两两都是朋友,或者n个人两两都是敌人所需要的最少人数。
  • 证明:
    R(3,3)=6

在六个人中随机选择一个人A,他与其他人有五个关系,分成两种,那么根据鸽巢原理必然有三个关系是一样的,用图来解释:至少有三条边是同一种颜色。(橘色代表朋友,绿色代表敌人。)在这里插入图片描述此时如果将CDE任意两两连成橘色,就得到了证明,所以我们将CDE两两连成绿色。在这里插入图片描述明显看到,CED形成了一个绿色的三角形,得到证明。
根据对称性可证明R(m,n)=R(n,m)。
R(5,5)由于算力的不足还不知道确切的值,知道是在在43到48之间(更新至2020年的数据)。

  • 最后
    如果一个集合足够大&#

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/157564.html

(0)
上一篇 2025-01-29 18:45
下一篇 2025-01-29 19:00

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信