【摘要】：對一個圖G進(jìn)行正常邊染色,如果圖G中的每一個頂點v所關(guān)聯(lián)的邊的顏色數(shù)是連續(xù)的或者說所染的顏色數(shù)可以構(gòu)成一個整數(shù)區(qū)間,那么這個圖就是一個可區(qū)間邊染色圖.這個問題源于學(xué)校在召開家長會時,想提前安排好家長與老師的咨詢時間,要求每組會議時間一定,所有參加會議的老師構(gòu)成集合A,所有的家長構(gòu)成集合B,集合A與B便是二部圖的二部頂點集,如果某位老師與某位家長要見面則連邊,此時對這個二部圖邊進(jìn)行染色,顏色數(shù)是整數(shù),每條邊的色數(shù)就是雙方約定的見面時間,安排完希望不管是家長還是老師結(jié)束一個見面會議以后可以直接進(jìn)入下一個會議,兩者都不用浪費時間等待,也即讓這個二部圖的每個點關(guān)聯(lián)邊的顏色數(shù)是連續(xù)的即可。如果給定一個圖,判斷這個圖是否是一個可區(qū)間邊染色圖,這是非常困難的一項任務(wù).事實上,現(xiàn)在已經(jīng)證明了一個二部圖是否有一個區(qū)間邊染色,這是一個NP-完備的問題.在這個課題中,我們主要整理了一些現(xiàn)在已經(jīng)知道的關(guān)于圖有區(qū)間邊染色的一些結(jié)果,并且針對(a,b)-雙正則二部圖,在論文第二章做了一些結(jié)果,我們給出了一個(3,4)-雙正則二部圖有區(qū)間染色的一個充分條件,以及關(guān)于(a,ka)-,(a,3a)-,(4,4k)-雙正則二部圖有區(qū)間邊染色的條件。隨著對二部圖的區(qū)間邊染色的研究,又有人開始對三部圖的區(qū)間邊染色情況做研究,在第三章中,我們主要得到了幾類特殊的完全三部圖K_(l,m,n)區(qū)間染色的結(jié)果,例如K_(2,m,m),K_(l,m,k(l+m))等.論文在最后一章則介紹了以后工作的方向及下一步所需要解決的問題。
【學(xué)位授予單位】：江蘇師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 徐森;徐秀芳;花小朋;皋軍;徐靜;;一種基于二部圖譜劃分的聚類集成方法[J];控制與決策;年期

2 喬曉云;;二部圖的Resolvent Estrada指標(biāo)的界[J];山西大同大學(xué)學(xué)報(自然科學(xué)版);2017年02期

3 牟谷芳;;有向通弦二部圖的最小秩問題研究[J];樂山師范學(xué)院學(xué)報;2017年08期

4 耿顯亞;趙紅錦;徐李立;;二部圖的距離k次方和問題（英文）[J];數(shù)學(xué)雜志;2017年06期

5 葛志鵬;嚴(yán)廣樂;張國亮;;基于蟻群聚類的二部圖網(wǎng)絡(luò)推薦算法[J];信息技術(shù);2016年03期

6 李碩;顏謹(jǐn);陳文雅;;均衡二部圖中點不交的4-圈和6-圈（英文）[J];數(shù)學(xué)進(jìn)展;2015年01期

7 孫靜;胡智全;;平衡二部圖哈密爾頓性的一個充分條件[J];應(yīng)用數(shù)學(xué)學(xué)報;2015年05期

8 柳俊;周斌;黃九鳴;;基于二部圖投影的微博事件關(guān)聯(lián)分析方法研究[J];信息網(wǎng)絡(luò)安全;2014年09期

9 李立峰;劉三陽;羅清君;;弦二部圖的概念格表示[J];電子學(xué)報;2013年07期

10 陳宏宇;張麗;;給定控制數(shù)的連通二部圖的最大邊數(shù)[J];山東大學(xué)學(xué)報(理學(xué)版);2012年08期

相關(guān)會議論文 前7條

1 柳俊;周斌;黃九鳴;;基于二部圖投影的微博事件關(guān)聯(lián)分析方法研究[A];第29次全國計算機(jī)安全學(xué)術(shù)交流會論文集[C];2014年

2 常迎香;;一類無完美匹配的二部圖[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（中卷）[C];2004年

3 王國霞;劉賀平;李擎;;二部圖影射及其在推薦系統(tǒng)中的應(yīng)用[A];第25屆中國控制與決策會議論文集[C];2013年

4 李小強(qiáng);張寧;;基于鄰接矩陣的二部圖的判定方法[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

5 姚家保;古天龍;徐周波;;二部圖無權(quán)最大匹配的符號OBDD算法[A];2005年全國理論計算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

6 吳修國;韓作生;許崇敬;林騰;;分布式教務(wù)監(jiān)考排定系統(tǒng)的研究與設(shè)計[A];山東省計算機(jī)學(xué)會2005年信息技術(shù)與信息化研討會論文集（一）[C];2005年

7 李盛;;基于協(xié)同聚類的圖像分割[A];第十四屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集[C];2008年

相關(guān)博士學(xué)位論文 前10條

1 王洪偉;二部圖的匹配強(qiáng)迫數(shù)[D];蘭州大學(xué);2008年

2 孫靜;二部圖參數(shù)與圈型結(jié)構(gòu)研究[D];華中師范大學(xué);2014年

3 邊紅;圖中的若干極值問題[D];廈門大學(xué);2008年

4 劉敏;圖中結(jié)構(gòu)及相關(guān)參數(shù)研究[D];華中師范大學(xué);2016年

5 鄧凱;圖的匹配強(qiáng)迫譜與匹配反強(qiáng)迫譜研究[D];蘭州大學(xué);2016年

6 郇瀟;圖中匹配的可擴(kuò)性研究[D];南開大學(xué);2010年

7 鄒青松;圖包含指定長度的圈和泛弧問題的研究[D];山東大學(xué);2011年

8 李良辰;圖中Z_3-連通和處處非零3-流問題的研究[D];華中師范大學(xué);2012年

9 張光軍;圖的特下與度序列[D];上海交通大學(xué);2012年

10 馬麗;素數(shù)冪與2倍素數(shù)冪階局部本原圖[D];云南大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 井普寧;幾類特殊圖的區(qū)間邊染色[D];江蘇師范大學(xué);2018年

2 朱高茲;基于協(xié)同過濾和加權(quán)二部圖的推薦算法研究[D];吉林大學(xué);2017年

3 許梅;基于二部圖的事件建模及分析[D];北京郵電大學(xué);2017年

4 丁立佳;二部圖完美匹配計數(shù)與禁位排列[D];大連交通大學(xué);2014年

5 胡琳;二部圖的列表著色問題[D];新疆大學(xué);2004年

6 孫曉萌;基于社團(tuán)劃分和加權(quán)二部圖網(wǎng)絡(luò)的個性化推薦算法研究[D];河北工業(yè)大學(xué);2015年

7 張文琦;均衡二部圖中的2-因子[D];山東理工大學(xué);2010年

8 馮文麗;關(guān)于二部圖的兩個結(jié)果[D];山西大學(xué);2005年

9 楊帆;（3，，4）-雙向正則二部圖的區(qū)間著色[D];華中師范大學(xué);2008年

10 郭趙強(qiáng);低密度校驗碼二部圖構(gòu)造算法研究[D];西安電子科技大學(xué);2009年

本文編號：2602641