本文關鍵詞：關于邊染色臨界圖有關性質的研究

  更多相關文章： 臨界圖 邊染色 獨立數 差值轉移法

【摘要】：圖論相對于其他數學分支學科來說,迄今為止只有200多年的歷史。本文研究的邊染色臨界圖的問題是圖的染色問題的一個分支,也是圖論的主要研究對象之一。最大度為D的圖G,其邊色數'c(G)要么是D,要么是D+1。如果'c(G)=D,則稱圖G是第一類的;如果'c(G)=D+1,則稱圖G是第二類的。如果圖G是連通的、第二類的,且對每條邊''c(G-e)c(G),則稱G是臨界圖。用'(G)ac表示。Vizing(1964)和Gupta(1966)各自獨立的得出一個關于圖的邊色數重要定理(Vizing Theorem):對任意最大度為D的簡單圖,'c(G)=D或'c(G)=D+1。1960年,Vizing提出了臨界圖獨立數猜想(Vizing’s Independence Number Conjecture):若G是n階D臨界圖,則有()2VaG￡,目前為止仍沒有被完全證明出來。本文在前人研究的基礎上,通過修改某些限制條件研究了邊染色臨界圖的邊數和獨立數的問題,共分4章.第1章主要對本課題的研究背景、研究現狀和基礎概念等做了簡單介紹.第2章討論了對于不含2度點邊染色臨界圖的獨立數的范圍。利用差值轉移方法證明了證明當最大度D?{9,10}時,3 3()5 3aG VD-￡D-和當D?{11,L,46},獨立數15 42()23 42aG VD-￡D-。第3章討論了邊染色臨界圖的邊數的新下界,通過運用差值轉移的方法證明不含3-圈的5-臨界圖和6-臨界圖邊數的新下界分別為12156m3n和13352m3n,比目前最好的結果157m3n和3313m3n分別提高了128n和126n。第4章提出了一些值得進一步研究的問題.
【學位授予單位】：中國礦業(yè)大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【共引文獻】

中國期刊全文數據庫 前10條

1 張彬;袁叢鑫;司璇;金飛;;基于圖論的數字圖像邊緣檢測算法[J];中國傳媒大學學報(自然科學版);2011年03期

2 張忠海;李端玲;廖啟征;;柔性變胞機構的拓撲結構表示及構態(tài)變換分析[J];北京郵電大學學報;2010年03期

3 涂冰英;;實時動態(tài)最佳路徑的實現方法[J];測繪信息與工程;2006年03期

4 郭紀云;;每棵非平凡樹至少有兩片葉子的證法研究[J];長沙大學學報;2011年05期

5 葉玉民,周立新,胡小倩;關于最佳糧庫地址的選擇[J];東北電力學院學報;2001年01期

6 解大;何恒靖;常喜強;姚秀萍;;電力系統(tǒng)低頻減載的同調分區(qū)定義與割集算法[J];電力系統(tǒng)及其自動化學報;2011年03期

7 陳彬;于繼來;;電力網絡拓撲分析與源流路徑鏈生成算法[J];電力系統(tǒng)及其自動化學報;2012年01期

8 陶華;楊震;張民;楊俊新;賀仁睦;石巖;;基于深度優(yōu)先搜索算法的電力系統(tǒng)生成樹的實現方法[J];電網技術;2010年02期

9 解大;何恒靖;常喜強;姚秀萍;;計及同調分區(qū)和全局優(yōu)化的電力系統(tǒng)低頻減載方案[J];電網技術;2010年06期

10 張民;賀仁睦;許津津;陶華;石巖;;圖論在BPA模型向PSCAD模型自動轉換中的應用[J];電網技術;2012年06期

中國重要會議論文全文數據庫 前1條

1 方崇惠;王偉;方波青;;南水北調東荊河節(jié)制工程復雜分汊河網水力分析[A];水文泥沙研究新進展——中國水力發(fā)電工程學會水文泥沙專業(yè)委員會第八屆學術討論會論文集[C];2010年

中國博士學位論文全文數據庫 前10條

1 邱宇;基于雙邊濾波的圖像去噪及銳化技術研究[D];重慶大學;2011年

2 白躍偉;結構造型技術及其在機械三維CAD中的應用[D];華中科技大學;2004年

3 張多利;基于功能信息的驗證工程學及若干驗證技術研究[D];合肥工業(yè)大學;2005年

4 喬海泉;并行仿真引擎及其相關技術研究[D];國防科學技術大學;2006年

5 秦寧寧;無線傳感器網絡柵欄覆蓋的研究[D];江南大學;2008年

6 賈玉福;基于資源受限的無線傳感器網絡關鍵問題研究[D];華中科技大學;2007年

7 林德明;適應性Agent圖及其在復雜系統(tǒng)脆性分析中的應用[D];哈爾濱工程大學;2008年

8 王靜;網絡編碼理論及其應用的研究[D];西安電子科技大學;2009年

9 崔琳;石油化工過程HAZOP專家系統(tǒng)與集成研究[D];北京化工大學;2009年

10 何雙華;供水管網系統(tǒng)抗震可靠性分析及加固優(yōu)化研究[D];大連理工大學;2009年

中國碩士學位論文全文數據庫 前10條

1 王冰山;網絡兩端可靠性問題的研究[D];西安電子科技大學;2011年

2 武艷南;基于管理機制設計理論的應急協調系統(tǒng)設計及其應用[D];山東大學;2011年

3 鄭孝俊;基于感興趣區(qū)域的顱腦圖像處理與應用[D];安徽大學;2011年

4 趙琪;認知無線電網絡頻譜分配及共享算法研究[D];杭州電子科技大學;2010年

5 譚顯強;基于FPGA的3D圖形處理器IP核的設計與實現[D];南京航空航天大學;2010年

6 雷楊;基于凸形障礙物的注水管網優(yōu)化研究[D];中國石油大學;2011年

7 陶慧;赤峰市煙草公司物流配送路線優(yōu)化研究[D];吉林大學;2011年

8 顏寧;基于層次分析和搜索算法的博弈模型研究[D];東北大學;2009年

9 季開青;基于軸輻式網絡的應急物資調度問題研究[D];遼寧科技大學;2010年

10 秦波;發(fā)電廠電氣主接線可靠性研究與實踐[D];廣西大學;2002年

，

本文編號：1152714