發(fā)布時間：2017-11-07 14:05

  本文關(guān)鍵詞：關(guān)于邊染色臨界圖有關(guān)性質(zhì)的研究

  更多相關(guān)文章： 臨界圖 邊染色 獨立數(shù) 差值轉(zhuǎn)移法

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

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

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

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

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

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

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

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

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

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

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

10 張民;賀仁睦;許津津;陶華;石巖;;圖論在BPA模型向PSCAD模型自動轉(zhuǎn)換中的應(yīng)用[J];電網(wǎng)技術(shù);2012年06期

中國重要會議論文全文數(shù)據(jù)庫 前1條

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

中國博士學位論文全文數(shù)據(jù)庫 前10條

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

2 白躍偉;結(jié)構(gòu)造型技術(shù)及其在機械三維CAD中的應(yīng)用[D];華中科技大學;2004年

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

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

5 秦寧寧;無線傳感器網(wǎng)絡(luò)柵欄覆蓋的研究[D];江南大學;2008年

6 賈玉福;基于資源受限的無線傳感器網(wǎng)絡(luò)關(guān)鍵問題研究[D];華中科技大學;2007年

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

8 王靜;網(wǎng)絡(luò)編碼理論及其應(yīng)用的研究[D];西安電子科技大學;2009年

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

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

中國碩士學位論文全文數(shù)據(jù)庫 前10條

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

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

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

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

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

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

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

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

9 季開青;基于軸輻式網(wǎng)絡(luò)的應(yīng)急物資調(diào)度問題研究[D];遼寧科技大學;2010年

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

，

本文編號：1152714