Ramsey理论中图的构造与计算

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:jxj860205
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Ramsey理论是组合数学中的一个重要分支,在通信、计算机信息检索和决策学等方面有一系列的具体应用,近年来在与其他数学分支的相互渗透中得到了迅猛的发展。Ramsey数,Ramsey重数和Folkman数是Ramsey理论的重要研究对象,目前只有很少的Ramsey数,Ramsey重数和Folkman数的精确值被确定,人们知道的上下界大多相距很远,进一步的工作,即使是给出较好的上下界,面对的都是非常巨大的计算量。本文对Ramsey理论中的若干问题作了相关的研究,讨论了经典Ramsey数、广义2色Ramsey数、路与圈的3色Ramsey数、Ramsey重数和Folkman数等有关问题,主要研究内容如下:(1)研究Ramsey图的性质有助于寻找新的Ramsey图,以改进Ramsey数的下界。本文研究了Ramsey图与准正则图之间的关系,提出了用构造准正则图的方法寻找新的Ramsey图,特别是(5,5)-图;验证了(5,5)Ramsey图中不存在强正则自补图;通过寻找满足一定条件的同构的子图,得到了三个经典Ramsey数R(6,8),R(7,9)和R(8,17)的新下界129,235和937。(2)确定小的R(Cm,Bn),R(Km,n,Kp,q)型Ramsey数以及R(Bm,Bn)的精确值是一个非常困难的问题,目前也都只得到了其中很少的精确值。本文通过计算得到了若干R(Cm,Bn)的值,计算得到R(B3,B4)=15,利用正则图得到了R(K2,5,K2,9),R(K2,6,K2,9),R(K2,7,K2,9)的新下界,从而确定了其精确值。(3)对于3色的广义Ramsey数,对3色圈,路以及圈和路混合形式的Ramsey数研究较多,目前只得到了若干小的圈和路混合形式的Ramsey数的精确值,以及R(P3,Ck,Ck),R(P3,P4,Ck),R(P3,P5,Ck)和R(P4,P4,Ck)的精确值。本文利用计算机和数学证明相结合,得到了一些新的路,以及圈和路混合形式的Ramsey数,以及若干R(P4,P5,Ck)和R(P4,P6,Ck)的精确值。(4)2002年,S.P.Radziszowski和Kung-Kuen Tse给出R(C4,K9)≤33,R(C4,K10)≤40。本文将R(C4,K9)和R(C4,K9)的上界分别改进为32和39,并得到了若干C4对完全图的多色Ramsey数的上下界。(5)图G的重数M(G)定义为:对KR(G,G)的所有可能的边2-着色中,含有单色子图G的最少的个数。直到2001年,人们才求出了了4阶的Ramsey重数的精确值,其中,M(K4)的精确值直到2001年才被解决。本文通过计算机算法,求得了17个5阶图的Ramsey重数精确值,通过模拟退火算法得到了5个5阶图的Ramsey重数的上界。(6)本文研究了一些Folkman图的性质和算法,通过计算得到了Fv(3,5;6),Fv(3,6;7),Fv(3,7;8)和Fv(3,8;9)的新上界,分别为16,18,22和23。并给出了Fv(3,k;k+1)类型的Folkman数的新上界公式;将Fv(4,4;5)新的上界由25改进到23,下界由16改进到17;证明了当k≥4时,Fv(k,k;k+1)≥4k-1;给出了Fe(3,4;5)的下界22。(7)引进了多重图的Ramsey数的概念,并对它进行了系统的研究,推广了许多关于经典Ramsey数的相应结果。
其他文献
公正,是公安执法的价值追求,是衡量执法优劣的标准。坚持执法公正,要正确理解公正的涵义,了解公正与正义、公平、平等之间的区别,把握好程序公正与实体公正的关系,落实自己不
池塘景观在流域的水文过程、生物地球化学循环扮演着重要的作用。研究水塘改变流域的产流过程、弄清水塘位置对于面源污染削减的影响机制,实现三峡库区面源污染削减,保证三峡
以核桃壳生物炭为原料,利用一步水热法合成锰铁氧体/生物炭复合材料(BMFC),采用SEM、XRD和FTIR对BMFC进行了表征,并研究了pH、吸附时间、起始浓度等对BMFC吸附Cd2+性能的影响,
图书馆作为一种社会认可度较高文化机构,其文化建设是其具有文化辐射力和感染力的关键。而在信息化社会环境下,图书馆的文化的建设和延续需要技术的支撑,才能保持长久旺盛的
施工企业的集团化发展,对企业绩效管理提出了挑战。EVA作为公司业绩度量指标,因其考虑所有资金成本,实施科学合理的奖金激励机制,改变了管理观念和管理者的决策行为。 The c
目的:观察不同吸烟时间大鼠支气管上皮细胞、肺泡巨噬细胞和肺组织中γ-谷氨酰半胱氨酸合成酶(γ-GCS)和转化生长因子β1(TGFβ1)mRNA及其蛋白的表达水平以及二者的相关性,探讨 T
旅游业是我国第三产业中的支柱型产业,在我国的经济产业升级过程中,旅游业扮演着重要的角色。在旅游过程中,旅游产品的品质与价值直接影响着旅游者的购买欲望,为了获得巨大的经济
近几年,随着硬件系统在技术上的不断突破,计算机技术的发展日新月异。如今的社会,人们对于计算机的计算能力以及对数据的处理能力的要求越来越高,而经典计算机在这两方面已经
众多歌剧作品中最激动人心的时刻是作品的悲剧情节,由于剧中人物命运无常,心情也是或忧伤或愤慨,但是结局大多比较悲惨。所以,人物的内心深处产生了较为强烈的情绪碰撞,在音
以陶瓷基复合材料(Ceramic Matrix Composite,CMC材料)为代表的纤维增韧复合材料由于其耐高温、高强度、低密度特点,在航空发动机高温部件中逐步得到工程实际应用。本文针对