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

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

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

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

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

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

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