论文部分内容阅读
图论的研究始于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.并且通过例子说明了结果中的连通度和下界都是最好可能的以及我们结果的优越性.