3連通圖中圈上可去邊的一些性質(zhì).pdf

1、圖的連通性是圖最基本的性質(zhì)之一，是圖論中重要的研究課題，連通圖與網(wǎng)絡(luò)模型和組合優(yōu)化聯(lián)系密切，使它具備很強(qiáng)的應(yīng)用背景.特別是近二十年來，隨著計算機(jī)與網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，這一聯(lián)系日益密切.連通圖中的可收縮變與可去邊是探討圖的結(jié)構(gòu)特征，尋求以遞歸方式證明圖的某些性質(zhì)的重要工具，對它們的研究具有重要的理論價值和應(yīng)用價值.隨著數(shù)學(xué)歸納法在圖論中的廣泛應(yīng)用，圖的“簡約”日益受到重視.它足指在保持圖的某種性質(zhì)的前提下使圖的階數(shù)或邊數(shù)減少的一系列運(yùn)算的

2、綜合.圖的可縮邊與可去邊就是在這種背景下產(chǎn)生的.
　　 本文主要研究3連通圖中可去邊的性質(zhì)，以及可去邊在圈上的分布情況.下面簡單介紹一下本文的主要結(jié)果.如無特別說明，文中的圖G均為簡單圖.
　　 首先我們給出可去邊與不可去邊的定義.定義如下：
　　 對于3連通圖中的一條邊e=xy進(jìn)行如下運(yùn)算：
　　 (1)從圖G中刪除邊e=xy，得到G-e.
　　 (2)如果存在一點(diǎn)u∈{x,y}，使得“在G-e

3、中的臨域NG-e(u)={w,v}，則用邊Wv代替G-e中的路WUV.
　　 (3)經(jīng)過(1)(2)運(yùn)算所得的圖G’如果有重邊，則刪除G’的重邊，使G’的每條邊的重數(shù)都為一.
　　 用GOe表示G經(jīng)過(1)(2)(3)運(yùn)算所得到的圖，如果GOe是3連通圖，則稱e是G的可去邊，或稱e可去；否則稱e是G的不可去邊或稱e不可去.用ER(G)表示G的可去邊集，eR(G)表示G的可去邊數(shù)，EN(G)和印(G)分別表示G的不可去邊集

4、和不可去邊數(shù).
　　 對于3連通圖中圈上的可去邊分布，本文對已有的部分研究成果進(jìn)行了推廣，得出下述兩條結(jié)論：
　　 定理3.1如果C是不同構(gòu)于W8的3連通圖G的一個7圈，那么：
　　 |E(C)nER(G)|≥l；
　　 或者G中存在同構(gòu)于W**s的子圖，且C? W**.其中dG(xi)=dG(Yi)=3，i=2，3，4；dG(a）≥4；dG(b)≥4.
　　 定理3.2如果C是不同構(gòu)于W9的3連