图的生成连通性及哈密尔顿连通指标

来源 :新疆大学 | 被引量 : 0次 | 上传用户:itbbs123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G=(V, E)是一个连通图。图G是哈密尔顿的,如果它有一个哈密尔顿圈(包含G的所有的顶点的圈)。如果G的任意两个顶点之间存在一个哈密尔顿路(包含G的所有的顶点的路),则G称为哈密尔顿连通的。图G称为k连通的,如果G的任意两个顶点之间存在k条内部不交的路。连通度κ(G)是最小的正整数k,使得删掉G的k个顶点后G是不连通的。在本文中,我们研究幂图的生成连通性以及树和单圈图的哈密尔顿连通指标。图的生成连通性是连通性和哈密尔顿性的融合与推广。我们的主要结果是:(a).对于任意u,v∈V(G),--个k*-container C(u,v)是k-条内部不交的(u,v)-路的集合,使得C(u,v)包含G的所有顶点。G是k*-连通的,如果任意两个顶点之间存在一个k*-container.如果G是1*-连通的,那么G的生成连通度K*(G),是最大的正整数k,使得对所有的i:1≤i≤k,G是i*-连通的,否则生成连通度没有定义。图G的s-次幂,记作Gs,是定义在V(G)上的图,使得在Gs中两个顶点相连当且仅当它们在G中的距离不超过s。我们证明:如果G是一个|V(G)|≥k+1≥4的连通图,那么Gk是k*-连通的。(b).图G=(V(G),E(G))的线图L(G)是一个图,它以E(G)作为顶点集,且L(G)中两个顶点相连当且仅当相应的边在G中相邻。叠加线图递归地定义为L0(G)=G且Lk+1(G)=L(Lk(G))(k∈N,其中N表示自然数集)。图G的哈密尔顿指标h(G)(哈密尔顿连通指标hc(G))是使得G的叠加线图Lk(G)是哈密尔顿的(哈密尔顿连通的)最小的k。Chatrand和Wall给出了树的哈密尔顿指标的精确的计算公式。我们证明:对于树T,h(T)≤hc(T)≤h(T)+1,对于单圈图G有:h(G)≤hc(G)≤max{h(G)+1,k’+1},其中k’满足下列三个条件的最长的路的长度:(1)全部顶点在某个圈上,(2)两个端点的度数至少为3,(3)内部顶点的度数全是2。我们还刻画了对于满足hc(T)=h(T)+1和hc(G)=h(G)+1的所有的树T和单圈图G。
其他文献
能源安全已经提升至国家层面,需要开源节流处理之。对于主机厂,就是从节流的角度提升燃油经济性(含电耗提升)。对于传统能源车,主要从整车阻力、附件消耗、发动机热效率角度去提升性能;对于新能源车,还需从三电控制策略、制动能量回收角度去处理。不管是哪一类型的车,言而总之都是能量优化,都可以从能量管理的角度,分析能量流动、拆解能量损耗,找出能量消耗的薄弱点,从而进行有针对性的优化。
国家新颁布的《普通高中课程标准(实验)》作为基础教育改革的重要举措,成为我国新一轮高考制度的主要依据。新高考政策的实施,在一定程度上改变了传统的教学模式,对学生产生了很大的影响,教师的教学方式和学生的学习方法都发生着翻天覆地的变化,对高中数学教学提出了更高的要求和挑战。
目的总结风湿性心脏炎的临床特点及用心脏彩超评价治疗前后心脏结构及功能情况。方法回顾性分析2007年10月到2019年4月首都医科大学附属北京儿童医院收治的136例风湿性心脏炎患儿的临床特点,用心脏彩超评价治疗前与治疗后6个月心脏结构变化,分析抗风湿治疗的效果。结果风湿性心脏炎患儿临床症状部分不典型。心脏彩超表现以瓣膜返流最为常见(86.0%),其次为心脏增大(34.6%),极少存在心包积液(0.7
论文通过对高枝假木贼(Anabasis elatior)的胎生萌发物候、种子萌发特性、耐盐性、幼苗耐干燥特性以及胎生苗的形成进行观察研究,并结合环境因子探讨其对准噶尔荒漠极端环境的响应对策,得出如下结论:(1)高枝假木贼具有胎生繁殖现象。其果实于10月成熟后不脱落,冬季被积雪覆盖。于次年早春积雪融化时(3月上旬~4月上旬)种子在株上萌发形成胎生幼苗。胎生萌发时,胚根首先突破种皮,下胚轴快速生长形成
杨博华简介:北京中医药大学东直门医院周围血管科主任、北京中医药大学中医外科教研室主任、教授、博士生导师,兼任中国中西医结合学会周围血管病专业委员会副主任委员、中国中医药学会疮疡专业委员会副主任委员、北京中西医结合学会周围血管病专业委员会主任委员、北京市中医血管疾病治疗中心主任等职。擅长血管外科、普通外科疾病,如动脉硬化闭塞症、糖尿病足、大动脉炎、静脉曲张等的中西医结合治疗,特别是对难治性溃疡
期刊
对于图G=(V,E),S-V. G的控制集S指的是对于每一个点v∈V\S在S中都有一个邻点u.此外,如果S是一个控制集并且G[S]连通,则S就是一个连通控制集.控制数γ(G)和连通控制数γc(G)分别指的是最小控制集和最小连通控制集的基数.很显然γ(G)≤γc(G). G的中心集指的是对于V\S中的任意两个点都存在连接它们的一条路,并且这条路的中间点在S中.当S为中心集并且G[S]连通的话,就称S
对一个连通图G=(V, E)和一个定义在正整数集上的点赋权函数w,G的一个最大最小平衡连通k-划分是指V的一个无交k-划分(V1,V2,...,Vk)使得G[Vi](由Vi导出的G的子图)是连通的并且min1≤i≤k{W(Vi)}是最大化的,记为BCPk.该问题在图像处理和聚类分析中有许多应用,并已经被证明是NP-困难的.在这篇文章中,我们在一类特殊图上研究BC只问题:即图的最大度被一个常数所限制
绵果荠(Lachnoloma lehmannii Bunge.)是十字花科绵果荠属的一年生短命植物,在我国主要分布在新疆北部准噶尔盆地周缘的盐渍化荒漠环境,其短角果卵形密被绵毛,果皮厚而硬,成熟时不开裂,以果实为单元从植株上散布。本文采用野外观察及田间与室内控制性实验相结合的方法,对绵果荠果实形态对其扩散、定居及种子萌发的影响,以及该物种休眠与萌发和耐盐特性进行了详细研究,以期揭示该物种对准噶尔荒
图的拓扑指标的学习和研究是图论应用研究的一个非常重要的部分.拓扑指标在计算机科学,组合化学,物理及其它应用学科中都有着十分广泛的应用.我们希望利用所有可能的信息来描述图的各种特征并且使它在我们以后更深层的研究和实际应用中运用.如果一个简单图的每个顶点代表分子中的一个原子,每条边代表原子之间形成的化学键,我们称这种图为分子图.图论学科的产生与发展和化学分子图的研究有密切的联系.分子拓扑指标与分子的不