关于一类特殊联图的交叉数的研究

发布时间：2018-01-01 22:20

  本文关键词：关于一类特殊联图的交叉数的研究　出处：《湖南师范大学》2015年硕士论文　论文类型：学位论文

  更多相关文章： 图 圈 画法 交叉数 联图

【摘要】：图的交叉数是在近代图论中发展起来的一个重要概念,起源于19世纪五十年代,是拓扑图论中的前沿问题.它主要研究图在一个平面或曲面上最优画法下的最小交叉数目,是图的非平面性的一个重要参数.由于其在电路板设计和生物工程DNA图示等领域的广泛应用,吸引着众多国内外的专家和学者的关注与研究.但Garey和Johnson已确定一般图的交叉数是NP-完全问题.因而,到目前为止,有关图的交叉数方面的研究结果较少.但在一些特殊图类和简单图的交叉数方面的研究结果还是比较丰富的.本文主要确定了几个特殊的五阶图和圈Cn的联图的交叉数,其中包过W4+Cn的交叉数的证明,并且在此基础上还提出了关于Wm1+Cn的交叉数的猜想.本文主要结构如下：第一章：绪论,简述图的交叉数的起源和应用意义,介绍研究背景及本文的结构.第二章：给出本文用到的图论的一些基本的概念,以及在后文中常用的性质、引理.第三章：确定了几个特殊的五阶图和圈Cn的联图的交叉数.第四章：关于Wm+Cn的交叉数的证明及猜想.第五章：总结本文和展望未来工作.
[Abstract]:The cross number of graphs is an important concept developed in modern graph theory, which originated in 1850s. It is a frontier problem in topological graph theory. It mainly studies the minimum cross number of graphs under the optimal drawing on a plane or surface. It is an important parameter of non-planarity of graphs, because of its wide application in the field of circuit board design and bioengineering DNA diagram. It has attracted the attention and research of many experts and scholars at home and abroad, but Garey and Johnson have determined that the crossing number of general graphs is NP-complete problem. There are few results on the cross number of graphs, but there are abundant results in some special graphs and simple graphs. In this paper, we mainly determine some special fifth-order graphs and the associative graphs of cycles CN. The cross number of. In this paper, we prove the crossover number of W4Cn, and put forward the conjecture about the crossover number of Wm1 CN. The main structure of this paper is as follows: chapter 1: introduction. This paper briefly describes the origin and application significance of cross number of graphs, introduces the research background and the structure of this paper. Chapter 2: gives some basic concepts of graph theory used in this paper, as well as the properties commonly used in later papers. Lemma. Chapter 3: determine the crossover numbers of some special fifth-order graphs and cycles CN. Chapter 4th: proof and conjecture on the crossover number of Wm CN. Chapter 5th: summary of this paper and prospect of future work.
【学位授予单位】：湖南师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 周志东;黄元秋;彭小多;欧阳娟;;一个小图与路和圈的联图的交叉数[J];系统科学与数学;2013年02期

2 李敏;;一个五阶图与n个孤立点及路的联图的交叉数[J];湖北文理学院学报;2013年11期

3 麦安婵;联图的邻域完整度[J];南阳师范学院学报(自然科学版);2004年09期

4 郑敦勇;黄元秋;;一个五点图和路的联图的交叉数[J];汕头大学学报(自然科学版);2011年04期

5 王晓琦;田双亮;薛国梁;孙向涛;;若干图的广义联图的星全染色[J];西北民族大学学报(自然科学版);2012年02期

6 李敏;;两个5阶图与路及圈的联图的交叉数[J];河南师范大学学报(自然科学版);2013年04期

7 张德龙;关于联图的圈唯一性[J];广西工学院学报;1997年01期

8 周志东;吕胜祥;;关于一个特殊六阶图与路和圈的联图的交叉数[J];数学进展;2014年01期

9 田双亮;;若干联图的邻点可区别全染色[J];西北民族大学学报(自然科学版);2006年01期

10 柳顺义;陈祥恩;;关于联图的强色指数的一点注记[J];甘肃科学学报;2008年02期

相关博士学位论文 前2条

1 欧阳章东;关于图的交叉数问题研究[D];湖南师范大学;2011年

2 周志东;图的交叉数有关问题研究[D];湖南师范大学;2013年

相关硕士学位论文 前10条

1 彭小多;几类联图的交叉数研究[D];湖南师范大学;2012年

2 岳为君;关于一类特殊联图的交叉数的研究[D];湖南师范大学;2015年

3 欧阳娟;特殊图G与路与圈以及与孤立点的联图的交叉数[D];湖南师范大学;2012年

4 孟献青;联图的全染色及邻点可区别全染色[D];山西大学;2007年

5 李婷;关于积图和联图的交叉数问题研究[D];北京师范大学;2008年

6 魏甲静;几个特殊图与空图、路、圈的联图的交叉数[D];西北师范大学;2013年

7 景京;连通度与奇H-联图[D];华中师范大学;2008年

8 李光荣;几类联图的全着色研究[D];中国人民解放军信息工程大学;2005年

9 陈园;图的模linkage研究[D];华中师范大学;2006年

10 赵丽桃;几类图的邻点可区别全染色[D];山西大学;2009年

，

本文编号：1366459