aimisiyou 发表于 2021-6-20 07:51:27

拉姆齐数

拉姆齐数除了暴力枚举，还有啥办法求解？
有人说可以求出任意拉姆齐数，是假的吧？

mathe 发表于 2021-6-20 08:43:24

https://mathimages.swarthmore.edu/index.php/Ramsey_Number

mathe 发表于 2021-6-20 09:10:11

例子可以在 http://users.cecs.anu.edu.au/~bdm/data/ramsey.html 找到，比如其中Ramsey(3,6)中17 vertices的7个图应该可以轻松反驳Ramsey(3,6)=17的结论。只是里面图的格式后缀是.g6不知道是什么文件格式

mathe 发表于 2021-6-20 09:16:20

展开一个结果了:
Graph 1, order 17.
0 : 9 14 15 16;
1 : 7 11 13 16;
2 : 8 10 12 15;
3 : 6 8 13 15 16;
4 : 5 7 12 14 16;
5 : 4 9 10 11 13;
6 : 3 10 11 12 14;
7 : 1 4 9 10 15;
8 : 2 3 9 11 14;
9 : 0 5 7 8 12;
10 : 2 5 6 7 16;
11 : 1 5 6 8 15;
12 : 2 4 6 9 13;
13 : 1 3 5 12 14;
14 : 0 4 6 8 13;
15 : 0 2 3 7 11;
16 : 0 1 3 4 10;

这个图找不到三个点两两之间都有边相连，找不到六个点两两之间都没有边相连，所以R(3,6)>17
页: [1]
查看完整版本: 拉姆齐数