检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

重爪图中哈密尔顿圈存在性的禁止子图条件

纺织高校基础科学学报 2010年第4期23卷 476-479页

作者：王莹西北工业大学应用数学系陕西西安710129

利用禁止子图给出了2-连通重爪图中哈密尔顿圈存在性的充分条件,并得到了2个结果:(1)G是一个含有n≥3个顶点的2-连通图,如果G是2-重图,并且是无Z2图,则G是一个哈密尔顿图.(2)G是一个含有n≥3个顶点的2-连通图,如果G是重爪图,并且是无Z2... 详细信息

利用禁止子图给出了2-连通重爪图中哈密尔顿圈存在性的充分条件,并得到了2个结果:(1)G是一个含有n≥3个顶点的2-连通图,如果G是2-重图,并且是无Z2图,则G是一个哈密尔顿图.(2)G是一个含有n≥3个顶点的2-连通图,如果G是重爪图,并且是无Z2图,则G是一个哈密尔顿图.这2个结果改进了1982年Gould和Jacobson给出的2-连通无爪图中哈密尔顿圈存在性的充分条件.

关键词：禁止子图哈密尔顿圈重爪

在线全文

学校读者我要写书评

暂无评论

一类路图的哈密尔顿圈

重庆建筑工程学院学报 1991年第3期13卷 1-6页

作者：张建高重庆建筑工程学院建管系

设G是一个图,我们用Π_k(G)表示G中所有具有k个顶点的路P_k所成之集。图G的路图P_k(G)有顶点集Π_k(G),且P_k(G)中的两个顶点相邻表示两条路P_k的并形成G中的一条路P_(k+1)或一个圈C_k。***和***研究了路图的一些性质,并提出了两个猜想... 详细信息

设G是一个图,我们用Π_k(G)表示G中所有具有k个顶点的路P_k所成之集。图G的路图P_k(G)有顶点集Π_k(G),且P_k(G)中的两个顶点相邻表示两条路P_k的并形成G中的一条路P_(k+1)或一个圈C_k。***和***研究了路图的一些性质,并提出了两个猜想:1)若T是一颗树,△(T)≥4,则P_3(T)不是哈密尔顿图;2)若G是唯一圈图,△(G)≥5,则G不是哈密尔顿图。在本文中,我们证明了这两个猜想是对的。

关键词：哈密尔顿圈路图图论

在线全文

学校读者我要写书评

暂无评论

关于无爪图中哈密尔顿圈的一个注记(英文)

西南大学学报（自然科学版） 2011年第2期33卷 110-112页

作者：李盛瑜李霄民重庆工商大学计算机科学与信息工程学院重庆400067 重庆工商大学数学与统计学院重庆400067

证明了具有Hourglass和Dumbbell性质的3-连通的无爪图是哈密尔顿圈.

关键词：哈密尔顿圈 3-连通无爪图线图

在线全文

学校读者我要写书评

暂无评论

平衡多部无向图存在哈密尔顿圈的度条件

平衡多部无向图存在哈密尔顿圈的度条件

作者：周芷伊山西大学

学位级别：硕士

无向图的哈密尔顿圈问题,是一个有着古老历史的图论问题.但是到目前为止,还没有得到无向图存在哈密尔顿圈的充分必要条件.关于它的研究主要集中于找存在哈密尔顿圈的充分条件,而充分条件中侧重于度条件.许多学者已经研究了一般无向图存... 详细信息

无向图的哈密尔顿圈问题,是一个有着古老历史的图论问题.但是到目前为止,还没有得到无向图存在哈密尔顿圈的充分必要条件.关于它的研究主要集中于找存在哈密尔顿圈的充分条件,而充分条件中侧重于度条件.许多学者已经研究了一般无向图存在哈密尔顿圈的度条件,特别地,Fan-型条件是无向图存在哈密尔顿圈的一类重要的度条件.近几年来,关于平衡二部无向图中存在哈密尔顿圈的Fan-型条件引起了许多学者的关注,但是仍然很不完善.本文主要研究了平衡二部无向图存在哈密尔顿圈的Fan-型条件,讨论了该条件下的偶泛圈性,经过每一个完美匹配的哈密尔顿圈的存在性,以及平衡k部无向图存在哈密尔顿圈的度和条件.本文共分为三章.第一章介绍了本文涉及到的基本概念,并给出了所研究问题的研究现状.第二章研究了平衡二部无向图存在哈密尔顿圈的度条件.在1996年,高太平和杨爱民在阶为2n的平衡二部无向图中引进了 Fan-型条件,并且证明了任意两个距离为2的顶点x,y满足max{d(x),d(y)}≥n/2+1时平衡二部无向图是哈密尔顿的.在2018年,王淼和刘岩将上述定理的下界改进为n+1/2.在本章中,我们首先将刻画上述条件的极图并且证明了除六类例外图是哈密尔顿的.其次证明了在上述条件下除了一类例外图是偶泛圈的.由这两个结论我们还可以推出对于阶为2n的平衡二部无向图中任意两个距离为2的顶点x,y满足d(x)+d(y)=n时,除三个特殊图外,平衡二部无向图是哈密尔顿的.对于阶为2n的平衡二部无向图中任意两个距离为2的顶点x,y满足d(x)+d(y)≥n+1时,除一个例外图,平衡二部无向图是偶泛圈的.在2018年,王淼和刘岩证明了阶为2n的平衡二部无向图中任意两个距离为2的顶点x,y满足max{d(x),d(y)}≥n时包含经过每一个完美匹配的哈密尔顿圈.在本章中我们将证明对于平衡二部无向图中任意两个距离为2的顶点x,y满足d(x)+d(y)≥n+2时包含经过每一个完美匹配的哈密尔顿圈.第三章研究了平衡k部无向图存在哈密尔顿圈的不同部集的任意两个不相邻顶点的度和条件.在1997年,陈冠涛等研究了阶为n的平衡k部无向图存在哈密尔顿圈的度和条件,得到了不同部集的任意两个不相邻顶点u和v满足条件d(u)+d(v)>2(n+2+n/2[k+1/2]-n/k)时平衡k部无向图是哈密尔顿的.在本章中,我们将对n等于奇数时对上述度和条件的下界进行改进,改进为d(u)+d(v)≥2([n/2]+[n+2/2k+1/2]-n/k).

关键词：无向图平衡二部无向图平衡k部无向图哈密尔顿圈度条件

Johnson图的连通度、割集和哈密尔顿圈

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Johnson图的连通度、割集和哈密尔顿圈

作者：宁万涛兰州大学

学位级别：硕士

Johnson图J(n，k)的定义如下：设n，k是固定的正整数且满足n≥k，Ω是大小为n的固定的集合，那么J(n，k)的顶点集由Ω的所有k元子集组成，两个顶点相邻当且仅当这两个顶点对应的k元子集的交的大小为k-1．对于图G的一个顶点v，v的一个局... 详细信息

Johnson图J(n，k)的定义如下：设n，k是固定的正整数且满足n≥k，Ω是大小为n的固定的集合，那么J(n，k)的顶点集由Ω的所有k元子集组成，两个顶点相邻当且仅当这两个顶点对应的k元子集的交的大小为k-1．对于图G的一个顶点v，v的一个局部割是由v的邻点x或者边vx构成的大小为d(v)的集合。对于图G，设W(?)(V(G)∪E(G))，当G-W不连通或者只有一个顶点时，W就定义为图G的一个广义割;当G-W的直径大于图G的直径时，W就定义为图G的一个直径增长集．Daven和Rodger在1999年证明了J(n，k)的连通度是k(n-k)，在本文中，首先我们用更简单的方法证明了同样的结果．接着我们论证了当n≠4且k≠2时，J(n，k)的每一个最小广义割都是某个顶点的一个局部割;当k≠2时，或者n≠6且k≠3时，J(n，k)的每一个最小的直径增长集是某个顶点的一个局部割的子集．最后我们得到了当n≥3时，J(n，k)有—个哈密尔顿圈．

关键词： Johnson图连通度广义割直径哈密尔顿圈

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

稠密有向图上哈密尔顿圈计数问题的改进算法

稠密有向图上哈密尔顿圈计数问题的改进算法

作者：张金山清华大学

学位级别：硕士

本文给出一个计算有向图上哈密尔顿圈个数的改进算法,该算法的基本思想是分步接受/拒绝。分步接受/拒绝方法已经成功地应用于渐进计算稠密图上完美匹配的个数。在本文中,我们利用1-因子数与哈密尔顿圈数的比率给出有向图上哈密尔顿圈个... 详细信息

本文给出一个计算有向图上哈密尔顿圈个数的改进算法,该算法的基本思想是分步接受/拒绝。分步接受/拒绝方法已经成功地应用于渐进计算稠密图上完美匹配的个数。在本文中,我们利用1-因子数与哈密尔顿圈数的比率给出有向图上哈密尔顿圈个数的一个新的上界。基于该上界,我们给出一个计算稠密图上哈密尔顿圈数的渐进算法(FPRAS),该算法给出.85n稠密图上哈密尔顿圈数的(ε,δ)渐进所期望运行的时间是O(n8.5)。这比目前存在的应用很广的马尔可夫链算法提高了至少n8.5(logn)4的运算时间。我们还将证明这类稠密图上的计数问题是不平凡的,确切地说是#P完全的。本文的创新点主要有:?将分步接受/拒绝方法用于计算哈密尔顿圈的个数;?给出稠密有向图上哈密尔顿圈个数的一个上界;?证明稠密有向图上计算哈密尔顿圈的个数是#P完全的。

关键词：哈密尔顿圈 1-因子计数 #P完全

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

平衡二部有向图存在哈密尔顿圈的几类度条件

平衡二部有向图存在哈密尔顿圈的几类度条件

作者：吴林鑫山西大学

学位级别：硕士

有向图在图论的研究中非常重要.而有向图的哈密尔顿圈问题及与其相关的很多问题,已经被广泛地研究了半个多世纪,并且取得了较为显著的成果.本文主要研究了平衡二部有向图在控制对度条件下存在哈密尔顿圈,在另外两类度和条件下存在哈密... 详细信息

有向图在图论的研究中非常重要.而有向图的哈密尔顿圈问题及与其相关的很多问题,已经被广泛地研究了半个多世纪,并且取得了较为显著的成果.本文主要研究了平衡二部有向图在控制对度条件下存在哈密尔顿圈,在另外两类度和条件下存在哈密尔顿圈的极图,以及在控制对和被控制对度条件下是几乎二泛圈的.本文共分为四章.第一章介绍了有向图的一些基本概念以及研究现状,并提出本论文的主要内容.第二章研究了平衡二部有向图存在哈密尔顿圈的控制对度条件.在2017年,王瑞霞给出了平衡二部有向图存在哈密尔顿圈的一个充分条件并提出下面的问题:对于一个阶为2a的强连通平衡二部有向图D.若D中任意一个控制对{x,y}都有d(x)≥ 2a-kc,d(y)≥ a+k 或者 d(x)≥ a+k,d(y)≥ 2a-kc,其中 2 ≤k≤a/2,那么D是否是哈密尔顿的?本章证明了如果上述问题中的k满足max{1,a/4}哈密尔顿的,即给出下面的定理:设D是一个阶为2a的强连通平衡二部有向图,其中a≥2.如果D中任意一个控制对{x,y}都有d(x)≥2a-k,d(y)≥ a+k或者d(x)≥a+k,d(y)≥2a-k,其中max{1,a/4}哈密尔顿的.第三章完全刻画了平衡二部有向图在同一部集顶点度和条件下以及在控制对和被控制对度条件下哈密尔顿圈的极图.在2014年,Adamus等给出了平衡二部有向图存在哈密尔顿圈的不相邻顶点度和的充分条件并说明这个条件的下界是紧的.在2017年,Adamus进而又给出了平衡二部有向图存在哈密尔顿圈的控制对和被控制对充分条件且说明该条件的下界是紧的.本章将上述的条件减弱1,完全刻画了在该条件下不存在哈密尔顿圈的5类极图,即给出了下面的定理:设D是一个阶为2a的强连通平衡二部有向图,其中a≥3.如果D中任意一个控制对和被控制对顶点{u,v}都有d(u)+(v)≥3a-1,则D或者是哈密尔顿的,或者同构于H1中的一个图,或者同构于H2,H3,H4或H5.第四章研究了平衡二部有向图在控制对和被控制对度条件下是几乎二泛圈的.在2018年,Adamus给出了平衡二部有向图存在二泛圈的Meyniel充分条件并提出了以下问题:设D是一个阶为2a的强连通平衡二部有向图,是否对每个1≤l圈.显然这个问题只需要对l=a-1进行证明.本章解决了这个问题,即证明了下面的定理:设D是一个阶为2a的强连通平衡二部有向图,其中a ≥4.如果D中任意一个控制对和被控制对顶点{u,v}都有d(u)+d(v)≥3a-1,则D或者包含长度为2,4,…,2a-2的圈,或者是长为2a的圈.

关键词：平衡二部有向图度条件哈密尔顿圈二泛圈极图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向图存在哈密尔顿圈的几类充分条件

有向图存在哈密尔顿圈的几类充分条件

作者：常静芳山西大学

学位级别：硕士

有向图是图论的一个重要分支,有向图的哈密尔顿性是图论的基本问题,在现实生活中有着非常广泛的应用.半个多世纪以来,人们对哈密尔顿问题进行了深入的研究且取得了很多重要的成果.本文主要对强连通有向图和平衡二部有向图的哈密尔顿性... 详细信息

有向图是图论的一个重要分支,有向图的哈密尔顿性是图论的基本问题,在现实生活中有着非常广泛的应用.半个多世纪以来,人们对哈密尔顿问题进行了深入的研究且取得了很多重要的成果.本文主要对强连通有向图和平衡二部有向图的哈密尔顿性进行研究.本文共分为四章.第一章介绍了本文涉及到的基本概念,并给出了所研究问题的研究现状.第二章研究了强连通有向图存在哈密尔顿圈的被控制对的度条件.1996年,Bang-Jensen,Gutin和Li提出猜想:设D是阶为n的强连通有向图,其中n ≥2.假设D中所有不相邻的被控制对{x,y}都满足d（x）+d（y）≥2n-1,则D是哈密尔顿的.在本章中,我们给出一个任意个顶点的反例图,证明这个猜想是错误的.其次也证明了即使将条件加强为d（x）≥2n-4,d（y）≥3或d（x）≥3,d（y）≥2n-4,这个猜想也是错误的.第三章研究了强连通有向图存在哈密尔顿圈的控制对和被控制对的度条件.Bang-Jensen,Gutin和Li提出猜想:设D是阶为n的强连通有向图,其中n ≥2.假设D中所有不相邻的控制对和被控制对{x,y}都满足d（x）+d（y）≥2n-1,则D是哈密尔顿的.这个猜想现在仍然是公开的.在本章中,我们进一步提出猜想:存在整数1 ≤k≤n-5,使得每个阶为n,对任意不相邻的控制对和被控制对{x,y}都满足条件d（x）≥n+k,d（y）≥ n-1-k或d（x）≥ n-1-k,d（y）≥ n+k的强连通有向图D是哈密尔顿的.我们证明了 k=n-5,n-6,n-7时是正确的,该结论也部分解决了以上Bang-Jensen,Gutin和Li的猜想.第四章研究了平衡二部有向图的哈密尔顿性.2012年,Adamus等人证明了定理:设D是阶为2a的平衡二部有向图,其中a ≥2.若D中属于不同部集的任意两个顶点u,v,当uv（?）A时满足d+（u）+d-（v）≥a+2,则D是哈密尔顿的.作者在文中也给出了一个阶为6的有向图证明其下界是紧的,但并未证明该有向图就是以上定理的极图.在本章中,我们将其下界降为a+1,证明了 D或者是哈密尔顿的或者与以上阶为6的有向图同构.由此,我们完全刻画了以上定理的极图.

关键词：有向图平衡二部有向图度条件哈密尔顿圈极图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

增广立方体中经过给定三条边的哈密尔顿圈

漳州职业技术学院学报 2015年第3期17卷 10-15页

作者：佘卫强漳州职业技术学院公共教学部福建漳州363000

用归纳假设法证明了结论:令AQn是增广立方体,当n≥2时,若EeE(AQn),1≤︱Ee︱≤3,这里Ee是线性森林(每个分支都是路),则在AQn中有哈密尔顿圈包含Ee的所有边.

关键词：增广立方体指定边哈密尔顿圈互连网络