隐度条件下图的若干性质

来源 :兰州大学 | 被引量 : 0次 | 上传用户:wychenjian
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论的研究始于1736年,Euler用图的方法解决了哥尼斯堡(Konigsberg)七桥问题,并发表了第一篇关于图论的学术论文.从此,图论这门新的学科诞生了.20世纪60年代以来,图论在科学界异军突起,迅猛发展.同时,众多有趣的图论问题也应运而生,比如哈密尔顿问题,中国邮递员问题,染色问题,连通性问题,匹配问题等.并且,应用图论的方法解决化学,生物学,信息与计算科学等学科中的问题已显示出极大的优越性.此外,图论在工程技术领域及社会科学领域中也有着广泛的应用.图G中经过每个顶点的圈,称为G的哈密尔顿圈.如果G中有一个哈密尔顿圈,那么我们称G是哈密尔顿图或者哈密尔顿的.哈密尔顿圈这一概念最初是由爱尔兰数学家W.R. Hamilton作为一个数学游戏提出来的.并且由这一游戏诱导出一个经典的图论问题-哈密尔顿问题(判断一个图是不是哈密尔顿的).哈密尔顿问题包含一系列问题:如哈密尔顿圈,哈密尔顿路,图的周长,泛圈,控制圈,图中的最长路和最长圈的相对长度等.哈密尔顿问题与四色问题,图的结构理论及极值理论等有着密切的联系.同时,哈密尔顿理论在网络结构及复杂性理论方面也有着广泛的应用.因此,从1970年开始,哈密尔顿问题得到了学者们的广泛关注.但是因为哈密尔顿问题是一个NP-完全问题,所以寻找图是哈密尔顿的充分条件就成为众多学者研究的主流方向.本文所考虑的图均是简单无向图.设G=(V(G),E(G))是一个图,其中V(G)和E(G)分别表示图G的顶点集和边集.图G中顶点的个数叫做G的阶.对于G中的一个顶点v,G中与v相邻的顶点的集合和个数分别称为顶点v的邻域和度,分别记为N(v)和d(v).顶点u和v在G中的距离记为d(u,v).G中与v距离为2的顶点的集合记为N2(v).由于有些顶点的度比较小,我们希望在证明过程中在适当的位置用度较大的顶点来代替那些度较小的顶点.在这一想法的启发下,1989年,Zhu, Li和Deng提出了顶点v的两个隐度(implicit degree)的定义-第一隐度id1(v)和第二隐度id2(v).记m2=min{d(u):u∈N2(v)}及M2=max{d(u):u∈N2(v)}.令k=d(v)-1.设d1≤d2≤≤dk≤dk+1≤为N(v)∪N2(v)中顶点的度序列.(a)如果N2(v)≠Φ且d(v)≥2,那么id1(v)和id2(v)的定义分别为:(b)如果N2(v)=0或者d(v)<2,那么id1(v)=id2(v)=d(v).由上面的定义可以看出:对任意的顶点v都有id2(v)≥id1(v)≥d(v).如果一个顶点数为n的图中包含从3到n之间所有长度的圈,那么我们称这个图为泛圈的.显然,一个泛圈图也是一个哈密尔顿图;反之,不一定成立.如果图G的一个圈C满足G-C的每个分支都是独立点,也就是说图G的每条边至少关联C中的一个顶点,那么称C为G的一个控制圈.本文在隐度条件下研究了图论中的哈密尔顿圈,泛圈,控制圈以及图中的最长路和最长圈的相对长度.全文共分为五章.第一章我们给出了一个简短但相对完整的综述.首先,我们给出了一些基本的定义和术语;然后对上述四个方面的研究进展分别做了介绍并且给出了本文在上述四个方面得到的主要结果.在第二章,我们研究了第二隐度条件下图的哈密尔顿圈的存在性问题,给出了图中有哈密尔顿圈的一个充分条件.证明了:设G是一个阶数为n≥3的2-连通图,如果G中任意一对距离为2的顶点的第二隐度之和大于或等于n-1,那么除了一些特殊图类之外,G是哈密尔顿的.并且通过例子说明我们的结果的优越性.在第三章,我们考虑了第二隐度条件下图的泛圈性问题,给出了图是泛圈的一个充分条件.1971年,Bondy证明了:如果一个阶数为n≥3的图的每个顶点的度大于或等于n/2,那么这个图要么是泛圈的;要么同构于完全二部图Kn/2,n/2.并且他给出一个meta猜想:几乎所有能表明一个图是哈密尔顿的非平凡条件也能表明这个图是泛圈的(可能除了一些特殊图类外).第三章中,我们根据这个猜想证明了:设G是一个阶数为n≥3的2-连通图,如果G的每个顶点的第二隐度都大于或等于n/2,那么G要么是泛圈的:要么是二部图;要么n=4r,r≥2并且G同构于F4r.并且通过例子说明我们的结果比Bondy的结果具有优越性.在第四章,我们研究了隐度条件下图的控制圈问题,给出了隐度条件下无爪图的每个最长圈都是控制圈的一个充分条件.首先我们根据Zhu,Li和Deng给出的两种隐度的定义思想,给出了另一种隐度的定义,具体定义如下:(a)如果N2(v)≠Φ且d(v)≥3,那么顶点v的隐度id0(v)定义为:(b)如果N2(v)=Φ或者d(v)≤2,那么id0(v)=d(v).由上面的定义可以看出:对任意的顶点v都有id0(v)≥d(v).由于通过考虑4个或更多个独立点的度和来寻找图是哈密尔顿的充分条件有一定的困难,所以许多学者转向研究图中有控制圈的充分条件以及控制圈与最长圈的关系Nash-Williams给出了2-连通图中每个最长圈都是控制圈的一个充分条件,他证明了:如果一个阶数为n的2-连通图的每个顶点的度都大于或等于(n+2)/3,那么这个图的每个最长圈都是控制圈.第四章中,我们研究了在新的隐度条件下3-连通无爪图有控制圈的一个充分条件.证明了:如果一个阶数为n的3-连通无爪图的每个顶点v的隐度id0(v)都大于或等于(n+2)/3,那么这个图的每个最长圈都是控制圈.同时,通过例子说明结果中的连通度是最好可能的,并且在一定意义上我们的结果比Nash-Williams的结果具有优越性.在第五章,我们考虑了图的最长路的顶点数和最长圈的顶点数之间的关系.我们用p(G)和c(G)分别表示G的最长路和最长圈的顶点数Enomoto,Heuuel, Kaneko和Saito证明了:如果一个阶数为n的连通图G的任意三个独立点的度和都大于或等于n,那么要么G中有一条哈密尔顿路;要么c(G)≥p(G)-1.第五章中,我们在第二隐度的条件下研究图的最长路的顶点数和最长圈的顶点数之间的关系,得出了:如果一个阶数为n的2-连通图G的任意三个独立点的第二隐度和都大于或等于n+1,那么要么G中有一条哈密尔顿路;要么c(G)≥p(G)-1.并且通过例子说明了结果中的连通度和下界都是最好可能的以及我们结果的优越性.
其他文献
生长素发现至今已有130余年,经过科学工作者们不懈的努力,在生长素的合成、信号传导、运输方面的研究都取得了一定的进展,然而在生长素的研究中还存在很多问题。就生长素合成方面而言,存在多种途径交叉形成的网络,很多基因是未知的,且各种途径的调节和相互关系很多也是未知的。由于生长素在植物的生长发育中起关键的调节作用以及大量冗余基因的存在,很难筛选到内源生长素降低的突变体。本文系统阐述了本实验室建立的生长素
本论文主要研究了Bloch厚膜和标量—张量薄膜上引力及物质场的局域化和质量谱问题。论文第一部分研究了引力和费米子在对称和非对称的Bloch厚膜上的局域化和共振态问题。我们主要考虑了具有内部结构的双膜情况。对于对称双膜,引力零模和费米零模的局域化性质一样,即它们均局域化在两个子膜之间。对于非对称双膜,引力零模局域化在一个子膜上,而费米零模局域化在另一个子膜上。引力子和左手征费米子质量谱都是由一个束缚
随着电子信息产业的迅速发展,要求电子元器件向小型化、高频化和集成化的方向发展,这便对作为电子元器件的核心即软磁材料提出了更高的要求。目前,研究具有高磁导率(μ)、低矫顽力(Hc)、高饱和磁化强度(4πMs)、高电阻率(p)以及适当大小的面内单轴各向异性场(Hk)的软磁材料已成为软磁材料发展的必然方向。Fe-N薄膜因为具有优异的铁磁、机械性能和良好的抗氧化、耐腐蚀、耐磨损以及好的热稳定性而成为很有发
椭圆问题是偏微分方程研究中最主要的问题之一,属于核心数学的研究范畴.早在1900年D.Hilbert提出的著名的23个问题中就有3个与椭圆问题有关.过去的一个多世纪椭圆问题得到了丰富的研究,获得了丰硕的成果,形成了庞大的理论体系,其在几何学、流体力学、热力学等自然科学和工程技术的各个领域都得到了广泛应用并有力地推动了这些学科的发展.本篇博士论文主要研究了一类从MEMS(micro electro
利用卫星观测资料、再分析资料,结合大气化学气候模式(WACCM),研究了热带上对流层下平流层(UTLS)区域一氧化碳(CO)时空变化和热带平流层CO准两年振荡(QBO)位相变化特征的形成机理,分析了亚洲夏季风反气旋环流造成的副热带地区向热带地区的CO水平输送对热带UTLS区域CO时空变化的影响,最后还分析了不同区域排放的大气示踪物向UTLS区域动力传输的特征。所得主要结论如下:(1)利用全球化学气
体心立方结构的铁及铁合金在核(原子能)工业领域是常见的结构材料。其中低活性铁素体/马氏体钢是聚变堆结构材料的候选材料。在14MeV中子的辐照下,由于(n,α)核反应,结构材料中将产生大量的He原子。一般结构材料是由多晶组成,包含大量的晶界,所以研究He泡在铁及铁合金晶界中的行为是发展耐辐照结构材料的重要研究课题之一。为了进一步理解多晶材料的辐照损伤效应,本文通过计算机来模拟缺陷在晶界中的演化。论文
细胞分裂素影响植物生长和发育的很多方面。在低温条件下植物会出现生长迟缓的现象.这里我们分离鉴定了一个在不同温度条件下生长速度有所差异的突变体cytokinin and temperature Sensitive Mutant (ckts)。突变体表现出在所有温度下,特别是在低温条件下主根生长缓慢,在低温生长环境中对外源生长素(IAA、2,4-D)敏感,并且使用细胞分裂素(6-BA、ZT)处理发现c
在本篇博士学位论文中,主要考虑在对数压力坐标下,关于三维大尺度大气运动原始简化方程的如下初边值问题:在区域上弱解的全局存在性,强解的全局存在唯一性以及在条件下强解全局吸引子的存在性.这里(x,y, z)∈Ω,其中:z=-Hs log(p/pm),Hs是定常高度尺度,p*是定常参考压力.并且记Ω的边界为:其中:对简化方程组(1),我们首先定义了水平速度v的平均v以及它的波动v并给出了它们的一些性质,
花粉发育及花粉管生长是有花植物有性生殖的关键步骤,受到很多蛋白和信号分子的调控,是一个非常复杂的生物学过程。膜联蛋白(Annexin)家族是一类进化上保守的且能结合钙和磷脂的多基因家族,该家族成员是否参与调控花粉发育和生长的研究还未见报道。在花粉萌发和花粉管生长过程中,微丝骨架在不同的时间和空间呈现出特定的结构并行使不同功能。ACTDIN DEPOLYMERIZING FACTOR (ADF)是一
线性系统的求解在数学、物理学、统计学、工程学甚至社会科学中的很多问题求解时都占有重要的地位.比如物理中的线性偏微分方程的近似求解就需要转化为线性系统的求解,所以线性系统数值求解历来都是数值线性代数研究的主要问题.随着大规模科学计算发展的需要,线性系统的求解越来越多地受到人们的关注.众所周知,求解线性系统的数值方法一般分为两类:直接法和迭代法.直接法的计算量小,但计算格式较复杂,因而适用于阶数不太高