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

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

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

【共引文獻(xiàn)】

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

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

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

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

4 郭紀(jì)云;;每棵非平凡樹至少有兩片葉子的證法研究[J];長(zhǎng)沙大學(xué)學(xué)報(bào);2011年05期

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

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

7 陳彬;于繼來(lái);;電力網(wǎng)絡(luò)拓?fù)浞治雠c源流路徑鏈生成算法[J];電力系統(tǒng)及其自動(dòng)化學(xué)報(bào);2012年01期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1152714