特殊图与n个孤立点、路及圈的联图的交叉数

发布时间：2020-04-14 04:37

【摘要】：图的交叉数是在近代图论中逐渐发展起来,主要研究如何把图画在一个平面上,使交叉数的数目最少的一门学科.关于它的研究通常采用纯数学方法证明.然而,求一般图的交叉数已经证明是一个NP-完全问题.因此到目前为止,关于图的交叉数的研究仅限于一些特殊图类和简单图,结果较少.近年来,越来越多的学者开始研究特殊图,研究具有特殊结构的小阶图与n个孤立点、路及圈的联图的交叉数.本文根据交叉数已有的研究结果,结合图的特殊结构,运用组合方法、归纳推理、反证法以及排除法,得到了一个特殊的六阶图与n个孤立点、路及圈的联图的交叉数和一个特殊的不连通五阶图与路及圈的联图的交叉数.本文主要结构如下:第一章:绪论.详细介绍了交叉数的国内外研究动态、研究背景和意义,简要概括了本文的结构.第二章:预备知识.主要介绍了交叉数研究过程中需要的基本概念、性质和引理.第三章:得到了一个特殊的六阶图分别与n个孤立点、路及圈的联图的交叉数.第四章:确定了一个特殊的不连通五阶图与路Pn和圈Cn的联图的交叉数.第五章:结语.包括工作总结和研究展望.
【图文】：

引理邋３．１逦＝邋０，，ｃｒ（Ｑ２）邋＝邋２．逡逑证明首先证明ｃｒＷｄ邋＝邋０．从图３．３可知，Ｑ为完全平面图，有＝邋０．逡逑证明ｃｒ（Ｑ２）邋＝邋２，图３．３中Ｑ２的好画法必表明ｃｒ（Ｑ２）邋Ｓ邋ｃｔ＞（Ｑ２）邋＝邋２？下面证明逡逑对（？２的任意的好画法心均有２邋２．逡逑Ｑ，逦Ｑ－）逡逑图３．３：图和图的一个好画法逡逑８逡逑

逡逑图３．２：邋＜５邋Ｕ邋／（６，？的一个好画法逡逑本章的主要结果如下：逡逑定理邋３．１邋ｃｒ（＜５？）邋＝邋Ｚ（６，ｎ）邋＋邋２Ｌｆ」，ｎ２邋１．逡逑定理３．２邋ｃｒ＾Ｑ邋＋邋ｚｇ＾邋Ｚ（６，ｎ）邋＋２［Ｊｊ，ｎ邋２邋ｌ■逡逑定理３．３ｃｒ（Ｑ＋Ｃ＾？）＝Ｚ（６，ｎ）＋２Ｌｆ」＋２，ｎ２３？逡逑３．１邋Ｑ邋＋邋ｎＭ的交叉数的证明逡逑引理邋３．１逦＝邋０，ｃｒ（Ｑ２）邋＝邋２．逡逑证明首先证明ｃｒＷｄ邋＝邋０．从图３．３可知，Ｑ为完全平面图，有＝邋０．逡逑证明ｃｒ（Ｑ２）邋＝邋２，图３．３中Ｑ２的好画法必表明ｃｒ（Ｑ２）邋Ｓ邋ｃｔ＞（Ｑ２）邋＝邋２？下面证明逡逑对（？２的任意的好画法心均有２邋２．逡逑Ｑ，逦Ｑ－）逡逑图３．３：图和
【学位授予单位】：湖南师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】

相关期刊论文 前8条

1 苏振华;黄元秋;;五阶图与路P_n的联图交叉数[J];高校应用数学学报A辑;2014年02期

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

3 周志东;王晶;;W_6×S_n的交叉数[J];运筹学学报;2013年02期

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

5 苏振华;黄元秋;;W_m∨P_n的交叉数[J];数学研究;2012年03期

6 王晶;黄元秋;;完全3-部图K_(1，10，n)的交叉数[J];高校应用数学学报A辑;2008年03期

7 贺佩玲;黄元秋;;W_4×S_n的交叉数[J];郑州大学学报(理学版);2007年04期

8 黄元秋;赵霆雷;;关于完全3-部图K_(1,6,n)的交叉数[J];应用数学学报;2006年06期

相关博士学位论文 前2条

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

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

本文编号：2626884