论文部分内容阅读
Ramsey理论是组合数学中的一个重要分支,而图的Ramsey数是Ramsey理论的一个主要研究方向.Ramsey理论在数论、有限域、泛函分析、拓扑学、通信以及计算机信息检索等领域都有着广泛地应用,它们从不同的方面揭示了:任何一个足够大的结构中必定包含一个具有给定性质的子结构.确定Ramsey数是NP难题,到目前为止,只有很少的Ramsey数的精确值被确定.随着计算机技术的不断发展,计算机技术在Ramsey理论中的应用给图的Ramsey数研究注入了新的活力.本文将数学证明和计算机证明相结合,对路与圈的3色Ramsey数、Lovász- Ramsey数、多重图Ramsey数以及多重图Folkman数等相关问题进行了研究,主要研究内容如下:1.提出了一个求3色Ramsey数R （ Pm,Cn,Cl ）上界的算法,利用改进的模拟退火算法计算R （ Pm,Cn,Cl ）的下界;通过计算机构造证明和数学证明,得到了若干小的圈和路混合的R （ Pm,Cn,Cl ）的精确值.2.定义了Lovász-Ramsey数,讨论了Lovász-Ramsey数与经典Ramsey数之间的联系;把Ramsey数中已知的结论推广到Lovász-Ramsey数,通过算法计算和理论证明得到了若干小参数Lovász-Ramsey数的精确值.3.利用合成图方法和颜色集的染色理论给出了几个多重图Ramsey数的上下界公式;把随机图理论引入到多重图,改进了多重图Ramsey数的下界公式,并且给出了若干多重图Ramsey数的参数下界;最后利用归纳法证明了一个多重图Ramsey数的上界公式.4.定义了简单图的颜色集顶点Folkman数和多重图的边Folkam数;讨论了多重图的边Folkman数与简单图的边Folkman数以及简单图的顶点颜色集Folkman数与多重图的边Folkman数之间的联系;通过对图的染色分析证明了Fe（2） （3,3,3;4） = 11.