论文摘要
我们已经知道确定图的交叉数是一个NP完全问题（见文献[2]），正是因为其计算复杂性，目前为止有关交叉数的结果比较少，甚至在许多情况下，找出图的一个好的上界或下界也很艰难。对具体图类的研究方法和图自身的结构特征紧密相连，相同的方法甚至不能用在结构相近的两类图上。本文具体研究了路，圈与某些6-阶图的笛卡儿积图交叉数。首先，交代了本文的写作背景，交叉数研究在国内外发展的动态，研究工作的意义以及本文中要解决的问题和创新之处。然后，给出了一些基本概念和性质，介绍了阅读本文所需要的预备知识其中主要包括交叉数的概念，并介绍了在后面文章中会出现的一些相关概念、性质以及常用到的一些定理，而部分使用较少的概念等我们放到了具体的章节中去交代。再接下来，在第三章，对图K3,3×Pn在一个已知上界的限制下的结构做了具体细分，同时运用归纳法，确定了K3,3×Pn的交叉数。在第四章，先确定一个子图的交叉数，通过母图的交叉数大于等于子图的交叉数，从而确定了笛卡尔积图S5×Cn及S5×Sn的交叉数。最后指出了研究工作中遇到的一些问题以及作者以后研究的主攻方向。
论文目录
相关论文文献
- [1].一个五阶图与路及圈的联图的交叉数[J]. 湖北文理学院学报 2012(11)
- [2].一个六阶图与路联图的交叉数[J]. 内江师范学院学报 2013(10)
- [3].两个5阶图与路及圈的联图的交叉数[J]. 河南师范大学学报(自然科学版) 2013(04)
- [4].K_(2,3)∨P_n的交叉数[J]. 高校应用数学学报A辑 2012(04)
- [5].S_m∨P_n与S_m∨C_n的交叉数[J]. 数学进展 2011(05)
- [6].G_(10)×S_n的交叉数[J]. 南华大学学报(自然科学版) 2010(04)
- [7].五阶图与星图的笛卡尔积交叉数[J]. 哈尔滨工业大学学报 2009(03)
- [8].一个五阶图与路、圈的联图的交叉数[J]. 数学的实践与认识 2014(11)
- [9].W_m∨P_n的交叉数[J]. 数学研究 2012(03)
- [10].一个五阶图与星图的笛卡尔积交叉数[J]. 河南师范大学学报(自然科学版) 2009(01)
- [11].S_5∨C_n的交叉数[J]. 数学研究 2013(04)
- [12].W_5×S_n的交叉数[J]. 山西师范大学学报(自然科学版) 2009(01)
- [13].W_4 ∨ C_n的交叉数[J]. 数学杂志 2015(03)
- [14].W_6×S_n的交叉数[J]. 运筹学学报 2013(02)
- [15].关于六阶图与星的笛卡儿积交叉数[J]. 湖南文理学院学报(自然科学版) 2008(01)
- [16].K_5\e×S_n的交叉数[J]. 湖南文理学院学报(自然科学版) 2011(01)
- [17].K_4∨C_n的交叉数[J]. 数学的实践与认识 2014(08)
- [18].W_5×S_n的交叉数[J]. 应用数学学报 2008(04)
- [19].K_m~-□P_n的交叉数[J]. 数学学报(中文版) 2016(03)
- [20].关于一个特殊六阶图与路和圈的联图的交叉数[J]. 数学进展 2014(01)
- [21].一个小图与路和圈的联图的交叉数[J]. 系统科学与数学 2013(02)
- [22].图的交叉数综述[J]. 华东师范大学学报(自然科学版) 2010(03)
- [23].最优画法的一个充分条件[J]. 邵阳学院学报(自然科学版) 2016(04)
- [24].｛P_6~2+e｝×S_n的交叉数[J]. 吉首大学学报(自然科学版) 2012(04)
- [25].关于1-齐次图的一种分类[J]. 青海师专学报 2008(05)
- [26].一类笛卡尔积图的交叉数[J]. 吉首大学学报(自然科学版) 2008(06)
- [27].六阶图Q与星图S_n的积图交叉数[J]. 数学的实践与认识 2017(12)
- [28].K_(1,1,2,2)×S_n的交叉数[J]. 计算机工程与应用 2018(14)
- [29].一个六阶图与星图的笛卡儿积的交叉数(英文)[J]. 湖南文理学院学报(自然科学版) 2008(02)
- [30].六阶图G与S_n的积图的交叉数[J]. 数学研究 2011(04)