导读:本文包含了可嵌入性论文开题报告文献综述、选题提纲参考文献及外文文献翻译,主要关键词:亏格,哈密,立方体,柔性,蕾丝,曲面,临界。
可嵌入性论文文献综述
董广华,王宁,黄元秋,任韩,刘彦佩[1](2014)在《顶点劈分与图的上可嵌入性(英文)》一文中研究指出一个图G的弱子式G是通过对G进行边收缩得到的.一个弱子式封闭的上可嵌入图族是一个上可嵌入图的集合,并且该集合中任何图的弱子式仍在这个集合中.目前关于判断图的上可嵌入性的充要条件很少.本文通过研究顶点劈分与图的上可嵌入性的关系得出一个判断图的上可嵌入性的充要条件;给出了一个从环束出发构造弱子式封闭上可嵌入图族的方法;推广了[J.Graph Theory,1981,5(2):205-207]的一个结论.并且,用本文所得结论判断图的上可嵌入性时其算法复杂度会得到很大降低.(本文来源于《数学进展》期刊2014年05期)
殷超杰[2](2013)在《父叉立方体里有条件点错误情况下哈密顿圈的可嵌入性讨论》一文中研究指出超立方体网络是现今最着名、最通用的,也是最有效的互联网拓扑结构.因为它具有:正则性、对称性、强连通性、可嵌入性、哈密尔顿性、容错性等性质,以及自身很强的递归结构.但是,超立方体也有它固有的缺点.例如它的直径较大.交叉立方体作为超立方体的一种重要变形结构,具有直径短、递归结构简单等特点,一直是国际上的研究热点,因而它的容错性研究也备受关注.网络结构的可嵌入性是衡量该网络结构优劣的重要指标之一,因此网络结构的泛圈性和哈密顿圈的可嵌入性也就成了评价网络结构优劣的重要标准.在投入使用的一些网络结构中,它们的组成元件和线路会难以避免的出现故障,通常所说的网络容错性是指该网络结构的一些元件和(或)连线出现故障时所能允许的故障个数,而所剩余的子网络仍然能保证该网络结构的畅通性和实用性,因此网络容错性研究具有一定的实际意义.而交叉立方体网络自身的图论性质和条件点错误情况下哈密顿圈的可嵌入性研究亦将作为本文中的主要工作.早在1995年Kulasinghe P等人就证明了:当n≥5时,交叉立方体CQn就不再具备可迁性.因为这个缺点给较高维的交叉立方体的研究工作带来诸多不便,所以本文对交叉立方体自身的图论性质进行了更深入的讨论,并利用群论的相关知识对交叉立方体进行了结构划分,确定了这个群的具体形式和群中元素的个数.这个结果为进一步研究高维交叉立方体网络打下了坚实基础,也为交叉立方体的容错性及嵌入研究提供了技术手段和理论支持.另外,本文在研究交叉立方体网络结构性质的同时还主要讨论了条件容错问题,即条件点错误情况下哈密顿圈的可嵌入性讨论.由于高维交叉立方体网络结构的不可迁性,所以要在含有故障元素的交叉立方体中寻找非故障的哈密顿圈是比较困难的.本文中,我们借助前人的一些研究经验和成果,采用代数的方法创新性地提出了一些新的理论,并进行了严格论证.例如,本文提出并论证了:若n维交叉立方体CQn中,每一个健康节点至少还有其它两个健康节点与之相邻,当n≥4时,只要CQn中错误节点的个数f≤2n-7,则CQn-F中至少存在一个长为2n-f哈密顿圈,其中F为故障集.这个结果把Hai-Liang等人的研究进行了改进和完善.(本文来源于《广东工业大学》期刊2013-05-29)
刘端凤[3](2013)在《关于图的上可嵌入性研究》一文中研究指出图论是一门古老而又有趣的学科。它主要研究用某种方式联系起来的若干事物之间的二元或者多元的关系,其中包括拓扑图论、代数图论、化学图论、算法图论、网络图论、模糊图论等研究领域。它也是一门应用相当广泛的学科。在物理、化学、通讯科学、计算机技术以及信息技术等各种学科中都有应用。目前,拓扑图论逐渐地发展成为了一个非常活跃的图论分支。拓扑图论的发展极大地丰富了图论、拓扑学和组合学的内容。它主要是利用组合的各种方法来研究曲面的性状,进行曲面元的刻画。它的核心内容是研究图在曲面上的各种嵌入性质,特别是2-胞腔嵌入。因为一个图可以在多种不同的曲面上有多种可能的嵌入,所以研究图在曲面上嵌入的极值情况具有非常重要的意义。而图能上可嵌入到曲面上,就是指图的最大嵌入亏格取到它的上界的特殊情况,因而研究图的上可嵌入性也引起了广大图论学者的浓厚兴趣。关于图的上可嵌入性这一课题的研究,主要体现在两个方面:希望能找到一些图类,使得它们的最大亏格取到上界,从而图是上可嵌入的;对于非上可嵌入图,希望能找到它们的最大亏格的较好的下界。本论文主要利用图的一些不变量,如直径,围长,点的度,独立数,非邻节点的度和等,研究了图的上可嵌入性以及非上可嵌入图的最大亏格的下界。具体研究工作主要体现在以下几个方面:(1)研究了直径为3且不含3阶完全子图的图的上可嵌入性:若图G是一个直径为3的简单图,且G中不含3阶完全子图K3,则图G是上可嵌入的,也即ξ(G)≤1。这个结果与其他学者所做的结论一起,基本上完善了直径为3的图的上可嵌入性讨论。(2)给出了直径为4且不含3阶完全子图的图的最大亏格的紧下界:若G是直径为4的简单图,且G不含3阶完全子图K3则ξ(G)≤2。这改善了文献[79]的相关结果。(3)研究了直径为4且不含k-圈(k≤4)的图的上可嵌入性:设G是直径为4的简单图,若G不含k-圈(k≤4),则ξ(G)≤1,也即G是上可嵌入的。这与(2)一起,比较完整地研究了直径为4的图的上可嵌入性。(4)用多个非邻节点度和以及独立数研究了一类半双图和单瓣图的上可嵌入性:设G是一个阶为,n的2-边连通半双图,若G满足条件(a)或(b):(a) α(G)≤2;(b)α(G)≥3,且对于任何彼此不相邻的叁个顶点ui,(i=1,2,3)都有则G是上可嵌入的。而且条件(b)中的下界是最好的。这改善并推广了文献[88]的相关结果。对于阶为n的2-边连通单瓣图的上可嵌入性,相对于半双图来说,要复杂一些,我们也得到了类似的结果。(5)研究了一类有环的非简单图和它的补图的上可嵌入性:设G是连通图,若G满足条件(a)或(b):(a)无环;(b)有环,但任意一个带环的顶点w,w带的环的个数都是偶数。则G或者Gc是上可嵌入的。而文献[82]只考虑了无环图和它的补图的上可嵌入性。(6)利用图的一些其他参数,比如点的度,2-因子等,研究图的上可嵌入性,得到了一些新的上可嵌入图类。推广和补充了相关结果。(本文来源于《中南大学》期刊2013-04-01)
魏二玲,李益凡[4](2013)在《广义Petersen图的消圈数与上可嵌入性》一文中研究指出给定图G=(V,E),S■V,若G-S(图G中去掉S中的点以及与其关联的所有边)是一个无圈图,则称S是图G的一个消圈集,且称min{|S|}S是图G的消圈集}为图的消圈数,记为▽(G).图的消圈数的求解是NP完全的.Bau和Beineke提出了如下问题:什么样的阶为2n的3正则图G,其消圈数为[(n+1)/2]?本文对广义Petersen图的消圈数进行了讨论,从而证明了这类图的消圈数恰好为[(n+1)/2].利用消圈集的性质,进一步可推出,这类图是上可嵌入的.(本文来源于《数学学报》期刊2013年02期)
王涛,李德明[5](2012)在《简单图的支配数和上可嵌入性(英文)》一文中研究指出设图G是n阶简单连通图.如果G的支配数为1,则G是上可嵌入的.如果G是2-边连通且G的支配数为2,则G是上可嵌入的.如果G是3-边连通且G的支配数为3,则G的最大亏格介于|(β(G)-2)/2|和|β(G)/2|之间,其中β(G)=|E(G)|-|V(G)|+1.论文得到了一些在控制数和边连通度条件下的最大亏格的界.(本文来源于《安徽大学学报(自然科学版)》期刊2012年06期)
黄元秋,郭婷[6](2012)在《关于图的上可嵌入性的一个注记》一文中研究指出任韩和李刚在图的最大亏格综述一文"Survey of maximum genus of graphs"[J East China NormUniv Natur Sci,Sep.2010,No.5,1-13]中,全面地阐述了近30年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想:猜想1设G为简单连通图,且G的每条边含在一个叁角形K3中,则G是上可嵌入的.猜想2设c为任意的正数,则存在一个自然数N(c),使得对每一个图G,若G的点数n N(c),且最小度δ(G)cn,则G是上可嵌入的.本文的主要工作是否定上述两个猜想,同时探讨上述猜想成立的条件且得了一些新结果,并提出有关进一步研究的问题.(本文来源于《中国科学:数学》期刊2012年09期)
卢晓丽[7](2012)在《交换超立方体网络中路的可嵌入性分析》一文中研究指出人们通常用连通的简单图G=(V,E)来表示互连网络的拓扑结构,其中图G的顶点代表网络中的组件,连线代表组件之间的通信联系,而图的嵌入问题是研究互连网络拓扑结构的中心问题之一,它的重要性在于我们可以将关于客图的已有算法应用于主图.路的结构简单,所以其上通信算法成本低,因此研究路的嵌入问题是非常重要的.超立方体Qn是常见的互连网络拓扑结构之一.交换超立方体(EH(s,t))作为超立方体的一个重要变型是由Loh等提出的,该图是从超立方体中有条理的删除一些边得到的.交换超立方体保留了大多数超级立方体的优良的性质,并且减少了网络的复杂度.交换超立方体EH(s,t)与超立方体Qs+t+1的点数相同,而EH(s,t)的边数几乎只有Qs+t+1的一半.因此,交换超立方体EH(s,t)的性质具有研究价值.本文讨论交换超立方体,主要研究EH(s,t)的哈密顿可蕾丝性和强哈密顿可蕾丝性,以及其宽直径和容错直径.运用构造法和数学归纳法证明了:(1)当s,t≥2时,EH(s,t)是哈密顿可蕾丝的,也是强哈密顿可蕾丝的;(2) EH(s,t)的宽直径dω(EH(s,t))和容错直径Dω(EH(s,t))有如下关系:(本文来源于《浙江师范大学》期刊2012-05-27)
刘端凤,刘新儒[8](2011)在《图的上可嵌入性与2-因子(英文)》一文中研究指出对含有4边形2因子的3连通图和k正则图的上可嵌入性进行了讨论,得到了一些上可嵌入图类.(本文来源于《吉首大学学报(自然科学版)》期刊2011年04期)
吴甬翔,李刚,李浩玲,任韩[9](2011)在《图的局部连通性与上可嵌入性》一文中研究指出研究局部连通图中支撑树的变换.给出L.Nebesk定理的一个新证明,并将其推广得到一类新的上可嵌入图.(本文来源于《华东师范大学学报(自然科学版)》期刊2011年02期)
苏振华,黄元秋[10](2010)在《关于(ξ,1)-临界图与上可嵌入性》一文中研究指出设G为连通图,且(ξG)=k≥1,若对G中任意边e,有ξ(Ge)=k-1,则称G为(ξ,k)-临界图.利用ξ-1-临界图的上可嵌入性,通过研究ξ-1-临界图的加重边、点扩张、圈扩张的ξ-1-临界性,得到了新的上可嵌入图,从而丰富了上可嵌入图的种类和求法.(本文来源于《吉首大学学报(自然科学版)》期刊2010年03期)
可嵌入性论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
超立方体网络是现今最着名、最通用的,也是最有效的互联网拓扑结构.因为它具有:正则性、对称性、强连通性、可嵌入性、哈密尔顿性、容错性等性质,以及自身很强的递归结构.但是,超立方体也有它固有的缺点.例如它的直径较大.交叉立方体作为超立方体的一种重要变形结构,具有直径短、递归结构简单等特点,一直是国际上的研究热点,因而它的容错性研究也备受关注.网络结构的可嵌入性是衡量该网络结构优劣的重要指标之一,因此网络结构的泛圈性和哈密顿圈的可嵌入性也就成了评价网络结构优劣的重要标准.在投入使用的一些网络结构中,它们的组成元件和线路会难以避免的出现故障,通常所说的网络容错性是指该网络结构的一些元件和(或)连线出现故障时所能允许的故障个数,而所剩余的子网络仍然能保证该网络结构的畅通性和实用性,因此网络容错性研究具有一定的实际意义.而交叉立方体网络自身的图论性质和条件点错误情况下哈密顿圈的可嵌入性研究亦将作为本文中的主要工作.早在1995年Kulasinghe P等人就证明了:当n≥5时,交叉立方体CQn就不再具备可迁性.因为这个缺点给较高维的交叉立方体的研究工作带来诸多不便,所以本文对交叉立方体自身的图论性质进行了更深入的讨论,并利用群论的相关知识对交叉立方体进行了结构划分,确定了这个群的具体形式和群中元素的个数.这个结果为进一步研究高维交叉立方体网络打下了坚实基础,也为交叉立方体的容错性及嵌入研究提供了技术手段和理论支持.另外,本文在研究交叉立方体网络结构性质的同时还主要讨论了条件容错问题,即条件点错误情况下哈密顿圈的可嵌入性讨论.由于高维交叉立方体网络结构的不可迁性,所以要在含有故障元素的交叉立方体中寻找非故障的哈密顿圈是比较困难的.本文中,我们借助前人的一些研究经验和成果,采用代数的方法创新性地提出了一些新的理论,并进行了严格论证.例如,本文提出并论证了:若n维交叉立方体CQn中,每一个健康节点至少还有其它两个健康节点与之相邻,当n≥4时,只要CQn中错误节点的个数f≤2n-7,则CQn-F中至少存在一个长为2n-f哈密顿圈,其中F为故障集.这个结果把Hai-Liang等人的研究进行了改进和完善.
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
可嵌入性论文参考文献
[1].董广华,王宁,黄元秋,任韩,刘彦佩.顶点劈分与图的上可嵌入性(英文)[J].数学进展.2014
[2].殷超杰.父叉立方体里有条件点错误情况下哈密顿圈的可嵌入性讨论[D].广东工业大学.2013
[3].刘端凤.关于图的上可嵌入性研究[D].中南大学.2013
[4].魏二玲,李益凡.广义Petersen图的消圈数与上可嵌入性[J].数学学报.2013
[5].王涛,李德明.简单图的支配数和上可嵌入性(英文)[J].安徽大学学报(自然科学版).2012
[6].黄元秋,郭婷.关于图的上可嵌入性的一个注记[J].中国科学:数学.2012
[7].卢晓丽.交换超立方体网络中路的可嵌入性分析[D].浙江师范大学.2012
[8].刘端凤,刘新儒.图的上可嵌入性与2-因子(英文)[J].吉首大学学报(自然科学版).2011
[9].吴甬翔,李刚,李浩玲,任韩.图的局部连通性与上可嵌入性[J].华东师范大学学报(自然科学版).2011
[10].苏振华,黄元秋.关于(ξ,1)-临界图与上可嵌入性[J].吉首大学学报(自然科学版).2010