图ramsey数及相关极图问题地研究

《图ramsey数及相关极图问题地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。学校可以为存在馆际合作关系的兄弟高校用户提供文献传递服务和交换服务。(保密的学位论文在解密后适用本授权说明)’学位论文作者签名：导师签名：扇，精、J签字日期：弘f毕年I1月皿日签字日期：加l午年ff月穆日万方数据学校代码：10004密级：公开北京交通大学博士学位论文图的Ramsey数

2、及相关极图问题的研究ResearchonRamseyNumbersandRelatedExtremalGraphs作者姓名：张锐导师姓名：孙永奇学位类别：工学学号：10112080职称：教授学位级别：博士学科专业：计算机科学与技术研究方向：算法设计与分析北京交通大学2014年11月万方数据致谢本论文的工作是在我的导师孙永奇教授的悉心指导下完成的，孙永奇教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响，是我学习的榜样。无论是在理论学习还是论文选题、资料查询、课题研究、论文写作等每一个阶段，孙永奇教授都悉心指导、严格要求。在此衷心感谢四年来孙永奇老师对我的关心和指

3、导。感谢我的研究生导师郝荣霞教授，她在我攻读硕士期间对我严格要求给我打下了良好的理论研究基础，并且在我准备毕业设计期间给于我很多帮助。感谢罗彻斯特理工学院的Radziszowski教授对于我论文写作和内容上的建议。在平时专业课的学习及科研中，王志海、瞿有利等老师对我进行了悉心的指导，并且对我的科研工作和论文都提出了许多的宝贵意见，在此对各位老师表示衷心感谢。武亚丽对于我的科研工作和论文都提出了许多的宝贵意见，为我论文写作、打开思路都有非常大的帮助，在此也对武亚丽表示衷心的感谢。在实验室工作及撰写论文期间，郑瑞君、张平等同学对我论文中的与算法有关的研究工作给予了热情帮助

4、和指导，在此向他们表达我的感激之情。另外感谢我的父母和工作单位，是他们的支持和鼓励才让我完成博士阶段紧张的学习生活，在我学习和工作进入低潮时，是他们让我走出低谷重拾信心。最后，感谢各位专家在百忙中审阅我的论文，并给出批评意见。感谢北京交通大学十年来对我的教育和培养，感谢北京交通大学计算机与信息技术学院诸多老师四年来的关心和教育。我在交大十年的生活中领悟了很多人生真谛，结识了许多天南海北的朋友，母校的这份恩情我将永远铭记。万方数据摘要图论是离散数学的一个重要分支，而Ramsey理论是图论研究中的一个重要方向，它已渗透到数学、计算机科学、信息论以及经济金融等领域。求解图的

5、Ramsey数是Ramsey理论研究中的一个很活跃的分支，它在逻辑分析、复杂结构、并行计算和计算几何等计算机科学领域都有重要作用，吸引了国内外许多学者进行研究。极图理论是图论中的一个重要组成部分，它是在Turfn极图问题的基础上发展起来的，主要研究顶点数一定且不包含某些子图的图的最大边数，即给定一个图集炒={H1，／-／2⋯．，风}，m缸数ex(n；Ic，)是顶点数为刀且不包含子图凰(1SiSm)的图的最大边数，EX(n；∽表示这些边数为ex(n；∽的图集。因为Turhn数是可着色方案中单色子图可以达到的最大边数，所以极图问题的研究可以确定相关多色Ramsey数的上界

6、。随机图理论是目前图论研究中比较热门的方向之一，它是由Erd6s和R6nyi建立起来的，他们发现概率方法在解决图论中的某些极问题时非常有用。随机图Ramsey理论研究的一个重要方向是求解某些Ramsey性质的临界函数。OnlineRamsey游戏是随机图Ramsey理论研究的重要内容，其研究成果可以为经典图论中Ramsey数的求解提供参考。本文利用计算机构造与数学证明相结合的方法，对与圈相关的Ramsey数、相关极图问题和圈的非对称onlineRamsey游戏问题进行了研究。主要成果如下：对二部Ramsey数西(C2。；c2。)的研究。首先通过给出完全二部图j0一，卜

7、2耐。2和恐+1，2，l对于(C2。，c2。)可2-着色的方案，证明了二部Ramsey数6(C2，；C2。)的下界。在对6(C2。；％)上界的证明中，由归纳假设可知第一色子图中存在圈％-2。对于6(％；K2．2)上界的证明，通过分析不在C2。2上的4个顶点与其他顶点的邻接情况证明了当m≥4时6(C2。；K2，2)=m+l。而对于6(C2。；C6)上界的证明，由于不在C2。．2上的顶点有6个，所以证明的难度大大增加。通过对8种情形的详细分析最终证明了当m三4时6(C2，；C6)=m+2。对四色Ramsey数R(c6，两，飓，凰)的研究，其中凰，凰和飓分