發(fā)布時(shí)間：2017-07-08 17:30

  本文關(guān)鍵詞：平面圖的邊染色問題

  更多相關(guān)文章： 平面圖 邊染色 權(quán)轉(zhuǎn)移方法

【摘要】：圖G的k-邊染色是用k種顏色對(duì)圖G的邊集合的元素進(jìn)行著色,使得相鄰的兩條邊染不同的顏色,即存在一個(gè)映射φ：E(G)→{1,2,...,k},對(duì)G中任意兩條相鄰的邊e1和e2,有φ(e1)≠φ(e2).圖G的邊色數(shù),用χ'(G)表示,是使G存在k-邊染色的最小整數(shù)kVizing定理指出：對(duì)于任意簡(jiǎn)單圖G,我們有χ'(G)=△(G)或△(G)+1.如果χ'(G)=△(G),圖G稱為第一類的,如果χ'(G)=△(G)+1,圖G稱為第二類的Vizing證明了△≥8的平面圖是第一類的,并且提出著名的Vizing猜想：每個(gè)最大度不小于6的平面圖是第一類的.對(duì)△=7的情形已由S anders和Zhao以及Zhang獨(dú)立證明.因此,Vizing猜想只剩下△=6的情形還沒有證明.Ni證明了最大度為6且不含弦-k-圈(4≤k≤7)的平面圖是第一類的.我們證明了：最大度為6,且不含弦-8-圈的平面圖是第一類的.利用反證法,假如存在最大度為6,且不含弦-8-圈的平面圖G是第二類的,不妨設(shè)G是臨界圖,對(duì)任意x∈V(G)∪F(G),定義權(quán)函數(shù)為ch(x)=d(x)-4,得到所有頂點(diǎn)和面上的權(quán)值之和為-8,并設(shè)置了權(quán)值轉(zhuǎn)移規(guī)則,在權(quán)值重新分配的過程中,所有頂點(diǎn)和面的權(quán)值之和保持不變,對(duì)所有的頂點(diǎn)和面上的權(quán)值進(jìn)行重新分配后得到的新權(quán)值定義為ch',如果對(duì)任意的x∈V(G)∪F(G),都有ch'(x)≥0,就會(huì)得到矛盾：0≤∑x∈V(G)∪F(G)ch'(x)=∑x∈V(G)∪F(G)ch(x)=-80,從而證明不存在這樣的反例.我們發(fā)現(xiàn)：對(duì)于最大度為6,且不含弦-8-圈的臨界圖,存在關(guān)聯(lián)3-面的個(gè)數(shù)較多且關(guān)聯(lián)6個(gè)面的度數(shù)之和較小的6-點(diǎn),在權(quán)值轉(zhuǎn)移的過程中,這類6-點(diǎn)傳遞給它的鄰點(diǎn)以及它關(guān)聯(lián)的3-面的權(quán)值之和大于這類6-點(diǎn)從它所關(guān)聯(lián)的面上得到的權(quán)值之和,我們通過對(duì)這類6-點(diǎn)的某些鄰點(diǎn)的結(jié)構(gòu)進(jìn)行研究,發(fā)現(xiàn)這些鄰點(diǎn)所關(guān)聯(lián)的面的度數(shù)較大,因此,在設(shè)置權(quán)轉(zhuǎn)移規(guī)則時(shí),可安排這類6-點(diǎn)從它的某些鄰點(diǎn)上得值.權(quán)值重新分配后,我們驗(yàn)證了任意頂點(diǎn)和面上的權(quán)值都不小于0,反證法證明了我們的結(jié)論.2≤△≤5的平面圖既有第一類圖,也有第二類圖,Ni證明了：最大度為5且不含弦-4-圈和弦-k-圈(k=5,6)的平面圖是第一類的.我們證明了：最大度為5且不含弦-4-圈和弦-7-圈的平面圖是第一類的.我們分別對(duì)最大度為5且不含弦-4-圈和弦-7-圈的臨界圖的每個(gè)頂點(diǎn)以及它的鄰點(diǎn)所關(guān)聯(lián)的面的情況進(jìn)行研究,并給出了適當(dāng)?shù)亩x和權(quán)轉(zhuǎn)移規(guī)則,反證法證明了我們的結(jié)論.
【關(guān)鍵詞】：平面圖 邊染色 權(quán)轉(zhuǎn)移方法
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5
【目錄】：

• 中文摘要6-8
• 英文摘要8-10
• 第一章 緒論10-17
• §1.1 基本定義10-12
• §1.2 研究背景12-17
• 第二章 最大度為6且不含弦-8-圈的平面圖的邊染色問題17-34
• §2.1 結(jié)構(gòu)與性質(zhì)17-25
• §2.2 主要定理及其證明25-33
• §2.3 小結(jié)33-34
• 第三章 最大度為5且不含弦-4-圈和弦-7-圈的平面圖的邊染色問題34-45
• §3.1 結(jié)構(gòu)與性質(zhì)34-39
• §3.2 主要定理及其證明39-44
• §3.3 小結(jié)44-45
• 第四章 結(jié)論和展望45-47
• 參考文獻(xiàn)47-50
• 致謝50-51
• 附表51

【相似文獻(xiàn)】

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

1 盧建立;任鳳霞;馬美琳;;中間圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色[J];河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年05期

2 馬生全,張忠輔,姚兵,李敬文;C_(3n)~2,C_(4n)~2鄰點(diǎn)可區(qū)別的全染色[J];蘭州鐵道學(xué)院學(xué)報(bào);2003年04期

3 李敬文;強(qiáng)會(huì)英;張忠輔;王文杰;王治文;;高度圖的鄰點(diǎn)可區(qū)別的全染色界的一點(diǎn)注[J];蘭州交通大學(xué)學(xué)報(bào);2006年01期

4 王顏妮;王麗偉;劉萍;;幾類圖的鄰點(diǎn)可區(qū)別的全染色[J];科學(xué)技術(shù)與工程;2007年13期

5 王雅琴;劉西奎;王英;;一些圖的鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色[J];大學(xué)數(shù)學(xué);2008年04期

6 劉海濤;;C_(5m)×C_(5n)圖的鄰點(diǎn)可區(qū)別的邊染色[J];河西學(xué)院學(xué)報(bào);2008年02期

7 卞西燕;苗連英;尚華輝;段春燕;馬國(guó)翼;;圖的鄰點(diǎn)可區(qū)別邊劃分(英文)[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

8 鄭純;劉煥平;;扇和輪的鄰點(diǎn)強(qiáng)可區(qū)別全染色[J];哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào);2009年05期

9 嚴(yán)謙泰;;k-方圖的一般鄰點(diǎn)可區(qū)別邊染色[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年03期

10 嚴(yán)謙泰;嚴(yán)楷;;關(guān)于圖的一般鄰點(diǎn)可區(qū)別邊染色[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2010年24期

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

1 李莉;耿顯民;;一類隨機(jī)圖的鄰點(diǎn)度數(shù)和[A];第十一屆中國(guó)不確定系統(tǒng)年會(huì)、第十五屆中國(guó)青年信息與管理學(xué)者大會(huì)論文集[C];2013年

2 曹淵;郭永輝;王鐵良;田宙;;自然鄰點(diǎn)插值方法在材料狀態(tài)方程數(shù)據(jù)庫(kù)開發(fā)中的應(yīng)用[A];中國(guó)計(jì)算力學(xué)大會(huì)'2010（CCCM2010）暨第八屆南方計(jì)算力學(xué)學(xué)術(shù)會(huì)議（SCCM8）論文集[C];2010年

3 劉君;趙傳成;任志國(guó);包世堂;李敬文;張忠輔;;C_m·F_n的鄰點(diǎn)可區(qū)別的邊染色[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

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

1 孔海榮;區(qū)組長(zhǎng)為4的二維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)[D];河北師范大學(xué);2008年

2 黃丹君;平面圖的鄰點(diǎn)可區(qū)別染色與點(diǎn)蔭度[D];蘇州大學(xué);2012年

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

1 劉配配;平面圖的非正常染色[D];浙江師范大學(xué);2015年

2 黃晨悅;一類區(qū)組長(zhǎng)為5的一維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)的存在性[D];河北師范大學(xué);2016年

3 李曉麗;區(qū)組長(zhǎng)為5的二維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)[D];河北師范大學(xué);2016年

4 張曉望;平面圖的邊染色問題[D];山東大學(xué);2016年

5 李瓊;圖的一般鄰點(diǎn)可區(qū)別色指標(biāo)[D];西北師范大學(xué);2008年

6 趙新梅;圖的鄰點(diǎn)可區(qū)別正常邊染色的一些結(jié)果[D];西北師范大學(xué);2006年

7 王雅琴;圖的關(guān)聯(lián)著色與鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色[D];山東科技大學(xué);2007年

8 劉萍;圖的鄰點(diǎn)可區(qū)別的全染色[D];山東師范大學(xué);2008年

9 王倩;若干圖的鄰點(diǎn)可區(qū)別關(guān)聯(lián)染色[D];西北民族大學(xué);2011年

10 張彩霞;幾類圖的鄰點(diǎn)可區(qū)別均勻E-全染色[D];蘭州交通大學(xué);2015年

，

本文編號(hào)：535618