论文部分内容阅读
Ramsey理论是组合图论中重要的研究内容之一,它在逻辑学、电讯工程以及计算机科学等领域中均有广泛的应用.Ramsey理论开创于1930年英国数学家Frank Ramsey证明的Ramsey定理,该定理是组合数学的一个基本结果,它直观的表明了:每一个无序且充分大的结构总会包含一定大小的有序子结构.对于给定的图G1,G2,..…,Gk,k≥ 2,k-色Ramsey数R(G1,G2,...,Gk)是指最小的正整数p,使得对p阶完全图Kp进行任意的k-边着色,总是存在某个着i色的单色图Gi,其中i∈ {1,2,...,k}.如果一个k-边着色的完全图满足对任意的i ∈ {1,2,...,k}都不包含i-色的子图Gi,并且其阶为R(G1,G2,...,Gk)-1,我们就称该完全图是(G1,G2,...,Gk)-Ramsey 图.迄今为止,关于2-色Ramsey数的研究结果虽十分丰富,但能够确定精确值的图类较少.而3-色及3-色以上Ramsey数的研究结果相对较少,能够确定精确值的图类更是少之又少,主要集中在圈、路以及完全图等有限的规则图形.Ramsey数的确定属于NP-Hard问题,常见的确定Ramsey数的数学方法有概率方法、数学归纳以及代数方法等.本学位论文主要关注一些3-色Ramsey数,确定了若干个3-色Ramsey数R(C4,C4,K1,,n)并完全确定了 3-色 Ramsey 数R(C4,C4,Pn).在第一章节中,我们首先介绍了本文中所涉及的基本概念,然后简述了相关领域的研究现状,最后呈现了研究的主要结果.在第二章节中,我们使用计算机与数学证明相结合的方法证明了 3-色Ramsey数R(C4,C4,K1,n)=n+9,其中 n ∈ {7,8,9,10}.在第三章节中,我们在已有的3-色Ramsey数R(C4,C4,P5)和R(C4,C4,Cn)的准确值的基础上运用反证法完全确定了 3-色Ramsey数R(C4,C4,Pn)的值.