連通圖中的可去邊和可收縮邊.pdf

1、圖的連通性是圖的最基本的性質(zhì)之一，是圖論中重要的研究課題．連通圖與網(wǎng)絡(luò)模型和組合優(yōu)化聯(lián)系密切，使它擁有很強的應(yīng)用背景．連通圖中的可去邊和可收縮邊是探討圖的結(jié)構(gòu)、遞歸的證明圖的某些性質(zhì)的重要工具，對它們的研究具有重要的理論價值和應(yīng)用價值．本文選擇連通圖中的可去邊和可收縮邊作為研究對象，就是希望通過努力能夠?qū)M一步了解連通圖的結(jié)構(gòu)以及找出其構(gòu)造方法的研究工作有所幫助．本文主要研究連通圖中可去邊和可收縮邊的性質(zhì)以及它們在特定子圖上的分布情況．

2、下面簡單介紹一下本文的主要結(jié)果． 對于連通圖中的可去邊，本文將已有的4連通圖中可去邊在圈上分布的部分研究成果作了改進，并首次提出了6連通圖中可去邊的一些性質(zhì)，主要結(jié)果如下： 定理2．2.10．設(shè)G是4連通圖，C為G中任意的圈，若圈C不與G的任何階為2的邊點割斷片相交，則C上至少有兩條可去邊． 定理2．3.2.設(shè)G是6連通圖，|G|≥11，δ(G)≥7，xy∈E<,N>(G)，(xy，S；A，B)為其對應(yīng)的分離分解

3、，其中x∈A，y∈B，則白(G[S])∈E<,R>(G)． 定理2．3.3.設(shè)G是6連通圖，|G|≥11，G的邊點割原子的階至少為3，xy∈E<,N>(G)，(xy，S；A，B)為其對應(yīng)的分離分解，其中x∈A，y∈B，則E(G[S])∈E<,R>(G)． 對于連通圖中的可收縮邊，本文將已有的4連通圖中可收縮邊在完美匹配上的分布結(jié)果進行了改進，并首次給出了5連通圖中可收縮邊在完美匹配上的分布情況，還得到了一個與6連通圖中可

4、收縮邊相關(guān)的結(jié)論，主要結(jié)果如下： 定理3．2.1．設(shè)G是階大于7的4連通圖，M是G的一個完美匹配，且M上的任意一條邊不在三角形上，則M上至少有兩條可收縮邊． 定理3.3.2．設(shè)G是階大于9的5連通圖，M是G的一個完美匹配，且M上的任意一條邊不在三角形上，則M上至少有兩條可收縮邊． 定理3.3.4．設(shè)G是階大于11的5連通圖，M是G的一個完美匹配，若圖G的任意斷片的階都大于2，則M上至少有兩條可收縮邊． 定