本文關(guān)鍵詞：Halin圖消圈數(shù)及點(diǎn)染色問(wèn)題的研究

  更多相關(guān)文章： 圖 Halin圖 近正則Halin圖 最小消圈集 消圈數(shù) 點(diǎn)色數(shù)

【摘要】：圖論知識(shí)在電路的設(shè)計(jì)和計(jì)算機(jī)操作系統(tǒng)中預(yù)防出現(xiàn)死循環(huán)等一系列實(shí)際問(wèn)題中的應(yīng)用引發(fā)了對(duì)通過(guò)去掉圖中的一些點(diǎn)(當(dāng)然也去掉了與這些點(diǎn)相連的邊),從而破掉圖中所有圈的問(wèn)題的研究,也就是對(duì)消圈數(shù)問(wèn)題的研究.圖的最大誘導(dǎo)森林,圖的獨(dú)立數(shù)(最大獨(dú)立集的階數(shù))等問(wèn)題都與消圈數(shù)有密切關(guān)系,所以這一問(wèn)題的研究在圖論中起著十分重要的作用.要想更好的了解圖的性質(zhì)與結(jié)構(gòu),從研究圖的消圈數(shù)入手不失為一個(gè)好的突破口.著名的四色猜想被提出來(lái)后,引發(fā)了人們對(duì)圖的染色問(wèn)題的研究,被染色的對(duì)象逐漸地變得越來(lái)越廣泛,出現(xiàn)了點(diǎn)染色,邊染色,面染色,全染色,強(qiáng)邊染色等等.圖的染色問(wèn)題具有很重要的理論和實(shí)際應(yīng)用價(jià)值,是圖論一個(gè)重要的研究方向.圖的染色問(wèn)題,處理的是涉及任務(wù)分配之類(lèi)的問(wèn)題.編排課表問(wèn)題,物品存放問(wèn)題,時(shí)間表問(wèn)題,網(wǎng)絡(luò)電路的設(shè)計(jì)等均屬于圖的染色問(wèn)題的范疇.雖然以上這兩個(gè)問(wèn)題很重要,但在對(duì)一般圖的研究上舉步維艱,人們更多時(shí)候是去研究一些特殊的圖類(lèi)并取得了一些進(jìn)展.根據(jù)Tutte關(guān)于3-連通圖的結(jié)構(gòu)定理：每一個(gè)3-連通圖都可由某個(gè)輪圖(也是Halin圖)經(jīng)過(guò)頂點(diǎn)分裂逐步得到,由此可以看出Halin圖在圖的結(jié)構(gòu)研究中的地位和作用.本文首先研究得到了近正則Halin圖G的消圈數(shù)的上,下界；接下來(lái)構(gòu)造得到了兩類(lèi)特殊的Halin圖,用以證明我們得到的消圈數(shù)的上,下界是緊的,接著得到了最大度為k或最小度為k的Halin圖的消圈數(shù)所滿(mǎn)足的界；本文還研究了另外兩類(lèi)近4-正則Halin圖的消圈數(shù)并確定了這兩者的各一個(gè)最小消圈集；在最后,本文還對(duì)Halin圖的點(diǎn)染色問(wèn)題進(jìn)行了研究,給出了點(diǎn)色數(shù)定理[1]的一種新證明.
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 趙小強(qiáng);;高考中一類(lèi)染色問(wèn)題的推廣與應(yīng)用[J];數(shù)學(xué)愛(ài)好者(高考版);2008年12期

2 劉西峰;;兩次捆綁快速解決有關(guān)染色問(wèn)題[J];中學(xué)教學(xué)參考;2009年26期

3 郭建華;;染色問(wèn)題解題策略例說(shuō)[J];青蘋(píng)果;2009年06期

4 盧建立;任鳳霞;;3×n方格染色問(wèn)題的兩個(gè)新結(jié)果[J];數(shù)學(xué)通報(bào);2011年12期

5 麥安嬋;兩類(lèi)圖的全染色問(wèn)題[J];榆林高等專(zhuān)科學(xué)校學(xué)報(bào);2002年04期

6 劉蓉;;排列組合中的染色問(wèn)題[J];科技信息;2011年10期

7 盧建立;任鳳霞;馬美琳;;項(xiàng)鏈的若干染色問(wèn)題[J];科技導(dǎo)報(bào);2012年07期

8 盧家華;吳康;;3×n方格染色問(wèn)題的再研究[J];數(shù)學(xué)通報(bào);2014年01期

9 林育青;關(guān)于圖的染色問(wèn)題[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2000年01期

10 王紹文;;圖的染色問(wèn)題綜述[J];北京機(jī)械工業(yè)學(xué)院學(xué)報(bào);1995年02期

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

1 李善海;設(shè)計(jì)的染色及其相關(guān)問(wèn)題的研究[D];上海交通大學(xué);2006年

2 陳敏;運(yùn)用權(quán)轉(zhuǎn)移方法研究圖的若干染色問(wèn)題[D];蘇州大學(xué);2011年

3 侯建鋒;圖上有限制條件的幾類(lèi)染色問(wèn)題的研究[D];山東大學(xué);2009年

4 胡小蘭;極值和染色問(wèn)題的一些新結(jié)果[D];南京大學(xué);2015年

5 董愛(ài)君;圖的幾類(lèi)染色問(wèn)題[D];山東大學(xué);2012年

6 梁作松;圖的團(tuán)橫貫與團(tuán)染色[D];上海大學(xué);2013年

7 于永;圖的[r，s，，t；f]-染色及（p，1）-全標(biāo)號(hào)問(wèn)題[D];山東大學(xué);2012年

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

1 朱俊俏;關(guān)于圖的點(diǎn)可區(qū)別染色問(wèn)題[D];浙江師范大學(xué);2009年

2 王瑞琦;圖邊單射染色問(wèn)題的復(fù)雜性及算法研究[D];南京師范大學(xué);2014年

3 朱恩強(qiáng);若干圖類(lèi)的新染色問(wèn)題[D];蘭州交通大學(xué);2010年

4 王輝;滿(mǎn)足某些特殊條件的平面圖邊染色問(wèn)題研究[D];山東大學(xué);2010年

5 尹琳娟;圖論染色問(wèn)題應(yīng)用研究[D];西安電子科技大學(xué);2009年

6 劉君;圖的染色[D];蘭州大學(xué);2006年

7 胡義;高效的圖染色近似型求解算法[D];華中科技大學(xué);2011年

8 吳倩;圖的若干染色問(wèn)題研究[D];浙江師范大學(xué);2012年

9 吳玉蝶;圖的k-重染色問(wèn)題[D];浙江師范大學(xué);2011年

10 任冠峰;圖的k-重染色問(wèn)題[D];浙江師范大學(xué);2009年

本文編號(hào)：1190515