3色Ramsey数R(C<,m<,1>>,C<,m<,2>>,C<,m<,3>>)

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:yidao
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Ramsey理论是图论的重要研究内容之一,而3色Ramsey数理论是其中一个重要的理论分支,对于3色Ramsey数的确定也是一个重要的研究方向,属于NP困难问题。Ramsey问题在数学的发展中有着重要的理论意义,然而,至今为止,人们仅计算出一部分3色Ramsey数的值。 用r种颜色对图G中的所有边进行着色,记着第i色的边所构成的子图为Gi。如果存在一种着色方法使得对于所有的i(1≤i≤r)都满足禁止子图Hi(?)Gi,则称图G对于(H1,H2,…,Hr)可r着色。Ramsey数R(H1,H2,…,Hr)是使得完全图Kn对于(H1,H2,…,Hr)不可r着色的最小正整数。本文所研究的就是当r=3且Hi≌Cm(禁止子图同构于圈)时即3色Ramsey数R(Cm1,Cm2,Cm3)的相关问题。 Erd(?)s等人在其研究成果中给出了在m足够大的情况下Ramsey数R(Cm,C3,C3)=5m-4和R(Cm,C4,C4)=m+2的结论。 本文通过数学证明的方法得出了当m≥5时,R(Cm,C3,C3)=5m-4;在m1不是足够大的情况下,运用临界图概念和有效的分枝限界条件,通过计算机辅助得出当7≥m1>m2≥m3时R(Cm1,Cm2,Cm3)的所有值,并给出了相应的猜想;为计算R(Cm,C4,C4)的值,文中定义了新的临界图概念,并得出结论即当11≤m≤19时R(Cm,C4,C4)=m+2,并在此基础上证明了当m>19,R(Cm,C4,C4)=m+2成立。
其他文献
IETF提出的IP主干网上核心技术之一的多协议标记交换MPLS[1]技术是一种典型的集成模型技术,它是综合了网络核心的交换技术和网络边缘的IP路由技术各自的优点而产生的,与传统
随着科学技术的发展,优化问题变得越来越复杂,上下级交互决策变得越来越普遍。对双层规划问题已经有了比较广泛的研究,近年来,双层多目标规划问题也逐渐引起了人们的关注。双层多
在当今信息时代,信息对处于激烈竞争中的企业的立足和发展至关重要。建设一个安全、可靠、开放、高效的信息网络和办公自动化系统能够有效提高企业的整体工作效率,增强企业的
随着计算机软件技术的不断发展,很多软件系统成为遗产资源,虽然它们在结构设计和界面设计等方面比较陈旧,但是它们里面包含的行为逻辑经过了多年的实践和检验,仍具有很高的应
当今,在信息化浪潮席卷全球的环境下,我国企业管理必须打破传统的模式,跟上时代的潮流,走企业管理信息化的道路。企业管理信息系统即企业MIS是企业信息化的重要内容。本文以宾馆M
随着网络的不断普及,IPv4网络暴露出地址空间严重缺乏及路由表膨胀等一系列自身无法解决的问题。IPv6是下一代互联网的核心,它所具有的巨大的地址空间、移动性、安全性等优点使
无线局域网(WLAN)技术是20世纪90年代计算机网络和无线通信技术相结合的产物,在现代实际的生活工作中有着广泛的应用,如高速计算机网络,家庭多媒体服务,医院的医疗数据、图像传输,以
高职教育是我国高等教育的重要组成部分,学分制教学管理模式是高职院校教学改革的必然趋势。在学分制教学模式下,选课活动是一切教学活动安排的基本依据,是产生学分制的基础,是实
合成孔径雷达(SAR)是一种以小孔径天线利用脉冲技术,合成孔径原理实现的具有高分辨率的新型雷达系统,较之原有的雷达系统,其功能得到质的变化。SAR可以对局域目标进行成像识别,
本文根据仿生学原理,模拟生物系统的免疫机理,设计了计算机系统安全模型GECISM(General Computer Immune System Model),该模型由不同的代理构成,各代理模拟不同的免疫细胞的