关于两类特殊图的交叉数的下界
发布时间：2020-08-02 05:35
【摘要】：图的交叉数是衡量一个图与平面图距离有多远的标准,也是图的一个重要参数,并且具有相当广泛的实际应用.但是,M.R.Garey和D.S.Johnson曾经证明了图的交叉数问题是NP-难问题[2],而且交叉数问题一直是拓扑图论中的前沿难题.现在还没有一个统一的方法来计算图的交叉数,因此关于这方面的结果并不丰富.本篇论文主要研究两类特殊图的交叉数的下界.第一部分:运用局部构建新图法建立了完全三部图K3,3,n与完全二部图K6,n+3的交叉数关系,从而得到了它的一个下界值;第二部分:运用收缩手术,求出了笛卡尔积图K2,6 × Sn的交叉数的下界值.本文主要分为下面五个章节:第一章:绪论,主要介绍了图论的研究背景以及目前所出现的几类特殊图的研究成果,简要的概括研究内容.第二章:主要给出本文中会涉及到的基本概念及相关性质,介绍本文的主要结果.第三章:首先介绍了本章所需要的概念与引理,对K3,3,,n的交叉数下界值进行证明.第四章:给出了本章所需要的引理,建立笛卡尔积图K2,6 ×Sn与完全三部图K2,6,n之间的交叉数关系,从而部分解决了猜想:cr(K2,m X Sn)= cr(K2,m,n)+n[m/2][m-1/2](m ≥ 5).第五章:总结与展望.
【学位授予单位】：湖南师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：
令Ｇ表示所有位于位于和＾ｅ３，ｉ＋１）形成的７ｉ边集合／＃，其中下标取逡逑模３．逡逑如图３．１所示，我们有ＥＬ⑷＝闯＝ＥＬ呦＝ｎ．另外，在平逡逑面ｉＥ２，存在关于祝办）的圆盘领域，ｉＶ（４（ａ：ｆｃ），ｅ）邋＝邋｛ｓ邋ｅ邋ｉ？２邋：丨丨ｓ邋－《（办）丨丨＜邋ｅ｝，逡逑其中ｅ充分小，并满足於，３，？中不与办相关联的边ｅ，有咖）ｎ邋ｉＶ（火办），0邋＝邋０．逡逑下面，由欠３，３，？任意画法也我们构造私，？＋３的一个画法么．逡逑步骤１：增加一个新点知＋１在《（ｅｄｎｉＶＯ＾ｉ）＃）的某个位置上．逡逑步骤２：对所有１彡ｉ邋＜邋３，去掉位于（注意保留知＋１）．逡逑步骤３：分别连接２？＋１和侦；ｄ），多（２：２），办３），《⑷，多（ｙ２），你３）｝．逡逑例如，连接２？＋１１；和４（０：１）沿着外１，１）（＂１＾＾（０；１），￡），连接４＋１到４（２／１）首先逡逑沿着多（ｅｉａ）邋ｎｉＶＷｈ），＾），然后沿着ｉＶ＾ｘＡｅ）的外部？接着，连接＿２ｎ＋１逡逑和火如）首先沿着ａｉ邋（靠近４（ａ：ｉ））
逦＝逦（ｆ＞｛＾ｓ，３，ｎ）邋＋邋Ｃｉ邋＋邋ｃ？ｉ邋＋邋ｅｉ邋＋邋２ｎ邋＋邋Ａｃｒ＾＾Ｓｙ＾邋＋邋９．（３．１．２）逡逑完全类似上述过程，得到私，ｎ＋３的另外两个画法如和如如图３．２逡逑Ｍ：；逡逑ｃ，邋／？＇逡逑／邋ｃ３逡逑／逡逑⑴逡逑广逡逑（２）逡逑图３．２：从＜＾（／＾３，３，７１）得到＾６，ｎ＋３的两个画法也和如逡逑因此逡逑＾２（７＾６，７１＋３）邋＝邋ｃｒ＾（ｉｆ３，３，ｎ）邋＋邋１＾２！邋＋邋｜＾３｜邋＋邋Ｉ－Ｂ２Ｉ邋＋邋１＾３！邋＋邋ＩＣ２Ｉ邋＋邋ＩＣ＾Ｉ逡逑＋邋２ｔｉ邋＋邋４。７＊彡（５＾９）邋＋邋９．逡逑１３逡逑
逡逑时私，６的画法乃在同构意义下是唯一的，如图４．４所示，而且任何一个区域最多逡逑含有欠２，６的６个顶点，所以Ｇ中欠２０６顶点一定会落在欠２，６的任何至少两个区域逡逑中，类似情形３．１，有＞邋４，矛盾？逡逑子情况３．３邋如果ｃｔ￡ｉ（／１）邋＝邋２，因为ｃｒｘ＾ＡｕＣ）邋＝邋４，那么彡邋２，这逡逑时私，６的画法乃在同构意义下如图４．５所示，而且至少有两个区域才能含有＆｜６的逡逑所有顶点，当Ｇ中欠２Ｑ６顶点落在至少两个区域中，类似情形３．１，有彡逡逑４，矛盾．逡逑子情况３．４如果ｃｒ0（＞４）邋＝邋３，因为ｃｒＤ0ｌ邋Ｕ逦＝邋４，则ｃｒ＾ＣＡＣ）彡１，这时在逡逑同构意义下私
本文编号：2778229
【学位授予单位】：湖南师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：
令Ｇ表示所有位于位于和＾ｅ３，ｉ＋１）形成的７ｉ边集合／＃，其中下标取逡逑模３．逡逑如图３．１所示，我们有ＥＬ⑷＝闯＝ＥＬ呦＝ｎ．另外，在平逡逑面ｉＥ２，存在关于祝办）的圆盘领域，ｉＶ（４（ａ：ｆｃ），ｅ）邋＝邋｛ｓ邋ｅ邋ｉ？２邋：丨丨ｓ邋－《（办）丨丨＜邋ｅ｝，逡逑其中ｅ充分小，并满足於，３，？中不与办相关联的边ｅ，有咖）ｎ邋ｉＶ（火办），0邋＝邋０．逡逑下面，由欠３，３，？任意画法也我们构造私，？＋３的一个画法么．逡逑步骤１：增加一个新点知＋１在《（ｅｄｎｉＶＯ＾ｉ）＃）的某个位置上．逡逑步骤２：对所有１彡ｉ邋＜邋３，去掉位于（注意保留知＋１）．逡逑步骤３：分别连接２？＋１和侦；ｄ），多（２：２），办３），《⑷，多（ｙ２），你３）｝．逡逑例如，连接２？＋１１；和４（０：１）沿着外１，１）（＂１＾＾（０；１），￡），连接４＋１到４（２／１）首先逡逑沿着多（ｅｉａ）邋ｎｉＶＷｈ），＾），然后沿着ｉＶ＾ｘＡｅ）的外部？接着，连接＿２ｎ＋１逡逑和火如）首先沿着ａｉ邋（靠近４（ａ：ｉ））
逦＝逦（ｆ＞｛＾ｓ，３，ｎ）邋＋邋Ｃｉ邋＋邋ｃ？ｉ邋＋邋ｅｉ邋＋邋２ｎ邋＋邋Ａｃｒ＾＾Ｓｙ＾邋＋邋９．（３．１．２）逡逑完全类似上述过程，得到私，ｎ＋３的另外两个画法如和如如图３．２逡逑Ｍ：；逡逑ｃ，邋／？＇逡逑／邋ｃ３逡逑／逡逑⑴逡逑广逡逑（２）逡逑图３．２：从＜＾（／＾３，３，７１）得到＾６，ｎ＋３的两个画法也和如逡逑因此逡逑＾２（７＾６，７１＋３）邋＝邋ｃｒ＾（ｉｆ３，３，ｎ）邋＋邋１＾２！邋＋邋｜＾３｜邋＋邋Ｉ－Ｂ２Ｉ邋＋邋１＾３！邋＋邋ＩＣ２Ｉ邋＋邋ＩＣ＾Ｉ逡逑＋邋２ｔｉ邋＋邋４。７＊彡（５＾９）邋＋邋９．逡逑１３逡逑
逡逑时私，６的画法乃在同构意义下是唯一的，如图４．４所示，而且任何一个区域最多逡逑含有欠２，６的６个顶点，所以Ｇ中欠２０６顶点一定会落在欠２，６的任何至少两个区域逡逑中，类似情形３．１，有＞邋４，矛盾？逡逑子情况３．３邋如果ｃｔ￡ｉ（／１）邋＝邋２，因为ｃｒｘ＾ＡｕＣ）邋＝邋４，那么彡邋２，这逡逑时私，６的画法乃在同构意义下如图４．５所示，而且至少有两个区域才能含有＆｜６的逡逑所有顶点，当Ｇ中欠２Ｑ６顶点落在至少两个区域中，类似情形３．１，有彡逡逑４，矛盾．逡逑子情况３．４如果ｃｒ0（＞４）邋＝邋３，因为ｃｒＤ0ｌ邋Ｕ逦＝邋４，则ｃｒ＾ＣＡＣ）彡１，这时在逡逑同构意义下私
【参考文献】
相关期刊论文 前5条
1 欧阳章东;黄元秋;;关于K_(2,2,2)□S_n的交叉数[J];应用数学学报;2015年06期
2 吕胜祥;黄元秋;;K_(2,4)×S_n的交叉数[J];系统科学与数学;2010年07期
3 张莉茜;李波;黄元秋;;关于六阶图与星的笛卡儿积交叉数[J];湖南文理学院学报(自然科学版);2008年01期
4 黄元秋;赵霆雷;;ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_(1,8,n)[J];数学物理学报;2006年S1期
5 黄元秋;赵霆雷;;关于完全3-部图K_(1,6,n)的交叉数[J];应用数学学报;2006年06期
相关博士学位论文 前1条
1 王晶;若干图类交叉数的研究[D];湖南师范大学;2009年
本文编号：2778229
本文链接：https://www.wllwen.com/kejilunwen/yysx/2778229.html
