圈的多色拉姆塞数及相关极图问题研究

项目名称： 圈的多色拉姆塞数及相关极图问题研究

项目编号： No.60973011

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 孙永奇

作者单位： 北京交通大学

项目金额： 29万元

中文摘要： 拉姆塞理论在很多领域都有应用，如信息论和计算机科学等。图的拉姆塞数研究是拉姆塞理论的一个主要研究方向，它对网络设计中通信设施数量的选择以及通讯频道Shannon容量的确定有重要意义。它是NP困难问题，研究它对解决一般NP困难问题有意义。 到目前为止，只有很有限的一些图簇的拉姆塞数得到了精确值，其成果主要集中在对两色拉姆塞数的研究。但实际应用中遇到的可能是多色拉姆塞数。本课题着重研究圈的多色拉姆塞数以及相关极图问题；研制出较好的计算圈的多色拉姆塞数的算法、计算圈的多色拉姆塞数下界的算法以及构造相关极图的算法。主要目标是探索出一条求解圈的多色拉姆塞数问题的有效途径，为圈的拉姆塞数的实际应用提供更坚实的理论基础，也为其它图簇多色拉姆塞数的求解提供借鉴。 　　在图的多色拉姆塞数研究领域，申请者已经取得了一些研究成果。本项目的研究，将有助于我们在该领域取得更大的突破。

中文关键词： 多色拉姆塞数；二部拉姆塞数；分布式计算；极图；圈

英文摘要：

英文关键词： Multicolor Ramsey Number；Bipartite Ramsey Number；Distributed Computing；Extremal Graph；Cycle