论文部分内容阅读
人们对组合结构的兴趣或偏爱可以追溯到人类文明的起源。在最近60多年里,从1946年第一台现代电子计算机出现到它的发展、应用和普及;从传统电话、电报的发明到现代计算机网络、移动通讯的进入日常生活和工作;以及在其发展过程所形成的象现代信息论、通信理论、理论计算机科学等学科或领域都与组合数学及其思想方法有着广泛深刻的联系或烙印。组合数学已经成为是现代科学技术不可缺少的重要的理论基础,从而受到前所未有的重视,是现代数学中发展最快的部门并保持强劲的发展势头。
现代组合数学是以研究各种离散结构及其空间形式和数量关系的知识体系或学科。组合数学大体上可分为两部分:一部分是组合基础理论,另一部分是组合算法理论。组合数学除了研究来自其自身的问题外,还吸收来自计算机编码理论、区组设计、数据结构、通信理论、信息论、密码学、生物学、信息安全等众多领域或方面的实践与理论问题。特别地,组合数学作为计算机程序设计的理论基础,在高层次或高智能化程度的软件产品设计、开发中组合数学的思想和算法是极为重要的。
Ramsey理论不仅作为组合数学的最重要的组成部分之一,也是计算机科学的基础。因此,它对于计算机科学理论与实践都有着重要的意义,如在噪声信道通讯的最大不混淆字母表的计算和。Bell信号系统的设计中提供了理论支持,又如,在信息检索,算法复杂度分析和数据无关度的区别等问题中得到了初步应用。
但是,当前Ramsey理论的研究难点在于Ramsey数值的估算涉及到图的最大团和独立数问题,而图的最大团问题是一个NP完全问题,所以Ramsey数的值的确定非常困难,因而,严重制约着Ramsey理论深入广泛的应用。
本论文首先对Ramsey理论的研究背景、意义以及国内外发展趋势进行了简要的分析和综述;其次,介绍了Ramsey理论和Ramsey图的基础理论,提出了一些新的证明思路,从而得到了Ramsey图一些重要临界性质;接下来阐述了我们建立的约束共存理论(简称为RC理论)以及基于这个理论下有关Ramsey数的算法研究。
RC理论是,经过作者和导师以及李争武、段光文和陈菊等同学反复研究、探索的基础上,由作者的导师王瑞首先严格阐述了约束共存性这个概念以及约束共存状态的势和容量的思想,并精心规划了整个研究路线和方案,在几个基础性定理的证明以及整个理论的建立中都起着决定作用。本文作者自始至终投入到这个理论的产生、辨析和论证的过程里,并为这一新理论体系的提出和建立做出了努力。
根据约束共存性这个极赋哲理的思想和理念,揭示了Ramsey现象的本质,从而得到了有关Ramsey数的重要不等式R(p,q)>R(p-1,q+1)(3≤p≤q)及其推广,它曾经是长期困扰人们的一大难题。利用这些不等式和已有数据,大面积更新已有的上下界,同时,填补了一些Ramsey数上下界空白。在RC理论的框架下,进一步研究了Ramsey数的算法及其计算复杂性问题。提出了极大拆分算[51],大幅度降低了时间复杂性。最后,对全文所做的主要工作进行总结,并对更进一步研究做了展望。