關(guān)于5連通圖中可去邊的一些性質(zhì).pdf

1、圖的連通性是圖的最基本的性質(zhì)之一，是圖論中重要的研究課題，近二十年來(lái)更是圖論的研究熱點(diǎn)。連通圖與網(wǎng)絡(luò)模型和組合優(yōu)化聯(lián)系密切，使它擁有很強(qiáng)的應(yīng)用價(jià)值和理論價(jià)值。連通圖中的可去邊和可收縮邊是探討圖的結(jié)構(gòu)、遞歸的證明圖的某些性質(zhì)的重要工具，對(duì)它們的研究具有重要的理論價(jià)值和應(yīng)用價(jià)值。本文選擇連通圖中的可去邊作為研究對(duì)象，就是希望通過(guò)努力能夠?qū)M(jìn)一步了解連通圖的結(jié)構(gòu)以及找出其構(gòu)造方法的研究工作有所幫助。本文主要研究連通圖中可去邊的性質(zhì)以及它們?cè)谔?/p>

2、定子圖上的分布情況。下面簡(jiǎn)單介紹一下本文的主要結(jié)果。 首先，我們給出幾個(gè)子圖的定義：定義令G是一個(gè)5連通圖，H是圖G的一個(gè)子圖，且圖H由點(diǎn)集V(H)={x，y，a，b，c，z，w)和邊集E(H)={xy，xa，xb，xc，xz，ab，ac，az，aw}組成，其中點(diǎn)x和a的鄰點(diǎn)都只有5個(gè)，我們稱這樣一個(gè)子圖為*1。類似的，我們給出其它子圖的點(diǎn)集和邊集分別如下，它們對(duì)應(yīng)的被稱為*2，*3： 結(jié)論：1設(shè)圖G是一個(gè)5連通圖，且階

3、數(shù)|G|≥10，對(duì)于其中一條不可去邊e=xy，設(shè)其對(duì)應(yīng)的分離組為(e，S；A，B)。A是一個(gè)2邊點(diǎn)割原子，x∈A，y∈B。若存在另一條不可去邊，f=xz(z≠y)，我們給出它的分離組(f,T;G,D))，其中x∈C，z∈D，則圖G必然包含*1，*2之一作為其子圖。 結(jié)論：2設(shè)圖G是一個(gè)5連通圖，它的階數(shù)|G|≥10，若圖G的一個(gè)圈C滿足，|E(C)∩ER(G)|=0，則圖G必然包含木*1，*2，*3之一作為其子圖。 結(jié)論