轮图、星图及圈集的Ramsey数研究

发布时间：2018-06-27 19:21

  本文选题：Ramsey数 + 星-临界Ramsey数　； 参考：《北京交通大学》2016年博士论文

【摘要】：Ramsey理论是组合数学的一个重要分支,它广泛应用于计算机科学、信息论以及决策学等领域。在Ramsey理论研究中,一个与图论交叉的重要分支是求解图的Ramsey数,它在逻辑分析、并行计算和计算几何等计算机科学领域都有重要作用。本文利用计算机构造与数学证明相结合的方法,对与圈相关的星-临界Ramsey数、四边形对轮图(或星图)以及圈集对完全图的Ramsey数进行了研究。星-临界Ramsey数r*(C4,Cn)。星-临界Ramsey数由Hook和lsaak于2011年提出,并给出了r*(C4,C3)的准确值。本文首先利用图的Hamilton性质证明了所有(C4.Cn；n)-图G的结构；然后在图G的基础上增加一个新的顶点v，通过讨论顶点v与G的n个顶点之间的添边情形,并结合三类特殊图的Hamilton-connected特性详细分析了添加的最大边数,最终证明了当n≥4时,r*(C4,G)=5。四边形对轮图的Ramsey数R(C4,Wm)。Tse用计算机算法确定了7≤m≤13时R(C4,Wm)的准确值。Dybizbanski和Dzido确定了14≤m≤17时R(C4,Wm)的值,并给出了R(C4,Wm)的上界。本文首先基于(k，5)-笼(3≤k≤7)构造了不含C4且满足最小度要求的图,给出了R(C4,Wm)的下界；然后运用星-临界Ramsey的研究成果证明了任意图G是(C4,Wm;n)-图的充分必要条件,并利用不含C4的极图的相关研究成果证明了一些(C4,Wm;n+1)-图是不存在的,从而改进了相关R(C4,Wm)的上界,最终求解出18≤m≤44中R(C4,Wm)的9个准确值。四边形对星图(或轮图)的Ramsey数。Parsons给出了四边形对星图的Ramsey数R(C4,K1,m)的上界,并证明了当q为任意素数幂时,R(C4,K1,q2)=q2+q+1和R(C4,K1,q2+1)=q2+q+2。本文通过研究基于射影平面的极性图的结构特性,构造性的给出了R(C4,K1,q2-2)的下界,并结合Parsons给出的上界,最终证明了R(C4,K1,q2-2)=q2+q-1。利用该构造方法,还给出了当q为任意素数幂时,R((C4,Wq2+2)和R(C4,Wq2-1)的下界。通过详细分析q2++2个顶点不包含C4图的特性,改进了R(C4,Wq2+2)的上界：再结合前人给出的R(C4,Wq2-1)的上界,最终证明了R(C4,Wq2+2)=q2+q+2和R(C4,Wq2-1)=q2+q-1。圈集对完全图的Ramsey数R(Csm,Km)。Erdos和Faudree等人证明了：当n≥2m-1时,R(C≤n,Km)=2m-1;当mn2m-1时,R(C≤n,Km)=2m。本文研究了n≤m≤n+2时的R(C≤n,Km)。首先利用平面图的特性证明了极图集合EX(2n;C≤n)中图的结构；然后通过分析EX(2n;C≤n)中图的独立数证明了：当n为奇数时,R(S≤n,Kn)=2n;当n为偶数时R(C≤n,Kn)=2n+1。利用上述结论证明了Ramsey数R(Csn,Kn+1)的上界,并结合构造的(C≤n,Kn+1;2n+2)-图证明了当奇数n≥4和偶数n之16时,R(C≤n,Kn+1)=2n+3。另外,当n为奇数时,通过构造(C≤n,Kn+2;2n+4)-图给出了R(C≤n,Kn+2)的下界,证明了任意的(C≤n,Kn+1;2n+2)-图的结构,并利用反证法给出了R(C≤n,Kn+2)的上界,最终确定了当奇数n≥25时R(C≤n,Kn+2)=2n+5。求解Ramsey数R(C≤n,Km)的多核并行算法研究。本文研究了求解Ramsey数R(C≤n,Km)的串行算法,对其中的可并行化部分进行了系统分析,设计了的求解Ramsey数R(C≤n,Km)的并行算法,并在Phoenix++平台上对其进行了实现。同时采用数据预处理和合理分割数据集等措施提高了并行算法的执行效率。优化试验结果表明,并行算法在四核下的加速比和执行效率分别达到了3.70和92.50%。最后,利用该并行算法确定了当4≤n≤12时,R(C≤n,Kn+1和R(C≤n,Kn+2)的准确值。
[Abstract]:It is an important branch of combinatorial mathematics , which is widely used in the fields of computer science , information theory and decision - making . In this paper , the Hamiltonian properties of graphs are first used to prove all ( C4.Cn ) .
n ) - the structure of FIG . G ;
Then , a new vertex v is added on the basis of graph G . By discussing the boundary between vertices v and n vertices of G , the maximum number of edges added is analyzed in detail by Hamilton - connected features of three special graphs . Finally , it is proved that when n 鈮，

本文编号：2075017