| Ramsey重数研究 |
| |
| 引用本文： | 邵泽辉,王子成,张凯.Ramsey重数研究[J].武汉大学学报(理学版),2009,55(6). |
| |
| 作者姓名： | 邵泽辉 王子成 张凯 |
| |
| 作者单位： | 1. 成都大学,信息科学与技术学院,四川,成都,610106;华中科技大学,控制科学与工程系,湖北,武汉,430074
2. 华中科技大学,控制科学与工程系,湖北,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金，国家高技术研究发展计划(863计划) |
| |
| 摘 要： | 对于图G_1,G_2,2色广义Ramsey数R(G_1,G_2)表示满足下列条件的最小正整数p:如果用2种颜色中的一种对K_p的每一条边染色,总有K_p的一个子图同构于G_i,它的边都染有第i种颜色,1≤i≤2.对K_(R(G))的所有可能的边2-着色中,含有单色子图G的最少的个数称为图G的重数.利用计算机计算了若干不小于5阶图的Ramsey重数精确值:M(C_6)=10,M(P_6)=300,M(P_7)=720;当计算量很大时,利用模拟退火算法得到了若干Ramsey重数的上界:M(B_4)≤51,M(K_(2,4))≤24,M(K_(3,3))≤150,M(K_(2,5))≤47,M(W_6)≤34,M(B_5)≤48.
|
| 关 键 词： | Ramsey数 Ramsey重数 边着色 |
Ramsey Multiplicities of Some Graphs |
| |
| SHAO Zehui,WANG Zicheng,ZHANG Kai.Ramsey Multiplicities of Some Graphs[J].JOurnal of Wuhan University:Natural Science Edition,2009,55(6). |
| |
| Authors: | SHAO Zehui WANG Zicheng ZHANG Kai |
| |
| Abstract: | For given graphs G_1 and G_2, the 2-color Ramsey number R(G_1 ,G_2) is defined to be the least positive integer p such that every 2-coloring of the edges of complete graph K_p contains a monochromatic copy of G_i colored with i, for some 1≤i≤2. We obtained some exact values by computer, M(C_6) =10,M(P_6) =300,M(P_7) =720. When the computation complexity is high for exact values, we computed some upper bounds of Ramsey multiplicities by simulated annealing method:M(B_4)≤51 ,M(K_(2,4))≤24,M(K_(3,3))≤150,M(K_(2,5))≤47,M(W_6)≤34,M(B_5)≤48. |
| |
| Keywords: | Ramsey number Ramsey multiplicity edge coloring |
| 本文献已被 万方数据 等数据库收录！ |
|
