連通圖中的可去邊及其算法分析.pdf

1、圖中可縮邊與可去邊是探討圖的結(jié)構(gòu)，尋求使用歸納法證明圖的某些性質(zhì)的一個(gè)有利工具.W.T.Tutte在1961年給出3-連通圖的結(jié)構(gòu)特征定理時(shí)，實(shí)際上用到了可去邊與可縮邊的存在性，Tutte給出了極為出色的3連通圖的結(jié)構(gòu)為：G時(shí)3連通圖當(dāng)且僅當(dāng)G是一個(gè)輪，或是從一個(gè)輪重復(fù)使用以下而種運(yùn)算推得的圖：(1).加邊；(2).拆點(diǎn)。證明了每個(gè)階大于或等于5的3-連通圖必有可縮邊，這是有關(guān)可去邊與可縮邊的最早的結(jié)果.Holton，.Jackson，

2、Wormald等在[3]中對(duì)3連通圖中可去邊的分布及數(shù)目進(jìn)行了探討.蘇健基在中得出了3連通圖中可去邊的下界，并描述了達(dá)到這一下界的圖的結(jié)構(gòu)特征.Fouquet，Thuiller和McCuaig在[5，17]中對(duì)3連通3正則圖中的可去邊進(jìn)行了研究。 尹建華在[2]中證明了4連通圖G(階數(shù)為5和6的2循環(huán)圖除外)中總存在可去邊，并且利用4連通圖存在可去邊與可收縮邊的事實(shí)，證明了一個(gè)4連通圖總可以從一個(gè)2循環(huán)圖經(jīng)過(guò)以下步驟得到：(1)

3、.加邊；(2).拆點(diǎn)；(3).加點(diǎn)去邊；(4).擴(kuò)點(diǎn)。 近二十多年來(lái)，有關(guān)可去邊和可收縮邊的研究已經(jīng)有了很大進(jìn)展，許多文獻(xiàn)重點(diǎn)研究了一個(gè)圖中可縮邊與可去邊的數(shù)目. 本論文主要研究了圖論及其應(yīng)用中連通度方面的問(wèn)題，重點(diǎn)放在了3連通圖與4連通圖方面：其主要研究成果如下：(1)在論文的第一部分(第二章)，我們研究了3連通圖的可去邊在生成樹(shù)上的分布。G是3-連通圖，e是G中的一條邊。若G-e是3連通圖的一個(gè)剖分，則稱(chēng)e是3連通圖

4、的可去邊。否則，e是G中不可去邊。我們?cè)谇叭搜芯康幕A(chǔ)上，對(duì)3連通圖的可去邊作了進(jìn)一步的研究，得到了以下結(jié)論：(1)3連通3正則圖的生成樹(shù)上至少有兩條可去邊；(2)設(shè)G是最小度至少為4的3連通圖，則任一生成樹(shù)上至少有兩條可去邊。(3)設(shè)G是圍長(zhǎng)至少為4的3連通圖，則任一生成樹(shù)上至少有兩條可去邊。 (2)在論文的第二部分(第三章--第六章)，我們主要對(duì)4連通圖中的可去邊作了一些研究。4連通圖G中的可去邊定義如下：(1)從G中去掉邊

5、e得圖G-e.(2)如果e的某個(gè)端點(diǎn)在G-e中度數(shù)為3，則去掉此端點(diǎn)，再兩兩聯(lián)結(jié)此端點(diǎn)在G-e中的3個(gè)鄰點(diǎn).(3)如果通過(guò)運(yùn)算(2)后有多重邊出現(xiàn)，則用單邊代替它們，使此圖成為簡(jiǎn)單圖.最后得到的圖記為GΘe.如果G()e仍舊為4連通圖，則稱(chēng)e為G的可去邊；否則稱(chēng)為G的不可去邊.在第三章中對(duì)4連通圖的可去邊的性質(zhì)作了研究，我們記G的所有不可去邊記為EN(G)，G的所有可去邊記為ER(G)，得到了以下結(jié)果：(1).G為4連通圖，且|G|≥7

6、，(xy，S；A，B)是G的分離組，其中x∈A，y∈B.若A是G的邊-點(diǎn)割原子，|A|≥3，且a∈S，z∈A，za∈E(G)，則za∈ER(G)。(2).設(shè)G是4連通圖，且|G|≥7，xy∈EN(G)，(xy，S；A，B)是G的分離組，其中x∈A，y∈B，若A是一邊-點(diǎn)割原子，且E(A)∩EN(G)≠φ，則|A|=2.(3).設(shè)G是階數(shù)至少為8且最小度至少為5的4連通圖，則對(duì)于G中任意邊e，則有e是可去邊或e是可收縮邊。(4).G是4連

7、通圖，設(shè)C是G中的5-圈，若G不同構(gòu)于階數(shù)為10的環(huán)帶或階數(shù)為7的雙輪(具體定義見(jiàn)正文)，則C上至少有兩條可去邊。在第四章，我們得到了以下結(jié)果：對(duì)于每一個(gè)階數(shù)大于或等于6的4連通圖(階數(shù)為6的2循環(huán)圖除外)，至少有[(4|G|+16)/7]條可去邊，并且刻劃了達(dá)到這一下界的圖的結(jié)構(gòu)特征。在論文的第五章和第六章，我們對(duì)4連通圖中某些子圖的可去邊的分布進(jìn)行了研究，得到了如下結(jié)果：(1).G是圍長(zhǎng)至少是4的4連通圖，則G中的最長(zhǎng)圈上至少有兩條