共查询到20条相似文献,搜索用时 62 毫秒
1.
设G 是一个n 阶简单连通图,k≥2 是一个整数.G 的k 阶幂图记作Gk ,定义为:V( Gk) = V( G) 且对任意u ,v∈V( Gk) ( u≠v) ,( u ,v) ∈E( Gk) 当且仅当dG( u ,v) ≤k ,则对任意的k≥2 ,Gk 本原.令E(k,n) = { γ( Gk)| G 是n阶简单连通图} ,可以得到E(k ,n) =dk k+ 1 ≤d ≤n - 1 , 若2 ≤k≤n - 2 ,{2} , 若k≥n - 1 . 相似文献
2.
曹细玉 《华中师范大学学报(自然科学版)》1998,32(3):263-268
证明了下列结果:(1)设G是3连通无爪图,│V(G)│≥6且G的每个导出图A都满足φ(a1,a2)那么对任意u,v∈V(G),若2≤d(u,v)≤5,则对满足d(u,v)≤k≤5的整数k,G中存在(u,v)-k路(2)设G是3连通无爪图,│V(G)│≥6,且G的每个导出子图A都满足φ(a1,a2)而P=v1,v2,...v5(v1=u,v5=v)是G的(u,v)-4路G(V(P)=K│v(p)│则 相似文献
3.
设G是n阶k-连通图(k≥3).称G的独立集S为一个基本集,如果存在{u,v}S使得dist(u,v)=2.本文证明了下述结论:如果对G的任-k-基本集S,有max{d(u)|uS}≥ 则G或者是Hamilton-连通的或者属于两类例外图之一。 相似文献
4.
Hamilton连通图的一个充分条件 总被引:1,自引:0,他引:1
周光和 《南京师大学报(自然科学版)》1994,17(1):29-34
设G是n阶3-连通图,若对任意不相邻二点{u,v}V(G)有d(u)+d(v)+2|N(u)∪N(v)|≥2n+1,则G是Hamiton连通的。 相似文献
5.
莫降涛 《广西大学学报(自然科学版)》1996,21(2):104-106
设v是图G=(V,E)的顶点,若存在顶点u∈V-{v},使子图G[N(v)∪{u}中任意一对顶点的距离不超过3,则称v是G的弱局部连通顶,点。设G是非平凡的连通无爪图,且它的任一顶点割均钫含一个弱局部连通顶点,则G包含Hamilton圈。 相似文献
6.
设G是n阶k-连通图(K≥3),称G的独立集S为一个基本集,如果存在,得得dist(u,v)=2,本文证明了下述结论:如果对G的任-k-基本集S有mux,则G或者是Hamilton-连通的或者属于两类例外图之一。 相似文献
7.
董进全 《内蒙古大学学报(自然科学版)》1995,26(1):39-42
以γ(G)记图G的控制数,如果对V(G)中任何一对满足条件uv不包于E(G)的顶点u,v,有γ(G+uv)<γ(G),则称G是控制临界的γ(G)=k的控制临图图称为是k-控制临界的,得出以下两个结果:1)如果G是具有n(>>2k)个顶点的连通3-控制临界图,则G中度≤2k的顶点的个数至多为2k,2)每个连通3-控制临界图或者有一个独立3-控制集或者有一个完全3-控制集。 相似文献
8.
蔡茂诚 《曲阜师范大学学报》1994,20(3):9-13
如果图G的每对不同顶点u和v之间都有哈密顿路相连,则称G是哈密顿连通的;而如果对于所有满足条件以d(u,v)≤q≤n-1的整数q,u和v之间有长为q路相连,则和G是泛连通的,其中以d(u,v)是u和v间的距离,而n是G的顶点数。本文证明了下述两个结果:(1)2k+1个顶点的k正则简单图是哈密顿连通的,(2)k连通国中任何两顶点之间存在k-1条长度不同的路;进而如果G的顶点数小于2k,则G是泛连通的。 相似文献
9.
王冬冬 《徐州师范大学学报(自然科学版)》1997,(4)
设G是n阶3-连通无向简单图,α表示图的独立数.若对G的所有距离为2的顶点u,v,都有d(u)+d(v)≥n或|N(u)∩N(v)|≥α,则G是Hamilton连通的,除非G属于一个特殊图类. 相似文献
10.
杨爱民 《山西大学学报(自然科学版)》1997,20(1):4-7
设G为n阶简单图,dG(u,v)记为顶点u,v之间的距离,称D(G)=(Σu≠vdG(u,v)/(n2))为G的平均距离。本文给出了用G的顶点数和连通度表示的图平均距离的一个上界 相似文献
11.
为研究以最少边集扩充一个任意无向图为R点连通图这一尚未解决的优化问题,通过将无向图点连通问题转化为有向图边连通问题,采用增广扩充的方法,提出了一个复杂度为O(|V|^5)的算法.利用该算法可最优地将给定无向图中任意2点达到所要求的点连通度.它发展了K点连通最优扩充的研究,从而使图的点连通扩充的研究在应用于网络设计的可靠性设计方面更具有实际意义. 相似文献
12.
许道云 《贵州大学学报(自然科学版)》1991,8(4):213-219
Minty算法和Mayeda—Seshu算法是求无向连通图树清单的两个直观算法,它们都比矩阵算法节省计算时间。然而,它们仍然较复杂。本文分别对这两个算法提出了改进措施,大大降低了计算复杂性。改进后的算法既简单又直观易懂。对于Minty算法,我们提出了一个不完全算法;对Mayeda—Seshu算法,我们则避开了求基本割集这一复杂步骤。 相似文献
13.
传统CAD的专家调度算法,大都集中在专家和患者一对一的会诊模式,或不同领域专家和患者多对一的会诊模式方面的研究,很少涉及对相同领域专家与患者多对一的会诊调度研究.针对这一问题,提出了群体决策思想的多专家会诊调度算法(MESDA),调度相同领域内的多位专家,为同一患者展开群体会诊.算法采用贪心策略,一方面考虑并行会诊的数量达到最大,另一方面考虑每一群诊项的专家成员数达到最大,通过滑动参数控制,从局部最优出发,逐步解决并行会诊和专家成员数的优化问题.实验结果表明:算法能够解决现实问题中相同领域专家和患者多对一的群体决策会诊的调度问题. 相似文献
14.
规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断;要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使... 相似文献
15.
提出了一个判断给定简单无向图中有无Hamilton圈的邻接边增长算法,给出了该算法的理论基础、算法步骤、算法描述及算法分析.最后给出了应用实例. 相似文献
16.
讨论了无向图G的等价有向图D(G)的构成,并利用布尔行列式det2(〖WTHX〗A〖WTBZ〗)和det2(〖WTHX〗A〖WTBZ〗)的性质,以及有向H-图的布尔行列式的判定方法和判定准则,给出了无向H-图的新特性和新判定准则. 相似文献
17.
18.
19.
记h(k)是使得满足ε=ν+h(k)的有限的无向图G包含k个边不交的圈的最小整数,P.Erds和L.Pósa证明了h(2)=4且对于任意正整数k≥1,存在充分小的正常数c1和充分大的正常数c2,使得c1klog2k≤h(k)≤c2klog2k。现把充分大的正常数c2的界缩紧到2.1相似文献
20.
研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性. 相似文献