6連通圖中的可收縮邊.pdf

1、早在200多年前,人類已經(jīng)開始涉足圖論的研究領(lǐng)域.1736年,Euler用圖的方法解決了哥尼斯堡七橋問題,發(fā)表了第一篇圖論論文.二十世紀(jì)三十年代以來,圖論在科學(xué)界異軍突出,活躍非凡.哈密頓圈問題、四色問題、中國郵遞員問題等等,這些都是圖論中非常重要的問題,而且在解決信息和計算機(jī)科學(xué)、生物學(xué)、化學(xué)等學(xué)科問題上圖論也已經(jīng)顯示出很大的優(yōu)越性.與此同時,在社會科學(xué)以及工程技術(shù)領(lǐng)域中,圖論也有著廣泛的運(yùn)用.
　　 圖的連通性是圖的最基本的

2、性質(zhì)之一,連通度是分析和刻畫圖的有力工具,有大量的問題可以歸結(jié)為圖的條件邊連通問題,所以這方面是圖論的熱點研究領(lǐng)域.目前,互聯(lián)網(wǎng)絡(luò)已經(jīng)與人們的工作、日常生活等方面息息相關(guān),連通圖與網(wǎng)絡(luò)模型和組合優(yōu)化的密切聯(lián)系,使它擁有很強(qiáng)的應(yīng)用背景.K-連通圖的K-可去邊和K-可收縮邊的存在對于探討圖的結(jié)構(gòu)、證明圖的某些性質(zhì)有著重要的應(yīng)用,所以,對于它們的研究具有非常重要的理論價值和應(yīng)用價值.本論文選擇連通圖中的可收縮邊作為研究對象,目的就是通過努力能

3、夠進(jìn)一步的了解連通圖的結(jié)構(gòu)以及找出其構(gòu)造方法,對以后的研究工作有所幫助.
　　 本論文主要研究6-連通圖中可收縮邊的性質(zhì)以及它們在特定子圖上的分布情況.下面先簡單介紹一下本文的主要結(jié)果.
　　 第二章主要研究6-連通圖完美匹配上可收縮邊的分布情況,得到如下結(jié)論:
　　 定理設(shè)G是階大于12的6-連通圖,M是G的一個完美匹配,若圖G的任意斷片的階都大于3,則M上至少有兩條可收縮邊.
　　 第三章在第二章研究

4、基礎(chǔ)上,繼續(xù)探索6-連通圖中的可收縮邊,得到6-連通圖最長圈上可收縮邊的分布情況,結(jié)論如下:
　　 定理設(shè)G是一個任意斷片的階都大于2的6-連通圖,C=x1x2…xmx1是G的任意最長圈,若C上的任意頂點xi都滿足以下條件之一,則G至少包含兩條可收縮邊.
　　 (1)d(x1)≥7;
　　 (2)d(x1)=6,則V(C)中無3-圈包含它.
　　 不存在K-可收縮邊的非完全K-連通圖稱為收縮臨界K-連通圖

5、.收縮臨界K-連通圖的研究也是目前比較熱門的一個課題,本文第四章給出了收縮臨界6-連通圖6度點的分布及斷片的相應(yīng)結(jié)果.
　　 定理設(shè)G是收縮臨界6-連通圖,x是G中任意一點,設(shè)A是一個x-原子,記NA=TA,N(x)∩TA≠φ,則A∩TA中有與x相鄰的6度點或兩點的距離為2.
　　 定理設(shè)G是收縮臨界6-連通圖,x∈V(G),F是G中的斷片,且x∈N(F).若|F|≥4,|-F|≥3且N(x)∩F={x1},則存在一點x