图的Hamilton性、Ramsey数和四色问题的研究

来源 :山西大学 | 被引量 : 0次 | 上传用户:sinner888
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文分为三章对有限图的Hamilton性、Ramsey数和四色猜想三方面的问题分别作了讨论。 在第一章里我们讨论了图的Hamilton性问题。文章第一节首先介绍了Hamilton图的概念和一些相关的定理。第二节对Ore定理的结论进行了推广,证明了2连通简单图G,若独立数α≥3且对G中任意一个独立集{x,y,z}有dx+dy+dz≥3ν/2,则G是Hamilton图,同时还证明了G是2连通简单图,若G的独立数α≥3且对G中任意一个独立集{x,y,z}有dx+dy+dz≥ν+α,则G是Hamilton图。第三节我们首先定义了平衡二部图的一个半闭包G+,并证明了若一个简单平衡二部图G的半闭包G+为完全二部图,则G为Hamilton图。然后,我们构作了一类度极大的非Hamilton简单二部图bm, n,证明了与1972年Chvátal得到的一个结论类似的结果:若G是ν≥4的非Hamilton简单平衡二部图,它一定度弱于某个度极大的非Hamilton简单二部图bm, n。第四节主要讨论部数为3和4的几乎正则多部竞赛图的Hamilton性质,证明几乎正则非平衡4部竞赛图T,如果r≥8(其中r=max{Vi|i=1,2,3,4}),并且T有一个圈因子,则T是Hamilton的;几乎正则平衡3部竞赛图T,如果r≥10,r≠11(其中r=max{Vi|i=1,2,3}),并且T有一个圈因子,则T是Hamilton的;几乎正则非平衡3部竞赛图T,如果r≥18,r≠19,并且T有一个圈因子,则T是Hamilton的。 第二章研究了图的Ramsey数方面的问题。我们证明了Ramsey数r(k1,k2,…,km),若ki=2,则r(k1,k2,…,ki-1,ki,ki+1,…,kn)=r(k1,k2,…,ki-1,ki+1,…,kn);若ki=3,则非平凡的Ramsey数r(k1,k2,…,ki-1,ki+1,…,kn)<r(k1,k2,…,ki-1,ki,ki+1,…,kn)。 第三章讨论了著名的平面图的“四色猜想”问题。我们证明了对于平图G,如果它的任意k个顶点的生成子图G′都有δ(G′)≤4则G是4-可着色的。在第二节中,我们指出了颜宪邦,屈姿朴在其《四色定理论证》一文中忽视的一个问题,此问题若无法解决,将会导致其证明方法失效。
其他文献
信息技术的快速发展与应用,对人们的生活和工作都产生了深刻影响。为了适应信息环境变化,满足新的工作需要,推动行政事业单位会计信息化建设成为一种必然趋势。《政府会计制度》的实施,对行政事业单位会计信息化建设提出了相应要求,并指明了发展方向。基于此,本文首先分析了加强行政事业单位会计信息化建设的必要性,并结合信息技术发展、工作需要与单位实际,对当前我国行政事业单位会计信息化建设中普遍存在的问题进行了深入
昆虫不像高等动物那样有完善专一的免疫体系,缺乏B和T淋巴细胞,没有免疫球蛋白和补体,但是它们有极强的适应能力和防御能力。昆虫在感染病菌或体壁受到损伤等情况下能够迅速合成一系列低分子量的抗菌蛋白/多肽,杀死病菌并且阻止病菌的继续侵染。昆虫抗菌肽具有分子量小、热稳定性好、不易被水解、无免疫原性等特点。近年来,昆虫抗菌肽的研究逐渐成为昆虫免疫学及分子生物学研究热点之一,迄今已从各类昆虫分离鉴定200多个
Kerr非线性效应的研究在量子光学和非线性光学中有重要的意义,例如可以用来实现量子的非破坏测量以及利用交叉相位调制实现光学Kerr开关等。近年来,利用原子和光场相互作用过程中量子相干所导致的EIT效应可得到无吸收、可控的极大增强的三阶Kerr非线性系数,这对实现全量子计算、光量子逻辑门以及单光子开关具有重要的意义。不仅在EIT过程可导致介质的线性和非线性极化率发生很大的变化,而且近来有的研究小组表
设G是一个连通有限简单图,有n个顶点υ1,υ2,…,υn,且有邻接矩阵A(G)=(αij)n×n,此处G的特征多项式为|xI-A(G)|。由于A(G)是实对称矩阵,故A(G)的所有特征值均为实数。不失一般性,假定它们按不增顺序排列,即 λ1(G)≥λ2(G)≥…≥λn(G)且称之为G的特征值。 当我们考虑的图是树的时候,相应的特征值的界已有了丰富的结果。但是对于具有m-匹配的树的第二大
本文的研究内容涉及有向图的三个方面:几乎正则多部竞赛图的Hamilton性,竞赛图的Hamilton-路数的下界及几种特殊有向图控制集的计数问题。 多部或n-部竞赛图是完全n-部图的一个定向。竞赛图是恰有n个顶点的n-部竞赛图。设x是有向图D的一个顶点,dD+(x)和dD-(x)分别表示x的出度和入度。有向图D=(V,A)的非正则度I(D)=(?){|d+(x)-d-(y)|)。称有向图D是
S.Karimis在文献[2]中讨论碳氢化合物时引进了(k,l)-正则极大平面图的定义,即:如果一个简单图G的顶点的度要么是k,要么是l,则称G是(k,l)-正则的。若一个n阶有ε条边的简单图G是(k,l)-正则的,且其边数ε=3n-6,那么我们称图G为(k,l)-正则极大平面图。本文在S.Karimis和Dragan Stevanovic研究的基础上,研究并得出了(k,l)-正则极大平面图存在的
本文主要讨论两尺度方程φ(x)=2 sum from k∈Z2 to hkφ(Ax-k),在尺度矩阵A满足|detA|=2且尺度系数{hk}k∈Z2,为特定排列方式的情况下尺度函数φ(x)的正交性和正则性问题,从而构造了一类新的非分离二元正交小波,同时本文研究了这类正交小波的尺度函数的光滑性。 在第一节中,我们介绍了一些与本文相关的基本概念和结论。 在第二节中,给出了本文的主要结论。本
关于线性算子升与降的概念最早由A.E.Taylor([1],1966)和D.C.Lay([2],1970)提出,他们利用升与降给出了线性算子谱分析的一些结果。这些内容也可见于由上述二人写的书[3]中,文献[3]对线性算子定义了升与降。1991年,S.M.Verduyn Lunel([4])对线性算子半群提出了升的概念,并利用它讨论算子半群无穷小母元根子空间完整性问题。但对线性算子半群升与降的系统研
本文主要讨论了算子的不动点的存在性问题,一是关于集值算子的,二是关于线性空间中的单值算子的。 集值分析是20世纪40年代以后蓬勃发展起来的一个现代数学分支,它已成为非线性分析的重要组成部分。而算子的不动点定理是非线性分析的基础,所以研究集值算子的不动点定理及其应用有着重要的意义。 第一章讨论了半序集和半序拓扑空间中的集值算子,主要使用了半序方法和单调迭代技巧。在§1.1中,将集值算子的
本文分为两章,第一章研究了连通无向图G的顶点扩张图(见定义1.13)的最小直径定向问题。图的最小直径定向问题的研究来自对单行街和流言问题的研究,目前这两个问题仍为研究的热点。单行街问题可以追溯到Robbins的经典论文[3],文[3]给出著名的单行街定理:一个连通的无向图G有强连通定向当且仅当G无桥。对一个无桥的连通无向图G,设Ω(G)表示G的强连通定向集合,对每一个D∈Ω(G),我们用d(D)(