欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
拉姆齐定理揭示了无序中必然出现有序的辩证统一。
拉姆齐
Frank P. Ramsey弗兰克·拉姆齐，1903~1930，英国哲学家、数学家和经济学家。
是的，你没看错，拉姆齐生年仅到26岁便英年早逝。
拉姆齐在数学和逻辑方面的一个重要贡献就是1928年他提出的一个组合数学理论，即后来以他的名字命名的拉姆齐定理（拉姆齐理论）。
拉姆齐定理RamseyTheory
这是一个组合数学中的问题，拉姆齐定理，也称之为拉姆齐二染色定理。它的直观描述是：
在超过6人的群体中，必然有3个人互相都认识或者有3个人互相都不认识。
换个说法：
在平面上超过6个点组成的群体中，必然有3个点互相连接成为三角形或者3个点互不相连。
再换个说法：
在一个完整的6阶图中，即6个点且每个点都和其他所有点进行连线，如果连线有红蓝两种，那么必然有一个红色三角形或者蓝色三角形。
或者说：
使得n个人中至少有k个人互相认识或u个人互相不认识，即R(k,u)=n。如果k=3，u=3，那么n最小值是6。
拉姆齐定理的证明
- 任意取6个点中的一个点P，对于一个完整图，它应该和其他5点相连。相连有两种可能，即认识或者不认识，认识标红色，不认识标蓝色。那么5条连线中至少有3条颜色是一样的，我么假设是3条红色认识。但这时并没有形成三角形，也不满足3个点互相都认识或都不认识。
- 我们把P点三条红线连接到的3个点互相连接，假设其中有一条是红色线互相认识，那么就会和P点的两条连线组成红色三角形，如图所示。
- 如果P点红线连接的3个点互相之间都是蓝色线，那么这三个点就形成了3个点互相不认识的情况，所以拉姆齐定理也成立。
- 思考一下，为什么五个点不行呢？
更多拉姆齐数
如图咋知道R(3,3)=6,R(4,4)=18...
友谊定理Friendship Theorem
友谊定理是指：在一群人数不少于三的人群中，若任意两人都刚好只有一个共同认识的人，这群人中总有一人是所有人都认识的。
在图论的角度来说，一幅图，若每个顶点都跟另一个顶点刚好只有一个共同相邻的顶点，这幅图中有一个顶点和其他顶点都相邻。
如图，友谊定理的图表示也称为友谊图，或者风车图，或n-fan图，最左侧的蝴蝶结装造型也称为蝴蝶图。
推论
拉姆齐定理还有几个推论，例如：范德瓦尔登定理、Hales-Jewett定理、舒尔定理、Rado定理等。
欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
每个人的智能新时代
如果您发现文章错误，请不吝留言指正；
如果您觉得有用，请点喜欢；
如果您觉得很有用，欢迎转载~
END
网友评论