無限平面圖中的哈密頓圈.pdf

1、作為四色定理證明進(jìn)程中的一個(gè)里程碑，哈密頓圈引起了人們的廣泛興趣。眾所周知，在給定的一個(gè)圖中是否存在哈密頓圈是一個(gè)NP-完全問題。這對(duì)數(shù)學(xué)家們來說是一個(gè)新的挑戰(zhàn)，使他們著迷于這一課題的研究。
　　 對(duì)于4連通平面圖中哈密頓圈的研究可追溯到上世紀(jì)三十年代，Whitney證明了任何一個(gè)4連通有限平面圖的三角剖分都包含一個(gè)哈密頓圈。這個(gè)結(jié)果被Tutte于1956年推廣至所有4連通有限平面圖。1983年，Thomassen進(jìn)一步證明了任

2、何一個(gè)4連通有限平面圖都是哈密頓連通的。
　　 為了更進(jìn)一步在無限圖中推廣Tutte的這一結(jié)果，Bruhn提出猜想：任何一個(gè)局部有限4連通無限平面圖中均含有一個(gè)哈密頓圈。2005年，郁星星教授證明了這一猜想對(duì)恰好含有一個(gè)端的局部有限4連通無限平面圖成立。最近，Bruhn和郁星星教授證明了這個(gè)猜想對(duì)于含有有限個(gè)端的局部有限6連通無限平面圖也成立。本文的主要貢獻(xiàn)就是研究Bruhn猜想的另一種主要情況，即任何一個(gè)不含分割圈的局部有限4

3、連通無限平面圖均存在一個(gè)哈密頓圈。
　　 本文結(jié)構(gòu)如下。在第一章中，我們首先簡(jiǎn)要介紹了有限圖中哈密頓圈的發(fā)展背景，以及它在無限圖中的一些已有結(jié)果。為敘述和證明的需要，我們引入了一些無限圖中的基本術(shù)語和記號(hào)，并給出本文主要定理的精確描述。隨后，我們描述了由Diestel和Kuhn定義的無限圖的拓?fù)浣Y(jié)構(gòu)。這一拓?fù)浣Y(jié)構(gòu)的提出使得無限平面圖中哈密頓圈的研究具有可行性。此外，我們還介紹了本文證明過程中使用的主要工具-Tutte子圖技巧。我

4、們進(jìn)一步介紹了兩個(gè)關(guān)于2連通有限平面圖中某種特定Tutte路的存在性的已知結(jié)果。這兩個(gè)結(jié)果為后續(xù)證明中延伸Tutte子圖提供了靈活的證明方法。為避免4連通條件可能帶來的困擾，我們?yōu)閹缀跏?連通的一類2連通平面圖定義了一種新的連通度－－(4，C)連通。另外，為了清晰的展示無限平面圖的結(jié)構(gòu)，我們引入了一種平面圖的嵌入表示方式，稱為優(yōu)嵌入。進(jìn)一步地，我們描述了不含有分割圈的無限平面圖的結(jié)構(gòu)。上述這些條件和結(jié)構(gòu)是證明主要結(jié)果的基礎(chǔ)。最后，為了便

5、于讀者理解證明的整體思路，我們概括了本文主要結(jié)果的證明過程。
　　 第二章中，我們證明了4元集分層結(jié)構(gòu)中Tutte子圖的兩個(gè)結(jié)果。為表述局部有限的無限平面圖的一類特殊結(jié)構(gòu)，我們首先定義4元集，并且針對(duì)4元集的偶數(shù)層和奇數(shù)層分別給出了兩個(gè)引理，證明了給定的4元集(G，H，x，y)(G是(4，C)連通的)中一定存在由G的子圖或幾乎是G的子圖的B1，B2…，Bk所構(gòu)成的一系列4元集，使得∪ki=1 Bi的Tutte子圖T'可以延伸成為

6、G的Tutte子圖T，并且T的閉包構(gòu)成一個(gè)圈或一個(gè)弧。這兩個(gè)引理有利于刻畫4元集中Tutte子圖的層次結(jié)構(gòu)。
　　 第三章中，我們給出了主要定理的證明過程。我們首先介紹了有限路序列收斂的定義，Konig無限引理的一個(gè)變型以及Bruhn和Stein提出的一個(gè)局部有限圖中形成一個(gè)圈的充分必要條件?；谶@些已知結(jié)果以及前行路的定義，我們證明了4元集(G，H，x，y)(G是(4，H)連通的)的一個(gè)結(jié)構(gòu)性結(jié)果：這一4元集中一定存在一個(gè)G的