6連通圖圈和樹(shù)上的可去邊.pdf

1、圖的連通性是圖的最基本的性質(zhì)之一，同時(shí)也是圖論中的重要研究課題。除了具備較高的理論價(jià)值，圖的連通性與網(wǎng)絡(luò)模型以及組合優(yōu)化等學(xué)科課題也有著密切的聯(lián)系，加之如今計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)發(fā)展迅速，使得連通圖的研究也具有一定的應(yīng)用價(jià)值。
　　 探討連通圖的結(jié)構(gòu)特征，尋找連通圖的構(gòu)造方法一直是連通圖研究的重要課題。隨著數(shù)學(xué)歸納法在圖論中的廣泛應(yīng)用，采用遞歸的方法，利用連通圖階數(shù)的”約簡(jiǎn)”來(lái)對(duì)其進(jìn)行研究日益得到重視，即保持圖的某種性質(zhì)，并使圖的階數(shù)

2、或邊數(shù)減少的一系列運(yùn)算的綜合。在這種背景下，圖的可收縮邊和可去邊被定義和廣泛研究。本文以連通圖中的可去邊作為研究對(duì)象，以期能夠?qū)M(jìn)一步了解連通圖的結(jié)構(gòu)及其構(gòu)造方法做出貢獻(xiàn)。
　　 本文主要研究6連通圖中可去邊的性質(zhì)及其在圈和生成樹(shù)中的分布情況。下面簡(jiǎn)單介紹一下本文的主要結(jié)果。
　　 首先我們給出可去邊的定義:
　　 設(shè)圖G為6連通圖，e=xy是圖G的一條邊。對(duì)圖G進(jìn)行以下運(yùn)算:
　　 (1)從圖G中刪去邊

3、e=xy，得到圖G-e。
　　 (2)若存在點(diǎn)u∈{x，y}，使得u在圖G-e中是個(gè)5度點(diǎn)，則刪掉點(diǎn)u，并將點(diǎn)u的5個(gè)鄰點(diǎn)兩兩連結(jié)為K5。
　　 (3)若經(jīng)過(guò)(1)(2)運(yùn)算后的圖出現(xiàn)重邊，則刪除重邊以單邊代替，使之成為簡(jiǎn)單圖。
　　 我們將經(jīng)過(guò)(1)(2)(3)運(yùn)算得到的圖記為G(⊙)e。
　　 如果G(⊙)e仍舊是6連通圖，那么邊e稱為可去邊;否則稱為可不去邊。圖G的所有可去邊的集合記為ER(G)，所

4、有不可去邊的集合記為EN(G)。
　　 本文研究了6連通圖中可去邊的性質(zhì)及其在圈上的分布情況，得出下面的結(jié)論:
　　 結(jié)論1圖G為|G|≥11的6連通圖，且δ(G)≥7，則G的任意一個(gè)圈中至少有兩條可去邊。
　　 對(duì)于6連通圖中可去邊在生成樹(shù)和哈密頓圈上的分布情況，我們得到下面兩條結(jié)論:
　　 結(jié)論2圖G為|G|≥11的6連通圖，且δ(G)≥7，則G的任意生成樹(shù)中至少含兩條可去邊。
　　 結(jié)論3圖