3連通圖的某些子圖上的可去邊.pdf

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

2、產(chǎn)生的。 本文主要研究連通圖中可去邊和可收縮邊的性質(zhì)，以及它們?cè)?連通圖中的分布情況。如無(wú)特別說(shuō)明，文中的圖G均為簡(jiǎn)單圖。下面簡(jiǎn)單介紹一下本文的主要結(jié)果。 首先我們給出可去邊與不可去邊的定義。定義如下： 對(duì)于3連通圖中的一條邊e=xy進(jìn)行如下運(yùn)算： （1）從圖G中刪除邊e=xy，得到G—e． （2）如果存在一點(diǎn)u∈{x，y}，使得u，在G—e中的鄰域NG—e（u）={w，v），則用邊wv代替G—e

3、中的路wuv． （3）經(jīng)過(guò)（1）（2）運(yùn)算所得的圖G'如果有重邊，則刪除G'的重邊，使G'成為簡(jiǎn)單圖。 用Gθe表示G經(jīng)過(guò)（1）（2）（3）運(yùn)算所得到的圖。如果GθP是3連通圖，則稱e是G的可去邊，或稱e可去，否則稱e是G的不可去邊或稱e不可去。用ER（G）表示G的可去邊集，eR（G）表示G的可去邊數(shù)，EN（G），eN（G）分別表示G的不可去邊集和不可去邊數(shù)。 對(duì)于3連通圖中圈上的可去邊的分布，本文對(duì)已有的部分研

4、究成果進(jìn)行了改進(jìn)，得出了： 結(jié)論1 G是3連通圖，C是G中一個(gè)6圈。如果C上至多存在一組3個(gè)連續(xù)3度頂點(diǎn)，則|E（C）∩ER（G）|≥1． 結(jié)論2 G是3連通圖，υ（G）≥6，Cn是G中一個(gè)n圈。如果Cn上至多存在一組3個(gè)連續(xù)3度頂點(diǎn)，則|E（Cn）∩ER（G）|≥1． 對(duì)于3連通圖中生成樹外可去邊的分布，本文通過(guò)對(duì)3正則圖的研究，得出了： 結(jié)論3 G是一個(gè)3連通圖，υ（G）≥6，如果G上不存在2個(gè)連續(xù)3