關于5連通圖中可去邊的一些性質.pdf

1、圖的連通性是圖的最基本的性質之一，是圖論中重要的研究課題，近二十年來更是圖論的研究熱點。連通圖與網絡模型和組合優(yōu)化聯系密切，使它擁有很強的應用價值和理論價值。連通圖中的可去邊和可收縮邊是探討圖的結構、遞歸的證明圖的某些性質的重要工具，對它們的研究具有重要的理論價值和應用價值。本文選擇連通圖中的可去邊作為研究對象，就是希望通過努力能夠對進一步了解連通圖的結構以及找出其構造方法的研究工作有所幫助。本文主要研究連通圖中可去邊的性質以及它們在特

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

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