共查询到19条相似文献,搜索用时 46 毫秒
1.
利用图的邻接矩阵与一种特殊矩阵置换相似的关系判别图中Hamilton圈(路)的存在情况。首先对于不完全图的无向图和有向图进行分析,给出不完全图和完全图存在Hamilton圈(路)的充分必要条件,然后得出了竞赛图寻找Hamilton圈(路)的简单方法。 相似文献
2.
唐德和 《江南大学学报(自然科学版)》1997,12(2):23-25
本文证明了如下结果:G是简单图满足条件:对G中任一对不相邻顶点,u,v有max(d(u),d(v))+/N(u)∪N(v)/≥n-1;且对任意T∈V(G),有ω(G/T)≤/T/,则G是Hamilton图。 相似文献
3.
本文的主要结果是:设G是D-圈图,若存在某个t≤δ,使得对任何t+1个点的独立集,X={x0,x1,…,xz),有,则G是Hamilton图。 相似文献
4.
5.
证明了当设G=(X,Y;E)是连通二部图,|X|=|Y|=n!5,且δ(G)≥2,若NC2≥n-1,则G是Hamilton图。 相似文献
6.
任韩 《北京交通大学学报(自然科学版)》1999,23(2):5
设G是2-连通图.如果对其任一3-独立集{x1,x2,x3},有xi(1≤i≤3)使得N(xi)与∪j≠iN(xj)至少有α(G)个公共元素,则Hamilton图.这里,α(G)是G的独立数. 相似文献
7.
王中兴 《广西大学学报(自然科学版)》1991,16(1):75-78
设G为n阶2-连通图,α为G的独立数.如果对于G中任意3个顶点的独立集{v_1,v_2,v_3}都有d(v_1)+d(v_2)+d(v_3)≥max{n+2,3α-2},则G是Hamilton-图。 相似文献
8.
9.
赵克文 《兰州理工大学学报》2004,30(2):123-125
在前人工作的基础上,创立进一步的新条件,得到结果:记δ为图G的最小度,若2连通n阶图G的距离为2的任意两点x和y均有max{d(x),d(y)}≥n/2或|N(x)∪N(y)|≥n-δ,则G是Hamilton图. 相似文献
10.
对Hamilton图性质的一个改进 总被引:1,自引:1,他引:0
n阶图G称为Hamilton图是指G包含一个长为n的圈,Bollbás曾证明了在Hamilton图H中,若边数e(H)≥n24-n+59,则H必含长为(n-1)的圈或具有特殊结构的长为(n-2)的圈.我们认为条件e(H)≥n24-n+59可以进一步减弱,本文证明了在e(H)≥n24-n+15的条件下,结论同样成立. 相似文献
11.
主要证明了以下结果;1.如果G是一个连通的无爪的非哈密顿图,则G至少有一条长为2δ+的路。2.如果G是一个2连通的无爪图,且δ(p-2)/3,则G是可迹的。3.G是一个2连通的无爪图,且不含生成子图B工G1,如果G的每个朵匀于Z2的生成子图都满足ψ(α1,b1)ˇψ(α1,b2),则是G是泛圈图。 相似文献
12.
陈东灵 《曲阜师范大学学报》1992,18(4):36-38
讨论了Hamilton图G和它的邻接矩阵A之间的关系,得到如下结果定理1:图G是H-图当且仅当A=B+Q,这里B≥0且B≠0,Q=PCP,C是由互换单矩阵中的第1行和第n行所得到的初等阵,P是置换阵,P是P的转置矩阵,定理:图G是H-图当且仅当A的谱半径ρ(A)是A的单根,且存在正特征向量ξ,使得Aξ=ρ(A)ξ>η,这里η是适当调整ξ的分量而得到的向量,满足:当ξ的第i个分量调为η的第j个分量时,A的(i,j)元aij=1. 相似文献
13.
14.
15.
16.
17.
任韩 《武汉科技大学学报(自然科学版)》1995,(1)
设G=(V,E)为n阶2-连通的1-坚韧图。将G的节点分类:g={v∈V|dG(v)≥n/2}而H=(G\g)。如果H满足Ore-条件:x,y∈V(H),(x,y)∈E(H)dH(x)+dH(y)≥|V(H)|,则有:(i)G是Hamilton的;(ii)若G不是偶图,则G至多丢失长为n-1的圈. 相似文献
18.
关于图G的节点(数码对)所作的双向搜寻产生一种搜寻树.由叠套结构组合出码,构成算法,基于节点关联矩阵的数码比较运算,逐层产生搜索树.用搜索树可系统地产生任意图的全部Hamilton回路,也可产生两节点间全部路径的完整系统.本算法易于编制程序,其速度快,内存小的优点是显而易见的. 相似文献
19.
任意无向图的最小R边连通扩充 总被引:2,自引:2,他引:2
研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。 相似文献