3連通圖的可去邊.pdf

1、廣西師范大學(xué)碩士學(xué)位論文3連通圖的可去邊姓名：歐見平申請學(xué)位級別：碩士專業(yè)：基礎(chǔ)數(shù)學(xué)指導(dǎo)教師：蘇健基200001013 連通圖的可去邊概 要九七級基礎(chǔ)數(shù)學(xué)專業(yè)碩士研究生：歐見平導(dǎo)師：蘇健基數(shù)學(xué)歸納法在圖論中的廣泛應(yīng)用致使圖的”約簡”( r e d u c t i o n ) 日益受到重視．圖的”約簡”是指在保持圖的某種性質(zhì)的前提下使圖的階數(shù)或邊數(shù)減少的一系列運(yùn)算的總和，圖的邊收縮便是其中之一．自從一九六一年W —T U t t e 用可

2、縮邊給出了3連通圖的結(jié)構(gòu)特征【7 】，一九八O 年C ．T h o m a s s e n [ 8 ] 用可縮邊給出了K u r a t o w s k i 定理的一個(gè)簡短證明之后，圖論界有許多著名專家，學(xué)者對不同的約簡方法進(jìn)行了有益的探索和研究，其中有W ．M a d e r [ 9 ] , B ．J a c k s o n [ 1 0 ] ，L ．A ．G o d d y n [ 1 1 ] 等人的可去圈( R e m o v a

3、b l e c i r c u i t s ) ；W ．M c c u a i g [ 1 2 】的可收縮3 邊形( c o n t r a c t i b lt r i p l e ) ；K i y o s h iA n d o 和A t s u s iK a n e k o [ 1 3 ] 的雙收縮對f o i ．c o n t r a c t i b l ep a i r ) ，M ．K r i e s e l l [ 1 4 ]

4、 ㈣收縮( c o n t r a c t i b l e n o n - e d g e s ) 以及D ．W ．B a m e t t e [ 1 5 ] 的可收縮圈( c o n t r a c t i b l ec i r c u i t s )有些方式，N I l 5 ] ，已經(jīng)有重要的應(yīng)用．值得注意的是，上述約簡方法中有許多是基于3 連通圖的．作者主要研究了3 連通圖的可去邊( R e m o v a b l e e d g

5、 e si n3 - c o n n e c t e d g r a p h s ) ，它與3 連通圖中的一種約簡方式有密切的聯(lián)系，其實(shí)早在一九八八年，J ．L ．F o u q u e t [ 6 】等人就提出了“3 連通圖的可去邊”這一概念的雛形．但其到一九九O 年，D e r e kA ．H o l t o n [ 1 ] 才給出這一概念的精確定義．在簡單無向有限圖G 中作如下運(yùn)算：( 1 ) 刪除G 的一條邊e = M ，得G

6、- e ．( 2 ) 如果存在點(diǎn)H E { x ，y ) ，使得u 在G - e 中的鄰域N o - c ( u ) = { W ，v ) ，則用邊、w代替G - e 中的路伽v ．( 3 ) 經(jīng)過( 1 ) ，( 2 ) 運(yùn)算所得到的圖G ’如果有重邊，則刪除G ’的重邊，使G ’的每一邊的重?cái)?shù)都為一．用G O e 表示G 經(jīng)過( 1 ) ，( 2 ) ，( 3 ) 運(yùn)算所得到的圖．如果G O e 是3 連通圖，則稱e是G 的可去邊，