Tutte子圖方法及其應用.pdf

1、哈密頓圈問題是數學和計算機科學中最重要的問題之一，它也與著名的四色定理有著密切聯系。1931年，Whitney在《Annals of Mathematics》中發(fā)表文章證明了每一個4連通平面三角剖分圖都含有哈密頓圈(因此，也是4面可著色的)。1956年，Tutte把Whitney的結果推廣到所有4連通平面圖，而后Thomassen在1983年對此作了進一步拓展。這些證明是借助于某些特殊的路和圈的存在性加以歸納而得到的(后來稱這些特殊的路

2、和圈為Tutte子圖)。
　　 Tutte子圖方法如今已經被廣泛應用到證明可嵌入各種曲面的圖中長路和長圈的存在性。例如：Thomasen在1983年證明了Plummer提出的猜想-每一個4連通平面圖都是哈密頓連通的，Thomas和郁星星解決了多面體領域的權威Grunbaum在1970年提出的把Tutte的結果推廣到射影平面的猜想一所有4連通射影平面圖都含有哈密頓圈，郁星星在1997年證明了Thomassen提出的猜想一所有(定向

3、和非定向)曲面上的5連通“局部平面”三角剖分圖都含有哈密頓圈，等等。
　　 在本文中，通過運用Tutte子圖方法，我們主要得到兩個結果。第一個是關于Malkevitch在1988年提出的一個猜想(第二章)，第二個是關于3連通3正則不含三角形的平面圖中的最大二部子圖問題(第三章)。
　　 在第一章中，我們主要介紹在本文中用到的一些基本定義和記號，并給出關于Tutte子圖方法的一個簡要概述。
　　 在第二章中，我們考

4、慮Malkevitch提出的猜想一如果一個n個頂點的4連通平面圖含有長度為4的圈，那么它一定含有長度為k的圈，其中k∈{n，n-1….，3}。已有的結果證明了每一個n個頂點的4連通平面圖都含有長度為k的圈，其中k∈{n，n-1….，n-6)且后≥3。通過運用Tutte子圖和可收縮子圖的方法，我們證明每一個n個頂點(n≥9)的4連通平面圖總是含有不包含某一給定頂點的長度為n-6的圈。運用這一結果(以及Fontet和Martinov的一個定

5、理)，我們進一步證明每一個n個頂點(n≥10)的4連通平面圖都含有長度為n=7的圈。
　　 在第三章中，我們研究3連通3正則不含三角形的平面圖中的最大二部子圖問題。最近，Thomassen證明了每一個3連通3正則不含三角形的平面圖G中都含有一個至少有29｜V(G)｜/24-7/6條邊的二部子圖，改進了已知的(3正則不含三角形的圖的)下界6｜V(G)｜/5。很容易可以看出，如果S是平面圖G的一個邊子集合使得G—S是一個二部圖，則在

6、G的對偶圖中刪除S所對應的邊后得到的圖是一個偶圖。通過運用這一性質以及Tutte子圖方法，Thomassen證明了如下等價結果：每一個最小度至少為4的平面三角剖分圖G都含有一個至多有7｜V(G)｜/12條邊的邊子集合使得在G中刪除這些邊后得到的圖是一個偶圖。我們通過拓展Thomassen在Tutte圈上的結果將上界改進到9｜V(G)｜/16-9/16，這表明每一個3連通3正則不含三角形的平面圖G中都含有一個至少有39｜V(G)｜/32-