论文部分内容阅读
作为四色定理证明进程中的一个里程碑,哈密顿圈引起了人们的广泛兴趣。众所周知,在给定的一个图中是否存在哈密顿圈是一个NP完全问题。这对数学家们来说是一个新的挑战,使他们着迷于这一课题的研究。对于4连通平面图中哈密顿圈的研究可追溯到上世纪三十年代,Whitney证明了任何一个4连通有限平面图的三角剖分都包含一个哈密顿圈。这个结果被Tutte于1956年推广至所有4连通有限平面图。1983年,Thomassen进一步证明了任何一个4连通有限平面图都是哈密顿连通的。为了更进一步在无限图中推广Tutte的这一结果,Bruhn提出猜想:任何一个局部有限4连通无限平面图中均含有一个哈密顿圈。2005年,郁星星教授证明了这一猜想对恰好含有一个端的局部有限4连通无限平面图成立。最近,Bruhn和郁星星教授证明了这个猜想对于含有有限个端的局部有限6连通无限平面图也成立。本文的主要贡献就是研究Bruhn猜想的另一种主要情况,即任何一个不含分割圈的局部有限4连通无限平面图均存在一个哈密顿圈。本文结构如下。在第一章中,我们首先简要介绍了有限图中哈密顿圈的发展背景,以及它在无限图中的一些已有结果。为叙述和证明的需要,我们引入了一些无限图中的基本术语和记号,并给出本文主要定理的精确描述。随后,我们描述了由Diestel和K(u|¨)hn定义的无限图的拓扑结构。这一拓扑结构的提出使得无限平面图中哈密顿圈的研究具有可行性。此外,我们还介绍了本文证明过程中使用的主要工具——Tutte子图技巧。我们进一步介绍了两个关于2连通有限平面图中某种特定Tutte路的存在性的已知结果。这两个结果为后续证明中延伸Tutte子图提供了灵活的证明方法。为避免4连通条件可能带来的困扰,我们为几乎是4连通的一类2连通平面图定义了一种新的连通度——(4,C)连通。另外,为了清晰的展示无限平面图的结构,我们引入了一种平面图的嵌入表示方式,称为优嵌入。进一步地,我们描述了不含有分割圈的无限平面图的结构。上述这些条件和结构是证明主要结果的基础。最后,为了便于读者理解证明的整体思路,我们概括了本文主要结果的证明过程。第二章中,我们证明了4元集分层结构中Tutte子图的两个结果。为表述局部有限的无限平面图的一类特殊结构,我们首先定义4元集,并且针对4元集的偶数层和奇数层分别给出了两个引理,证明了给定的4元集(G,H,x,y)(G是(4,C)连通的)中一定存在由G的子图或几乎是G的子图的B1,B2….Bκ所构成的一系列4元集,使得∪i=1kBi的Tutte子图T′可以延伸成为G的Tutte子图T,并且T的闭包构成一个圈或一个弧。这两个引理有利于刻画4元集中Tutte子图的层次结构。第三章中,我们给出了主要定理的证明过程。我们首先介绍了有限路序列收敛的定义,K(o|¨)nig无限引理的一个变型以及Bruhn和Stein提出的一个局部有限图中形成一个圈的充分必要条件。基于这些已知结果以及前行路的定义,我们证明了4元集(G,H,x,y)(G是(4,H)连通的)的一个结构性结果:这一4元集中一定存在一个G的包含H上一条边的H-Tutte子图T,使得T在|G|中的闭包是一个从x到y的弧。最后,我们得到如果一个不含分割圈的局部有限的2连通无限平面图G至少有两个端,则G中一定含有一个Tutte子图T使得它在|G|中的闭包是一个圈。再结合郁星星教授关于恰好含有一个端的局部有限无限平面图上的结果,我们完成了预想结果的证明。