检索结果-南通市图书馆

琼州大学学报 2002年第4期9卷 18-19页

作者：曾克扬琼州大学数学系海南五指山572200

深入研究包含 3连通的 2连通n阶哈密尔顿连通图 ,得到结果 :2连通n阶图G ,NC ≥n -δ 。

关键词： hamilton连通性邻域并条件哈密尔顿连通图 NC 例外

在线全文

学校读者我要写书评

暂无评论

HCH—立方体的hamilton连通性

计算机工程与应用 2005年第32期41卷 83-86页

作者：刘昕樊建席宗绪锋徐翠霞潍坊学院计算机科学系山东潍坊261043 青岛大学信息工程学院青岛266071

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络... 详细信息

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在hamilton路径,即HCH-立方体是hamilton连通的,而超立方体不是hamilton连通的。这表明HCH-立方体具备了交叉立方体在hamilton连通性方面的性质。文章还给出了在n维HCH-立方体中构造任意两个顶点之间hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数。

关键词：互连网络 HCH-立方体超立方体交叉立方体 hamilton-路 hamilton连通性

邻集并、连通度及最大度和hamilton连通性

在线全文

学校读者我要写书评

暂无评论

南通工学院学报（自然科学版） 2004年第2期3卷 9-11页

作者：范允征施声久张义清陈娟南通工学院应用数学系江苏南通226007

文章讨论了无爪图的hamilton连通性 ,给出邻集并与最大度的条件下hamilton连通图的新的充分条件,证明了下述定理 :设G是一个3 -连通简单无爪图 ,连通度为k。如果对于G的每一个k阶独立集S满足 :对 u,v∈S,都有(1)k>3时,│N(u)∪N(v)│... 详细信息

文章讨论了无爪图的hamilton连通性 ,给出邻集并与最大度的条件下hamilton连通图的新的充分条件,证明了下述定理 :设G是一个3 -连通简单无爪图 ,连通度为k。如果对于G的每一个k阶独立集S满足 :对 u,v∈S,都有(1)k>3时,│N(u)∪N(v)│≥n-Δ(s) -k +2,(2)k=3时,│N(u)∪N(v)│≥n -Δ(s),则G是hamilton连通的。

关键词：邻集圈连通度最大度 hamilton连通性连通图无爪图

在线全文

学校读者我要写书评

暂无评论

图的路圈性质的子图度型充分条件研究

图的路圈性质的子图度型充分条件研究

作者：孙运伟山东师范大学

学位级别：硕士

在图论中,图的路圈问题一直是我们研究的一个十分重要而且非常活跃的课题.图论中的hamilton司题本质上是图的路和圈问题,它是图论中的三大著名疑难问题之一.国内外许多学者在这一方面作了大量的研究工作,这方面的研究成果和进展可参见文... 详细信息

在图论中,图的路圈问题一直是我们研究的一个十分重要而且非常活跃的课题.图论中的hamilton司题本质上是图的路和圈问题,它是图论中的三大著名疑难问题之一.国内外许多学者在这一方面作了大量的研究工作,这方面的研究成果和进展可参见文献[33]-[37].经过几十年的研究和发展,图的路圈性质所涉及的内容日益丰富和具体.其中路方面包括图的hamilton路(可迹性),Dominating路,齐次可迹性,最长路,hamilton连通,Dominating连通,泛连通,路可扩等等;圈的方面包括图的hamilton圈,Dominating圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等.然而,由于在一般图中研究hamilton问题比较困难,所以人们转而在不含有某些禁用子图的图类中研究,如无爪图.继Beineke1970年发表的关于线图性质的文章[31]-[32]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[15]-[30].另外,无爪图的概念也被从不同角度推广到了更大的图类,如半无爪图,几乎无爪图等.本文主要探索了图的度型条件(任意两个不相邻子图的度和)与路圈性质(包括hamilton连通,hamilton圈,Dominating圈等)之间的关系,得出了一般图及无爪图的路圈性质的几个度型充分条件.在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.在第二章中,我们主要研究了无爪图的路圈性质的子图度型充分条件,得到下面的结果：定理2.1.9设G是n阶2-连通无爪图,如果G中任意两个同构于K1,K2的不相邻子图H1,H2满足：d(H1)+d(H2)≥n-3,则G的任意最长圈是hamilton圈.这里的下界”n-3”是最好可能的.定理2.2.9设G是n阶2-连通无爪图,如果G中任意两个同构于K1和K2的不相邻子图H1,Ht2满足：d(H1)+d(H2≥n,则对于G中任一对u,v,若{u,v}不是割集,则u,v可间存在hamilton路.推论2.2.10设G是n阶3-连通无爪图,如果G中任意两个同构于K1和K2的不相邻子图H1,H2满足：d(H1)+d(H2)≥n,则G是hamilton连通的.定理2.3.2对2-连通无爪图G,若任意同构于K2的不相邻子图H1,H2,H3满足：d(H1)+d(H2)+d(H3)≥｜G｜-1,则G的任意最长圈是Dominating圈.在第三章中,讨论了一般图的路圈性质的子图度型充分条件,得到下面的结果：定理3.1.1设G是n阶连通图,如果G中任意两个同构于K2的不相邻子图H1,H2满足：d(H1)+d(H2)≥n-4,则G的任意最长路是Dominating路.这里的下界”n-4”是最好可能的.定理3.1.2设G是n阶2-连通图,如果G中任意两个同构于K3和K2的不相邻导出子图H1,H2满足：d(H1)+d(H2)≥N-2,则G的任意最长路是Dominating路.推论3.1.3设G是n阶2-连通图,如果G中任意两个同构于K2和K2的不相邻导出子图H1,H2满足：d(H1)+d(H2)≥n-2,则G的任意最长路是Dominating路.定理3.2.1设G是n阶2-连通图,如果G中任意两个同构于K2,K2的不相邻导出子图H1,H2满足：d(H1)+d(H2)≥n-1,则G的任意最长圈是Dominating圈.推论3.2.2设G是n阶2-连通图,如果G中任意两个同构于K1和K2的不相邻子图H1,H2满足：d(H1)+d(H2)≥n-1,则G的任意最长圈是Dominating圈.定理3.2.3设G是n阶3-连通图,如果G中任意两个同构于K3,K2的不相邻导出子图H1,H2满足：d(H1)+d(H2)≥n-1,则G的任意最长圈是Dominating圈.定理3.3.1设G是n阶2-连通图,如果G中任意两个同构于K2的不相邻子图H1,H2满足：d(H1)+d(H2)≥n,则对于G中任一对u,v,若{u,v}不是割集,则u,v可间存在Dominating路.定理3.3.2设G是n阶2-连通图,如果G中任意两个同构于K2和K2的不相邻导出子图H1,H2满足：d(H1)+d(H2)≥n,则对于G中任一对u,v,若{u,v}不是割集,则u,v间存在Dominating路.推论3.3.3设G是n阶3-连通图,如果G中任意两个同构于K2的不相邻子图H1,H2满足：d(H1)+d(H2)≥n,则G是Dominating连通的.推论3.3.4设G是n阶3-连通图

关键词：无爪图子图的度 hamilton圈 hamilton连通性 Dominating路 Dominating圈 Dominating连通性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

HCH-立方体互连网络及其性质的研究

HCH-立方体互连网络及其性质的研究

作者：刘昕青岛大学

学位级别：硕士

并行处理系统是当今计算机科学研究的前沿。互连网络作为并行处理系统的主干，它的性质对整个网络的性能起着决定性作用。新型并行机的研制依赖于对新型互连网络的设计以及对互连网络的内在性质的研究。然而，互连网络的设计是一个多目... 详细信息

并行处理系统是当今计算机科学研究的前沿。互连网络作为并行处理系统的主干，它的性质对整个网络的性能起着决定性作用。新型并行机的研制依赖于对新型互连网络的设计以及对互连网络的内在性质的研究。然而，互连网络的设计是一个多目标最优化问题，这些目标包括小的网络直径，高连通度，每个处理器(图中的顶点)与其他处理器间的低连接数，可嵌入性，可扩展性，可诊断性与容错性，易实现性，正则性和好的通信算法等等。国际上已提出了许多种互连网络，其中超立方体以其低直径，高连通度，对称性等许多良好的性质已被用作多种并行机中处理器连接的拓扑结构。然而，超立方体并非各种性质都最优的互连网络，超立方体的有些变型还有许多比超立方体更好的性质，其中交叉立方体已经引起了国际上许多研究者的研究兴趣，它已被证明在直径、hamilton性质、模拟树和圈等方面的能力都比超立方体强。当然，交叉立方体也有一些比超立方体差的性质，如交叉立方体不像超立方体那样是边对称的。超立方体和交叉立方体相比都既有优点也有缺点，我们希望一个网络既能具备超立方体的优点，又能具备交叉立方体的优点，使多个基本目标得到改进。针对这一问题，本文将给出在超立方体与交叉立方体的顶点之间的一种连接——超连接，从而得到一种称为HCH-立方体的新型网络，并对这种网络的以下性质进行了研究：直径、最小顶点度数、顶点连通度、边连通度、圈嵌入、hamilton连通性以及比较模型下的可诊断性。本文首先证明了当1≤n≤3时，n维HCH-立方体互连网络的直径为n，当n≥4时，直径为[n／2]+2，即其直径仅仅比交叉立方体的直径至多大2(n维交叉立方体的直径为[(n+1)／2])，从而证明HCH-立方体的直径比超立方体小大约一半;然后证明了n维HCH-立方体互连网络的最小顶点度数和顶点连通度和边连通度为n，保持了超立方体和交叉立方体的最高连通度的优点;接下来证明了当n≥2且n≠3时，HCH中存在长度为l的圈(其中4≤l≤2)，克服了超立方体在对圈的模拟能力方面的不足，并给出了求n维HCH-立方体中长度为l的圈的算法，该算法的时间复杂摘要度为O(l);本文还证明了当n之4时，HCH一立方体任意两个顶点之间存在Hamllton 路径，即HCH一立方体是hamilton连通的，而超立方体不是hamilton连通的，这表明HCH一立方体具备了父叉立方体在hamilton连通性方面的性质。本文还给出了在n 维HCH一立方体中构造任意两个顶点之间hamilton路径的算法，该算法的时间复杂度为O(N)，其中N=2n，为n维HCH一立方体的顶点个数;最后证明了，当n之4时， n维HCH一立方体互连网络在比较模型下的可诊断性为n，与超立方体和交叉立方体在比较模型下的可诊断性相同。另外，由于这种网络同时包含了超立方体和交叉立方体作为子网络，因此它也同时具有低维超立方体和交叉立方体的性能。

关键词：互连网络超立方体交叉立方体 HCH-立方体直径最小顶点度数顶点连通度边连通度圈嵌入 hamilton连通性比较模型可诊断性算法时间复杂度

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

无爪图的hamilton性

无爪图的Hamilton性

作者：石开欣华东师范大学

学位级别：硕士

本文主要研究无爪图在不同子图的度和条件下的路圈性质,hamilton圈以及hamilton连通性),得出了无爪图有hamilton圈和hamilton路的三个充分条件.第一章我们介绍了图论中hamilton问题的研究背景和无爪图有hamilton圈和hamilton路的现有结... 详细信息

本文主要研究无爪图在不同子图的度和条件下的路圈性质,hamilton圈以及hamilton连通性),得出了无爪图有hamilton圈和hamilton路的三个充分条件.第一章我们介绍了图论中hamilton问题的研究背景和无爪图有hamilton圈和hamilton路的现有结果,以及本文中所需用到的的一些基本概念和符号术语.第二章主要讨论无爪图中任意两个不相邻子图在度和条件下的hamilton圈性质,得到了如下结果:定理2.1设G是n阶3-连通无爪图,如果G中任意两个分别同构于P和K的不相邻子图H和H的度和d(H)+d(H)≥n-2,则G有hamilton圈.定理2.2设G是n阶3-连通无爪图(n>12),如果G中任意两个分别同构于P和K的不相邻子图H和H的度和d(H)+d(H)≥n-3,则G有hamilton圈.第三章主要研究无爪图在度和条件下的hamilton连通性质,得到了如下结果:定理3.3设G是n阶3-连通无爪图,δ(G)≥4,如果G中任意两个分别同构于P和K的不相邻子图H和H的度和d(H)+d(H)≥n-1,则G是hamilton连通的.

关键词：无爪图不相邻子图子图的度 hamilton圈 hamilton连通性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

特殊图类路圈性质的子图度型充分条件研究

特殊图类路圈性质的子图度型充分条件研究

作者：米晶山东师范大学

学位级别：硕士

在图论中,路和圈是图的两种基本结构,是分析和刻画图的常用工具,而且在实际生活中,有很多实际问题可以归结为图的路和圈问题(例如我们经常见到的一笔画游戏),所以这一问题一直是图论中重要的热点问题.图论中的hamilton问题本质上也是图... 详细信息

在图论中,路和圈是图的两种基本结构,是分析和刻画图的常用工具,而且在实际生活中,有很多实际问题可以归结为图的路和圈问题(例如我们经常见到的一笔画游戏),所以这一问题一直是图论中重要的热点问题.图论中的hamilton问题本质上也是图的路和圈问题,它和四色问题还有并称图论的三大著名难题.国内外诸多学者在这方面做了大量的研究工作,其研究成果和进展可参见文献[29]-[37].经过几十年的研究和发展,图的路圈性质所涉及的内容日益丰富和具体.其中路方面包括图的hamilton路(可迹性),齐次可迹性,最长路,hamilton连通,泛连通,路可扩等等;圈的方面包括hamilton圈,Dominating圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等.然而直接研究一般圈的hamilton问题往往比较困难,所以人们常常转而研究某些特殊图类,例如不含某些禁用子图的图类.其中度型条件、邻域和条件以及邻域并条件成为研究路和圈问题的重要途径.继1970年Beineke发表的关于线图性质的文章[27]-[28]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,对于无爪图的的研究进入了一个活跃时期,关于无爪图方面的部分优秀成果可参考文献[11]-[26].另外,无爪图的概念也被从不同角度推广到了更大的图类,如半无爪图,几乎无爪图等.本文主要对图的度型条件(即任意两个不相邻子图的度和)与路圈性质(包括hamilton连通,可迹性及hamilton圈等)之间的关系进行了一些探索研究,得出无爪图以及半无爪图的路圈性质的几个充分条件.在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.在第二章中,我们主要研究了无爪图及半无爪图在不同度型条件下的Hamil-ton性,得到下面的结果：定理2.1.7设G是n阶2-连通无爪图,如果G中任意两个分别同构于P3和K1的不相邻子图H1,H2的度和d(H1)+d(H2)≥n,则G有hamilton圈.推论2.1.8设G是n阶2-连通无爪图,如果G中任意两个分别同构于K3和K1的不相邻子图H1,H2的度和d(H1)+d(H2)≥n,则G有Hamiltion圈.定理2.2.1设G是n阶2-连通半无爪图,如果G中任意两个分别同构于K2和K2的不相邻导出子图H1,H2的度和d(H1)+d(H2)≥n,则G有hamilton圈.推论2.2.3设G是n阶2-连通半无爪图,如果G中任意两个同构于K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n,则G有Hamiltion圈.定理2.3.2设G是n阶3-连通无爪图,如果G中任意两个分别同构于K3和K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-3,则G有hamilton圈.推论2.3.3设G是n阶3-连通无爪图,如果G中任意两个分别同构于P3和K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-3,则G有Hamiltion圈.推论2.3.4设G是n阶3-连通无爪图,如果G中任意两个分别同构于K3和K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-3,则G有Hamiltion圈.推论2.3.5设G是n阶3-连通无爪图,如果G中任意两个分别同构于K3和K1的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-3,则G有Hamiltion圈.推论2.3.6设G是n阶3-连通无爪图,如果G中任意两个分别同构于P3和K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-3,则G有Hamiltion圈.在第三章中,讨论了无爪图在不同度型条件下的hamilton连通性,得到下面的结果：定理3.1.1设G是n阶2-连通无爪图,δ(G)≥3,如果G中任意两个同构于K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-1,则对于G中的任意两点u,v,若{u,v}不构成割集,则u,v间存在hamilton路.推论3.1.2设G是n阶3-连通无爪图,如果G中任意两个同构于K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-1,则G是Hamiltion连通的.推论3.1.3设G是n阶2-连通无爪图,δ(G)≥3,如果G中任意两个分别同构于K2和K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-1,则对于G中的任意两点u,v,若{u,v}不构成割集,则u,v间存在hamilton路.推论3.1.4设G是n阶2-连通无爪图,δ(G)≥3,如果G中任意两个同构于K2的不相邻子图H1,H2的度和d(H1)+d(H2)≥n-1,则对于G中的任意两点u,v

关键词：无爪图半无爪图子图的度 hamilton连通性可迹性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

特殊图类中子图的度和与路圈性质

特殊图类中子图的度和与路圈性质

作者：徐珊珊山东师范大学

学位级别：硕士

在图论中,我们研究的一个十分重要而且非常活跃的课题为图的路和圈的问题,而实际生活中的很多问题都可以归结为图的路和圈问题.图论中的hamilton问题本质上也是图的路和圈问题,它是图论中的三大著名疑难问题之一.国内外许多学者在这一... 详细信息

在图论中,我们研究的一个十分重要而且非常活跃的课题为图的路和圈的问题,而实际生活中的很多问题都可以归结为图的路和圈问题.图论中的hamilton问题本质上也是图的路和圈问题,它是图论中的三大著名疑难问题之一.国内外许多学者在这一方面作了大量的研究工作.这方面的研究成果和进展可参见文献[31]-[35].其中度条件、邻域和条件以及邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果.经过几十年的研究和发展,图的路圈性质所涉及的内容日益丰富和具体.其中路方面包括图的hamilton路（可迹性）,齐次可迹性,最长路,hamilton连通,泛连通,路可扩等等;圈的方面包括图的hamilton圈,Dominating圈,最长圈,（点）泛圈,完全圈可扩,点不交的圈,圈覆盖等等. 由于图的hamilton问题是一个疑难问题,所以在一般图中研究hamilton问题会更加困难,于是人们转而研究不含有某些禁用子图的图类,如无爪图.继Beineke1970年发表的关于线图性质的文章[29]-[30]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[13]-[28]另外,无爪图的概念也被从不同角度推广到了更大的图类,如半无爪图,几乎无爪图等. 本文主要对图的度条件（任意两个不相邻子图的度和）与路圈性质（包括hamilton连通,可迹性及Hamilron圈等）之间的关系进行了一些探索,得出了一般图及无爪图的路圈性质的几个充分条件. 在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果. 在第二章中,我们主要研究了一般图及无爪图在不同度条件下的路圈性质,得到下面的结果：定理2.1.3设G是n阶2-连通图,如果G中任意两个同构于K2（2阶完全图）的不相邻子图H1,H2的度和d（H1）+d（H2）≥n—2,则G有Dominating圈. 推论2.1.4设G是n阶2-连通图,如果对G中任意一个同构于K2的子图H,有d（H）≥n-2/2,则G有Dominating圈. 定理2.2.4设G是n阶2-连通无爪图,如果G中任意两个分别同构于P3与K2（2阶完全图）的不相邻子图H1,H2满足d（H1）+d（H2）≥n—2,则G有hamilton圈. 定理2.3.1设G是n阶3-连通无爪图,如果G中任意两个分别同构于K3（3阶完全图）与K1的不相邻子图H1,H2满足d（H1）+(d（H2）≥n—3,则G有hamilton圈. 在第三章中,讨论了无爪图在度条件下的hamilton连通性质,得到下面的结果：定理3.5设G是n阶3-连通无爪图,如果G中任意两个分别同构于P3与K1的不相邻子图H1,H2满足d（H1）+d（H2）≥n,则G是hamilton连通的. 在第四章中,讨论了半无爪图在度条件下的可迹性,得到下面的结果：定理4.4设图G是n阶2-连通半无爪图,如果G中任意两个同构于K3和K1的不相邻导出子图H1,H2的度之和d（H1）+d（H2）≥n—1,则G是可迹的.

关键词：无爪图半无爪图子图的度 hamilton圈 Dominating圈 hamilton连通性可迹性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

子图的度与若干图类的路圈问题

子图的度与若干图类的路圈问题

作者：马修山山东师范大学

学位级别：硕士

路和圈的问题一直是图论中的热点研究领域.路和圈是图的两种基本结构,是分析刻画图的有力工具.有关这方面的研究成果和进展可参见文献[34]-[38]事实上,图论中的三大著名难题之一的Hamiltom问题本质上也是图的路和圈问题.经过几十年的发... 详细信息

路和圈的问题一直是图论中的热点研究领域.路和圈是图的两种基本结构,是分析刻画图的有力工具.有关这方面的研究成果和进展可参见文献[34]-[38]事实上,图论中的三大著名难题之一的Hamiltom问题本质上也是图的路和圈问题.经过几十年的发展,路圈性质所涉及的内容也日益丰富.路的方面包括可迹性,最长路,hamilton连通,泛连通,路可扩等等;圈的方面包括Hamiltom圈,Dominating圈,最长圈,点泛圈,完全圈可扩,圈覆盖等等. 由于直接研究一般图的Hamilon问题往往比较困难,于是人们转而研究不含某些禁用子图的图类.继Beinekel968.1970年发表的关于线图性质的两篇文章[17]-[18]之后,人们开始关注包含线图的五爪图.70年代末80年代初是研究无爪图的一个非常活跃的时期.关于无爪图的部分优秀成果可参见[2]-[4],[19]-[34]. 无爪图的概念也被推广到了更大的图类,如半无爪图,几乎无爪图等等.其中半无爪图的某些研究进展可参见[35]-[37]. 本文主要对子图的度条件(任意两个不相邻子图的度和)与路圈性质(包括可迹性,Hamilron圈,Hamilon连通等)之间的关系进行了一些探索,得出了无爪图及半无爪图的路圈性质的几个充分条件. 在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果. 在第二章中,我们主要研究了无爪图在不同子图的度条件下的路圈性质,得到下面的结果：定理2.1.3设图G是n阶连通无爪图,如果G中任意同构于K1,P3的不相邻导出子图H1,H2的度之和d(H1)+(H2)≥n-2,则G是可迹的. 定理2.2.6设G是n阶2-连通无爪图,如果G中任意两个同构于K2(2阶完全图)的不相邻子图H1,H2满足D(H1)+(H2)≥n-2,则G有hamilton圈. 推论2.2.7设图G是n阶2-连通无爪图,如果δ(G:K2)≥n/2-1,则G有Harmilton圈. 定理2.3.3设G是n阶3-连通无爪图,如果G中任意两个同构于K2(2阶完全图)的不相邻子图H1,H2满足d(H1)+d(H2)≥n;则G是hamilton连通的. 推论2.3.4设G是n阶3-连通无爪图,如果G中任意两个同构于K2(2阶完全图)的不相邻子图H1,H2满足δ(G:K2)≥n/2,则G是Hanilton连通的. 定理2.4设G是n阶4-连通无爪图,如果G中任意同构于K3和同构于K2的不相邻子图H1,H2的度之和d(H1)+d(H2)≥n,则G中任意两点之间都存在控制路. 在第三章中,我们讨论了半无爪图在子图的度条件下的可迹性,得到下面的结果：定理3.4设G是n阶2-连通半无爪图,如果G中任意两个同构于K2(2阶完全图)的不相邻子图H1,H2满足d(H1)+d(H2)≥n-1,则G是可迹的. 推论3.5设G是n阶2-连通半无爪图,如果G中任意两个同构于K2(2阶完全图)的不相邻子图H1,H2满足δ(G:K2)≥n-1/2,则G是可迹的.

关键词：无爪图半无爪图子图的度可迹性 hamilton圈 hamilton连通性控制路

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

交叉立方体圈嵌入的一个新算法(英文)

青岛大学学报（自然科学版） 2002年第1期15卷 19-25页

作者：樊建席王庆红刘昕晁岳壮青岛大学信息工程学院潍坊学院计算机科学系潍坊261043 山东松下映像产业有限公司

交叉立方体互联网络有不少独特的性质。已经证明当3n时n维交叉立方体nD是hamilton连通的,一个将长度)24(,nll的圈以扩张1嵌入nD的)log(llO算法。本文利用交叉立方体的hamilton连通性给出了一个将长度nll24,的圈以扩张1嵌入nD的新的算法... 详细信息

交叉立方体互联网络有不少独特的性质。已经证明当3n时n维交叉立方体nD是hamilton连通的,一个将长度)24(,nll的圈以扩张1嵌入nD的)log(llO算法。本文利用交叉立方体的hamilton连通性给出了一个将长度nll24,的圈以扩张1嵌入nD的新的算法也被给出,其时间复杂度为)(lO。

关键词：互连网络交叉立方体超立方体 hamilton连通性扩张圈嵌入时间复杂度