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

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

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

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

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

5、e得圖G-e.(2)如果e的某個端點在G-e中度數(shù)為3，則去掉此端點，再兩兩聯(lián)結(jié)此端點在G-e中的3個鄰點.(3)如果通過運算(2)后有多重邊出現(xiàn)，則用單邊代替它們，使此圖成為簡單圖.最后得到的圖記為GΘe.如果G()e仍舊為4連通圖，則稱e為G的可去邊；否則稱為G的不可去邊.在第三章中對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的邊-點割原子，|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是一邊-點割原子，且E(A)∩EN(G)≠φ，則|A|=2.(3).設(shè)G是階數(shù)至少為8且最小度至少為5的4連通圖，則對于G中任意邊e，則有e是可去邊或e是可收縮邊。(4).G是4連

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