平面Ramsey数PR(K4-e，K6)和PR(C4，K7)的研究

作     者：宋亚楠 

作者单位：大连理工大学 

学位级别：硕士

导师姓名：杨元生

授予年度：2007年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：Ramsey数 平面Ramsey数 圈 禁止子图 

摘      要：图的Ramsey数研究是Ramsey理论的一个重要研究方向。该问题不仅在数学的发展中有重要的理论价值，而且在信息论和理论计算机科学等许多领域中也有重要的应用。Ramsey数的确定是一个NP困难问题，用数学方法仅能求出极少数图的Ramsey数的准确值。计算机技术的应用给图的Ramsey数研究注入了新的活力。本文将计算机构造性证明与数学证明相结合，对图的平面Ramsey数问题进行了深入研究。 1969年，Walker首先提出了平面Ramsey数PR(H，H)的概念。Bielak和Gorgol证明了PR(C，K)=13和PR(C，K)=17，并给出PR(C，K)的一个下界。 本文在这些研究的基础上，发现用临界图策略算法在可容忍的时间内最多只能证明PR(K-e，K)=14和验证PR(C，K)=17。针对此算法这一不足，本文研制了计算平面Ramsey数PR(H，H)值的新算法CPG。该算法没有采用通常的临界图策略，而是针对平面Ramsey数中平面性这一限制，利用非平面图一定包含同胚于K或K的子图这一定理，通过增加顶点与边从小顶点构造出所有不含禁止子图H(H(?)K-e或H(?)C)的n个顶点的平面图，然后判定这些图中是否存在一个图G使得H(?)。若存在这样的图，则PR(H，H)≥n+1;否则，PR(H，H)≤n。该算法已在Intel P4 1.7G，内存500M的计算机上运行。实验表明，该算法可验证到PR(K-e，K)(l≤6)和PR(C，K)(l≤7)的值，并可证明PR(K-e，K)=17和PR(C，K)=20。该算法因不存在删边操作，运行速度也比临界图策略算法提高了6倍多。本文同时将欧拉公式和三连通平面图的平面嵌入唯一的性质应用到平面Ramsey数的证明中。用数学方法严格证明了PR(K-e，K)=17和PR(C，K)=20。而且给出当l≥3时PR(K-e，K)≥3l+[(l-1)／4]-2的简短证明。本文还给出如下两个猜想：PR(C，K)=3l+[(l-1)／5]-2(l≥3)和PR(K-e，K)=3l+[(l-1)／4]-2(l≥3)。