圖的圈和路因子理論的若干結果及對平面圖中全染色猜想的研究.pdf

1、山東大學碩士學位論文圖的圈和路因子理論的若干結果及對平面圖中全染色猜想的研究姓名：耿建艷申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：顏謹20070508山東大學碩士學位論文無爪圖．無爪圖是一類非常有趣的圖，半無爪圖是無爪圖的放松．所以把在無爪圖中成立的結論推廣到半無爪圖中來研究是非常有意義的．圖的—個路因子就是指每—個分支都是一條路的—個生成子圖．給定一個正整數(shù)七，P > ^ ．因子就是指每個分支都至少含七個頂點的—個路因子．

2、G 的—個哈密頓圈是G 的包含G 中所有頂點的一個圈．G 的—個1 一因子是G 的—個1 ．正則支攆子圖，通常我們稱1 ．因子為完美對集或完美匹配．顯然G 的—個1 ．因子是覆蓋G 的所有頂點的—個邊集合．G 的—個參因子是G 的—個二正則支撐子圖，易見2 - 因子的每—個連通分支為—個圈．圖的七個獨立圈是指G 中七個頂點不相交的圈．圖的獨立圈、二因子和路因子問題是圖的因子理論中非常重要的—部分，也是圖的哈密頓圈理論的推廣和延伸．它是圖

3、論中非常有趣的一類問題，也是國內(nèi)外研究的熱門課題．其理論研究日益成熟和完善，麗且它在計算機科學、通信網(wǎng)絡設計等中都有重要應用．關于圖的獨立圈，2 - 因子和路因子理論的研究主要集中在以下幾個方面t 圖中含指定個數(shù)的獨立圈和2 _ 因子；含指定長度的獨立圈和參因子；圖中具有指定性質的獨立圈和參因子；具有指定性質的路因子等等．全文共分四章．第一章簡單介紹了圖論的基本概念，圈和路因子理論的歷史和發(fā)展狀況及一些已有的相關結論．這一章是第二章和第

4、三章的基礎．第二章討論了二部圖中包含指定頂點的獨立圈的部分結果．其主要結果如下l定理2 ．1 ．1 ．設k ≥2 。1 ≤J S 七，l ' t ≥2 知- I - 1 ．如果以，l ( G ) 芝撇z { 『紐乒1 ，n + 七} ，那么對任給的七個頂點饑，也，．．．，仇，G 含七個獨立圈a ，G ，．．．，倪使得。仇∈y ( Q ) ，l G l ≤6 。且{ G ，G ，．．．，o k } 中至少有8 個} 圈．定理2 ．

5、2 ．1 ．設奄≥1 。0 ≤s ≤k ，n ≥2 k ．如果6 ( G ) ≥徹{ 『羋1 ，f 羋1 ，r 警1 ) ’那么對任給的七個頂點饑，地，?，仇。G 含七個獨立圈a ，島，．．．，G 使得t 耽∈y ( c ：) ，且I G I = 4 ( 1 ≤t Ss ) ，I G I ≤6 ( s + 1 ≤i ≤詹) ．關于路因子的研究，2 0 0 2 年，K i y o ＆h iA n d o 等人證明了下面的結論t 如果圖G