检索结果-南通市图书馆

2-连通K1,4-free图中特型支撑树的存在性研究

在线全文

学校读者我要写书评

暂无评论

2-连通K1,4-free图中特型支撑树的存在性研究

作者：侯黎华中师范大学

学位级别：硕士

图中特型支撑树的存在性问题一直是结构图论研究中的一个重要课题.该问题的产生和发展与图论中的哈密顿问题有着密切联系.判断一个图是否存在一条哈密顿路,亦可看成判断该图中是否存在至多两个叶子点的支撑树.那么就出现了一个自然的问... 详细信息

图中特型支撑树的存在性问题一直是结构图论研究中的一个重要课题.该问题的产生和发展与图论中的哈密顿问题有着密切联系.判断一个图是否存在一条哈密顿路,亦可看成判断该图中是否存在至多两个叶子点的支撑树.那么就出现了一个自然的问题:对于任意正整数k≥ 2,在什么条件下,图G中存在至多k个叶子点的支撑树.Kyaw在文献[12]中,从度和的角度出发给出了在连通K1,4-free图中存在叶子点数至多为k的支撑树的一个充分条件,即:对任意正整数k≥ 3,如果G是连通K1,4-free图,并且σk+1（G）≥ |G|-k/2,那么图G中存在一个叶子点数至多为k的支撑树.虽然该结果是最好可能的,但其极图的连通度为1.于是产生一个自然的问题:是否存在整数a ≥ 2及b使得所有满足σk+a（G）≥|G|+b的2-连通K1,4-free图都含有至多k个叶子点的支撑树?Chen等人在文献[6]中给出了k-连通K1,4-free图中存在叶子点数至多为3的支撑树的一个充分条件:设图G是k-连通K1,4-free图,其中k≥2.如果σk+3（G）≥ |G|+2k-2,则G中存在叶子点数至多为3的支撑树.本文对k=2的情况进行了更进一步的研究,利用6个点的独立集的度和,得到了 2-连通K1,4-free图中存在叶子点数至多为3的支撑树的一个充分条件.全文一共分为四章,主要内容如下:在本文第一章,我们介绍了图的支撑树问题的研究背景,研究意义以及现有的国内外研究成果,并且介绍了本文的主要结论.在本文第二章,我们给出了文中出现的一些基本概念,基本定义,以及符号.在本文第三章,我们利用反证法给出了本文主要定理的证明.通过适当地选取2-连通K1,4-free图中恰含四个叶子点的最大树,我们将定理的证明分为四种情形.对每种情形选取适当的6点独立集,并估计其中点的度和,分别得到矛盾.在本文第四章,我们对图中支撑树存在性问题的进一步研究进行了展望.

关键词：支撑树度和 K1,4-free 2-连通

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

关于2-连通图可迹性的两个充分条件

关于2-连通图可迹性的两个充分条件

作者：邱小波华中师范大学

学位级别：硕士

图的可迹性一直是结构图论的一个非常重要的研究课题.众所周知,哈密尔顿路可以看成一个不含任何分支点的支撑树,也可看成至多含两个悬挂点的支撑树.因此判断一个图的哈密尔顿路是否存在,可转化成判断图中是否含至多两个悬挂点的支撑树.... 详细信息

图的可迹性一直是结构图论的一个非常重要的研究课题.众所周知,哈密尔顿路可以看成一个不含任何分支点的支撑树,也可看成至多含两个悬挂点的支撑树.因此判断一个图的哈密尔顿路是否存在,可转化成判断图中是否含至多两个悬挂点的支撑树.则存在一个很自然的问题:能否利用图中含3个悬挂点的最大树研究图的可迹性?本文对此进行了初步探讨.全文共分为四章,主要内容如下:在本文第一章,我们介绍了文中出现的一些基本概念、定义、符号以及关于支撑树问题的研究背景、意义和国内外现有的研究成果,同时提出了本文的主要结论.在本文第二章,我们研究2-连通K-free图中哈密尔顿路的存在性,Kyaw[21]利用3个不相邻点的度和得到连通的K-free图可迹的下述充分条件:若连通图G是K-free的,且σ(G)≥ |G|,则G中存在哈密尔顿路.尽管这个结果中关于σ的下界是最好可能,但其极图的连通度是1.由此产生下述问题:是否存在整数b ≥ 2使得对某个常数c,所有满足σ(G)≥ |G|+c的2-连通K-free图G都含有哈密尔顿路?在本章,我们用反证法,利用图G中恰含三个悬挂点的最大树证明了该问题对b=3的答案是肯定的,即所有满足σ(G)≥ |G|+3的2-连通K-free图G都含有哈密尔顿路.在本文第三章,我们研究2-连通K-free图中哈密尔顿路的存在性,Chvátal和Erd?s[3]得到图的连通度和独立数与其可迹性之间的联系:设图G的连通度至少为k,如果α(G)≤k+1,那么G中存在哈密尔顿路.一个自然的问题是:是否存在常数c使得所有满足σ(G)≥ |G|+c的k-连通图G都是可迹图?由完全二部图K(m≥k)知该问题的答案是否定的.在本章,我们证明对2-连通K-free图,该问题的答案为真:设G是2-连通K-free图,如果σ(G)≥|G|+3,那么G中存在哈密尔顿路,并且条件中关于σ(G)的下界是最好可能的.在本文第四章,我们对2-连通K-free图中特型支撑树的存在性问题进行了进一步展望.

关键词：支撑树哈密尔顿路度和 K1,4-free K1,5-free 2-连通

2-连通T_3-受限图的Hamilton性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

山东师范大学学报（自然科学版） 2007年第1期22卷 8-9页

作者：石玉华王玉丽山东师范大学数学科学学院济南250014 济南大学理学院济南250022

部分K1,3的一条边所得到的图记为T3,其中的3度顶点称为T3的中心.如果图G的任意一个同构于T3的导出子图,除中心以外的4个顶点之间的边数≥3,则称G为T3-受限图.本文主要证明:如果GF′,2-连通T3-受限图G含有Hamilton图.

关键词： T3-受限图 2-连通 Hamilton圈

在线全文

学校读者我要写书评

暂无评论

2-连通无爪图的Hamilton性

沈阳航空工业学院学报 2005年第3期22卷 83-85页

作者：闻良辰沈阳航空工业学院理学系辽宁沈阳110034

Hamilton问题是图论中重要的问题之一,已经得到了很多很好的结果,但一个图是Ham-ilton图的充分必要条件到现在还没有得出,文章应用幅度的概念,使用反证法,通过构造最长圈并得出矛盾的方法,给出了2-连通无爪图,若θ(G)21(n-δ-2)时,G为Ha... 详细信息

Hamilton问题是图论中重要的问题之一,已经得到了很多很好的结果,但一个图是Ham-ilton图的充分必要条件到现在还没有得出,文章应用幅度的概念,使用反证法,通过构造最长圈并得出矛盾的方法,给出了2-连通无爪图,若θ(G)21(n-δ-2)时,G为Hamilton图这一充分条件,为进一步讨论Hamilton提供了一种新的思路。

关键词： 2-连通无爪图周长幅度 Hamilton

在线全文

学校读者我要写书评

暂无评论

基圈数为5的2-连通平图的构造

Journal of Mathematical Study 2004年第1期37卷 83-95页

作者：杨维玲金贤安厦门大学数学系厦门大学数学系福建厦门361005

所有的 2 -连通平图可通过收缩 2度点变换成无 2度点的、基圈数不变的 2 -连通平图 .本文给出了基圈数为 5的、无 2度点的所有 2 -连通平图

关键词： 2-连通平图收缩基圈数

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

四维光滑Poincaré猜测

科学通报 2017年第33期62卷 3807-3810页

作者：邓少雄朱熹平中山大学数学学院广州510275

首先讨论更为熟悉的三维Poincaré猜测,它的解是现代几何分析的一个主要成果,这启发了本文中给出的光滑四维Poincaré猜测的精确陈述.然后解释流形上的拓扑结构与光滑结构之间的差异以及Donaldson利用Yang-Mills方程瞬子解定义四维流形... 详细信息

首先讨论更为熟悉的三维Poincaré猜测,它的解是现代几何分析的一个主要成果,这启发了本文中给出的光滑四维Poincaré猜测的精确陈述.然后解释流形上的拓扑结构与光滑结构之间的差异以及Donaldson利用Yang-Mills方程瞬子解定义四维流形微分不变量的开创性工作.最后,给出了尝试解决该猜想的一些新方法.

关键词： 2-连通微分同胚标准四维球面 Ricci流微分不变量

在线全文

学校读者我要写书评

暂无评论

泛圈图的一个充分条件

武汉理工大学学报（交通科学与工程版） 2004年第4期28卷 583-584,617页

作者：桂预风李刚王彬武汉理工大学理学院武汉430063

哈密顿图和泛圈图的充分条件是图论中的重要理论问题之一 ,文中讨论了基于禁用子图的泛圈图的一些充分条件 ,给出了泛圈图的一个新的充分条件 :设 G是 2 -连通 ,{K1 ,3,P5,P+ 5}-free的 n阶图 ,则 G是泛圈图或圈 .

关键词：泛圈图禁用子图 2-连通

关于连通中心数与连通控制数参量下图的平均距离与极值图的刻画

在线全文

学校读者我要写书评

暂无评论

关于连通中心数与连通控制数参量下图的平均距离与极值图的刻画

作者：高晓璐兰州大学

学位级别：硕士

设G是连通图,顶点集为V(G),边集为E(G),S是G的一个顶点子集.若S’外的任意一对不相邻的点都可由一条内点都在S中的路相连,则我们称S是G的一个中心集.进一步地,若S导出的子图是连通的,就称其为连通中心集.最小中心集的阶称为中心数,记为h... 详细信息

设G是连通图,顶点集为V(G),边集为E(G),S是G的一个顶点子集.若S’外的任意一对不相邻的点都可由一条内点都在S中的路相连,则我们称S是G的一个中心集.进一步地,若S导出的子图是连通的,就称其为连通中心集.最小中心集的阶称为中心数,记为h(G);最小连通中心集的阶称为连通中心数,记为hc(G).若S外的任一点都与S中的某个点相邻,且S导出的子图是连通的,则我们称S是G的一个连通控制集.类似地,定义连通控制数γ(G).图G的直径用d(G)表示.本文完成了不等式h(C)≥d(G) - 1取等号时对应极值图的刻画.其次,根据参量h(G)与γ(G)之间的联系:hc(G) ≤ γ(G)≤h(G) + 1,我们将图分为两类,并按这种分类方式分别给出图G关于h(G)的平均距离的上界以及相应极值图的刻画.作为推论,我们对一般的给定顶点数的连通图G分别给出了其关于h(G)与γ(G)的平均距离的上界.进一步地,本文又将图G限制为2-连通图,并得到结论:2-连通的边极小图的最小连通控制集导出的子图一定是树.特殊地,当限制γ(G) = 2时,我们给出了 2-连通图G的平均距离的上界,并刻画了相应极值图.

关键词：平均距离 2-连通连通中心数连通控制数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

均衡路径覆盖和连通子图划分问题

均衡路径覆盖和连通子图划分问题

作者：姚会影杭州电子科技大学

学位级别：硕士

本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容... 详细信息

本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容如下。第一章介绍了图论、计算复杂性和近似算法的一些基础知识,并阐述了{1,2}-边赋权完全图上最小最大k-路径（圈）覆盖问题和连通图上的均衡k-连通划分问题的研究现状。第二章研究了{1,2}-边赋权完全图上最小最大k-路径覆盖与k-圈覆盖问题。利用经典NP-哈密顿路问题和哈密顿圈问题进行多项式时间归约,证明了两个问题均是NP-难的。对最小最大2-路径覆盖问题,基于旅行售货商问题的一个近似算法,提出了一个近似比不超过11/7的算法,并给出了一个算例;然后将此算法推广到了一般最小最大k-路径覆盖问题,证明了算法的近似比不超过24/7-2/k。对于最小最大k-圈覆盖问题,基于上述最小最大k-路径覆盖问题算法,得到了一个近似比不超过19/7-1/k的算法。第三章研究了2-连通图上的均衡2-连通划分问题,基于局部搜索技术,提出了一个近似比不超过6/5的算法。第四章对全文的内容进行了总结,并对未来的研究方向给出了相关分析和展望。

关键词：路径覆盖圈覆盖图划分诱导子图 2-连通近似算法 NP-难