几类图的优美性-研究

《几类图的优美性-研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、KEYWORDS：gracefulgraph；k—graceful；chaingraph；7Yti—circlechaingraphwithahandle；mi—circlechaingraphwithouthandleVVI摘要ABSTRACT目录IIV第一章绪论11．1引言．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．11．2国内外研究现状．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．31．3本文研究的目的和研究内容．．．．．．．．．．．．．．．．．．．．．．

2、．．．．51．3．1本文研究的目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．51．3．2本文研究的主要内容．．．．．．．．．．．．．．．．，．。．．．。．．．5第二章基本概念与预备知识72．1基本概念与记号．．．．．．．．．．．．．．．．．．．．，．．．．．．．．．．．．72．1．1基本概念．．．．．．．。．．。．．．．．。．．．．．．．．．。．．．．．．72．1．2符号说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．92．2重要定义．．．．．．．．．．．．．．，．．．．．．．

3、．．．．．．．．．．．．．，．9第三章3．13．23．3结论一类新图的优美性关于有柄m。圈链图和无柄mi圈链图的优美性研究．．．．．．．无柄mi圈链图的奇优美性和奇强协调性．．．．．．．．．．．．．一类并图的奇优美性和奇强协调性．．．．．．．．．．．．．．．．43VII128l12参考文献致谢攻读硕士学位期间发表的撇独创性声明VIII535745§1．1引言第一章绪论1736年，这一年欧拉(Euler)研究了著名的哥尼斯堡七桥问题『21，发表了图论的首篇论文《哥尼斯堡的七座桥》，开创了图论科学的研究，这一年是图论的

4、历史元年．在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点?欧拉于1736年研究并解决了此问题，他把问题归结为Ⅳ一笔画”问题，并证明上述走法是不可能的．《有限图与无限图理论》是图论的第一部专著，它总结了图论二百年的主要成果，是1936年匈牙利著名图论学家Konig发表的，是图论发展的重要里程碑．从此以后，图论开始飞速发展起来，随之成为数学科学中一门独立的学科．图论的分支非常多，如极值图论、算法图论、网络图论、模糊图沦、随机图论

5、、代数图论、超图论等等，随着现代科技尤其是大型计算机的迅猛发展，无论是数学、物理、化学、天文、地理、生物等基础科学，还是信息、交通、战争、经济乃至社会科学的众多问题，都可以应用图论方法予以解决，图论大有用武之地．图论中极有趣的研究课题之一是图的标号问题．它的研究始于1963年RingelG提出的一个猜想和1966年RoseA的一篇论文．对于一个图的顶点标号是指图的顶点集到整数集f一般的也可以是一个交换群)的映射，同样的边标号则是图的边集到整数集的映射．根据对映射的不同的要求，自然而然就产生了各种各样的图的标号问题．

6、到目前为止已有优美标号、平衡标号、调和标号、和谐标号、序列标号和边幻方标号等十几种不同的标号．由于它的趣味性和应用性，自上世纪60年代中期提出来后，很快得到了人们的重视，最近几十年来，这一课题非常活跃，有各种应用背景的需要不断产生新的标号，在证明一类特殊的图是优美图的同时，学者们也开始把目光集中到一些组合图上，所谓的组合的图是指用一些常规的图类，通过笛卡尔积，并图，一个点连接的方式等组合成一个新图．有关这方面的论文成千上万篇阱．5】．几类图的优美性研究1963年Ringel在文献[6】提出一个的猜想：设T是一个给定

7、的有几个顶点，n—l条边的树，那么由尬。一1可分解成2n一1个树同构于丁．1966年，Rosa在文献f7]中提出了非常著名的优美树猜想：所有的树都是优美的．他指出Ringel猜想的证明与此相关，即：若所有的树都是优美图，则对于有个顶点的树丁，由鲍口+1可分解出2q+1个树同构于丁，此猜想已被证明．Rosa在文献[7]还给出了更普通的结论：设G是一个有q条边的优美图，那么K2。+，可分解出2口+1个图同构于G．1972年，文献[8]S．W．GolombH)j确给出了无向优美图的定义，虽然Erdos在文献[9]一个未发

8、表的结论说大多数图都不是优美图，但结构上有某种规则的图通常是优美的，Sheppard在文献[10]ii[实有q条边的所有优美图的优美标号总共有q!种；Balakrishnan和Sampathkumarn[11]ilE明每个图是一个优美图的子图．Rosa在[7】中总结了～个图Gd<是优美图的二个基本原冈：(1)G有太多顶点且没有足够的边：(2)G有太多的边：(