轮图和圈集的拉姆塞数及相关算法研究

Over the years Ramsey theory found its way into several areas of mathematics, computer science, finance and economics. It has applications in parallel programming, approximation algorithms, game theory and theoretical computer science.. In this project, we will focus on graph Ramsey numbers R(H1, H2, ..., Hr), where r>=2 and H1 are wheels Wn or cycle-sets {C3, C4, ..., Cm}. We are planning to study the structures of Ramsey graphs related to these forbidden graphs, and the new algorithms specific for Ramsey theory computations will be designed according to the characteristics of these graphs. For these multi-color cases, novel and well-tuned implementations of algorithms for detection and elimination of isomorphic edge-colored graphs will be needed. By this algorithm, we will use the way of filling edge-colored subgraph to obtain bounds or exact values of the multi-color Ramsey numbers for these graphs.. The goal of the research described in this proposal is to two-fold: To pursue further the state of knowledge on Ramsey numbers for wheels and cycle-sets, and to enhance known and develop new abstract methods and computational techniques to decide if Ramsey arrowing holds in a general or particular situation. The research will not only lay a theoretical foundation for applications of these graphs to network designs, but also provide references for solving other NP-hard problems.

拉姆塞理论广泛应用于数学、计算机科学以及经济金融等领域，它在并行编程、近似算法、博弈论以及理论计算机科学中有很多应用。. 本项目着重研究广义拉姆塞数R(H1, H2, ..., Hr)，其中r>=2，H1为轮图Wn或圈集{C3, C4, ..., Cm}。(1) 研究与这两类图相关的拉姆塞图的结构特征；(2) 根据这两类图的特点设计出较好的计算拉姆塞数及其下界的算法，对他们的拉姆塞数进行计算；(3) 设计带权图的同构判定算法，用于边着多种颜色图的同构判定；(4) 利用多色子图填充法对与这些图类相关的多色拉姆塞数进行研究，给出他们的准确值或更好的界。. 本项目的目标是找到轮图和圈集的拉姆塞数变化规律，并探索拉姆塞数研究的新方法和新技术。项目的研究将为这些图类在网络设计中的应用奠定更加坚实的理论基础，并为解决其他NP困难问题提供借鉴。

拉姆塞理论在信息论、计算机科学以及经济金融等很多领域都有应用，但确定拉姆塞数是非常困难的。本项目采用计算机构造与数学证明相结合的方法对圈集和轮图的拉姆塞数及极图问题进行了研究。首先研究了圈集对完全图的拉姆塞数，给出了极图集合EX(2n; C≤n)中图的结构，从而确定了R(C≤n, Kn)和R(C≤n, Kn+1)的准确值；并给出了当n为奇数且n ≥ 25时R(C≤n, Kn+2)的值。然后，研究了完全图的哈密尔顿圈分解，给出了完全图的新的分解方式。对于奇数k，证明了Rk(C≤k+1)；对于偶数k，则给出了R4(C≤5) = 12，R6(C≤7) = 16和Rk(C≤k+1) = 2k + 3，其中8 ≤ k ≤ 12。第三，研究了围长为9的极图，通过分析顶点数n = 13, 16, 18, 22 和26时EX(n; 8)中极图的特点，证明了当25 ≤ n ≤ 30时ex(n; 8)的准确值；还构造了三个特殊的图，并基于他们改进了31 ≤ n ≤ 57时ex(n; 8)的下界值。研究了不包含圈集的极图构造算法，设计了一种基于量子进化的构造给定围长图的极图构造算法，利用该算法构造出顶点数为n (31 ≤ n ≤ 89)围长为11的图，从而给出了相应的ex(n;11)的下界。第四，研究了六边形对星图、六边形对轮图的拉姆塞数，给出了当5 ≤ n ≤ 28时R(C6, Sn)的准确值或上下界，给出了当4 ≤ n ≤ 26时R(C6, Wn)的准确值或上下界。最后，对图论和复杂网络理论在生物信息处理中的应用进行了研究，在关键蛋白质识别、复合物检测以及疾病与RNA的关联关系预测等方面取得了一系列研究成果。