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

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

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

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

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