Tutte子圖方法及其應(yīng)用.pdf

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

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

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

4、慮Malkevitch提出的猜想一如果一個n個頂點的4連通平面圖含有長度為4的圈，那么它一定含有長度為k的圈，其中k∈{n，n-1….，3}。已有的結(jié)果證明了每一個n個頂點的4連通平面圖都含有長度為k的圈，其中k∈{n，n-1….，n-6)且后≥3。通過運用Tutte子圖和可收縮子圖的方法，我們證明每一個n個頂點(n≥9)的4連通平面圖總是含有不包含某一給定頂點的長度為n-6的圈。運用這一結(jié)果(以及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所對應(yīng)的邊后得到的圖是一個偶圖。通過運用這一性質(zhì)以及Tutte子圖方法，Thomassen證明了如下等價結(jié)果：每一個最小度至少為4的平面三角剖分圖G都含有一個至多有7｜V(G)｜/12條邊的邊子集合使得在G中刪除這些邊后得到的圖是一個偶圖。我們通過拓展Thomassen在Tutte圈上的結(jié)果將上界改進到9｜V(G)｜/16-9/16，這表明每一個3連通3正則不含三角形的平面圖G中都含有一個至少有39｜V(G)｜/32-