【摘 要】
:
Ramsey理论是组合数学与图论的主要研究内容之一。Ramsey数的确定是Ramsey理论中的一个重要研究方向,该问题不仅在数学的发展中有着重要的理论意义,而且在计算机科学、通信、管
论文部分内容阅读
Ramsey理论是组合数学与图论的主要研究内容之一。Ramsey数的确定是Ramsey理论中的一个重要研究方向,该问题不仅在数学的发展中有着重要的理论意义,而且在计算机科学、通信、管理决策等许多领域中也有着实际的应用。然而,Ramsey数的确定是一个NP困难问题,至今人们只计算出了为数很少的几个Ramsey数的精确值。 对R个顶点的完全图KR的每一条边着由0到r-1中的一种颜色,记其中的着第i种颜色的边组成的子图为Gi(0≤i≤r-1);如果存在一种着色方法,使得对0≤i≤r-1都有Gi不包含图H,则称KR对禁止子图H可r-着色,否则称KR对禁止子图H不可r-着色。禁止子图H的r色Ramsey数Rr(H)是使得KR对H不可r-着色的最小正整数R。 本文讨论禁止子图H为圈的情况。 Ronald L.Graham,Burce L.Rothschild与Joel H.Spencer, (Ramsey Theory, SecondEdition,JOHN WILEY & SONS,1990)证明了: 当禁止子图H为奇圈C2m+1时,2rm<Rr(C2m+1)<2(r+2)!m; 当禁止子图H为偶圈G2m时,Rr(C2m)>(r-1)(m-1)。 本文利用因子分解的理论,给出并证明了Ramsey数Rr(C2m)的一个更优的下界: Rr(C2m)>Max{(r+1)m-2+(rmod2),2(r-1)(m-1)+1}。当r=3时,本文进一步结合构造性证明的方法得出R3(C8)=16;并猜想:当m≥3时,R3(C2m)=4m。
其他文献
随着航天技术的发展,航天电子设备的设计与研制所需要的成本不断提高,例如研发周期长,可靠性要求高等。因此,需要对各种航天产品进行各方面严格的测试。使用地面测试系统对航
课题基于移动代理对异构计算的负载平衡问题做了一些研究.首先对移动代理的特点、优势及形式化作了阐述,与其它模型作了比较,并对其性能进行了分析.随后的研究内容包括:利用
随着Internet网的快速发展,网络和信息技术的应用也越来越普及,从传统的小型的应用,到现在的大型的、关键业务的系统如电子商务、电子政务等,网络已经成为人类生活中不可或缺的重
本文从当前电力运营部门的实际需要出发,根据电力载波通信的工作原理,在技术上提出了一种高效可行的自动抄表方案,以解决电力运营部门普遍存在的“抄表难、收费难、管理难,运营成本高”等问题。 在查阅了大量的文献资料和广泛实地调研的基础上,本文对低压电力载波自动抄表系统的工作原理和通信协议进行了详细论述,并应用改进的Musa执行时间模型对低压电力载波自动抄表系统的软件可靠性进行了分析,从而使整套方案具
工作流管理技术是近几年来被业界广泛采用并迅速发展的一个技术,通过采用计算机技术,使业务流程部分或全部地自动化,使人以及各种应用工具相互之间协调工作,以完成某项工作.
伴随全球信息技术的迅猛发展,整个广播电视行业正在经历一场数字化浪潮的洗礼.作为电视节目的源头,电视节目制作播出系统在这场数字化浪潮中受到了巨大的影响.这种影响不仅体
图论是应用数学理论的重要分支.图论的广泛应用,促进了它自身的发展.尤其是近几十年来,随着计算机技术的出现和进步,图论理论有了飞速的发展并取得了惊人的成绩.该文所研究的
如何基于现有网络技术和各种新技术快速推出吸引消费者的电信业务素来都是电信企业领导者思考得最多的一个问题.传统的电信业务系统需求分析设计方式是先采用自然语言描述用
大型高海拔宇宙线观测站(Large High-Altitude Air Shower Observatory,LHAASO)计划的核心科学目标是探索高能宇宙线起源、宇宙线相关演化以及高能天体运动,为开展大气、气象
复合材料三维整体异型编织技术是二十世纪八十年代发展起来的高新纺织技术,它具有异型件一次编织成型、结构不分层、整体性能好和设计灵活等特点,因而这种复合材料倍受关注。然