3連通圖的可去邊.pdf

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

2、縮邊給出了3連通圖的結構特征【7 】，一九八O 年C ．T h o m a s s e n [ 8 ] 用可縮邊給出了K u r a t o w s k i 定理的一個簡短證明之后，圖論界有許多著名專家，學者對不同的約簡方法進行了有益的探索和研究，其中有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 ] ，已經有重要的應用．值得注意的是，上述約簡方法中有許多是基于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)系，其實早在一九八八年，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 中作如下運算：( 1 ) 刪除G 的一條邊e = M ，得G

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