若干圖類的對策色數(shù)和關(guān)聯(lián)色數(shù).pdf

1、山東科技大學(xué)碩士學(xué)位論文若干圖類的對策色數(shù)和關(guān)聯(lián)色數(shù)姓名：劉西奎申請學(xué)位級別：碩士專業(yè)：運籌學(xué)與控制論指導(dǎo)教師：陳東靈2000.5.1碩士學(xué)位論文第1章序言強豹瓣色理論雀圖論巾具有囂卷重要熬地位，它的起源可以追溯到1852年“四色問題”的提出。迄今“四色問題”并未劃上句號，盡警K。Appel移WHaken予1976年芯費大塞熬辯潤曩詩葵梗涯弱了數(shù)學(xué)史上懸掛多年的四色猜想，1997年，NRobertson，DSandersandRThom

2、as[43]繪窶了～令鬻純魏詩葵壤涯麓。霆梵瑗在誨多入爨在尋找“四色問題”的一個理論證明，圖著色一直是圖論中的凝有中心地位靜磷究謀戇，這一磷究課戇吳有率塞瑟露逢翦等價闖瑟。囂蘩，叉出現(xiàn)了若干新的著色分支，它將過擻未解決的問題轉(zhuǎn)化為一個新的著色閥越，這樣使器潤題衙犖荔懂，又便于研究顯技巧毪強。圖著色理論具有非常麓要的實際應(yīng)用價值。主要表現(xiàn)在交通調(diào)整、時間表、艏酞養(yǎng)護(hù)、信遙設(shè)計、W移動禿線電話豳程表、任務(wù)靜安排等方面，躐此這一研究課題具有強

3、勁的生命力和廣闊的發(fā)展前景。本文主要討論某些圈類的對策色數(shù)和關(guān)聯(lián)色數(shù)。關(guān)予圖的對策著色瓤關(guān)聯(lián)麓色都是本世紀(jì)90年代粵|入的凝概念。我們將農(nóng)下一章給出圖的對策著色的部分性質(zhì)并確定一些圈類的對策色數(shù)。在本文第三章中討論嬲敬關(guān)聯(lián)色數(shù)，繪出了寵全多部圖的關(guān)聯(lián)色數(shù)，勢討論了其他一些圖的關(guān)聯(lián)色數(shù)。若G爨無重邊又無環(huán)，剮豫為楚攀圈；若G霉重邊域繇，則猿建多踅圖。G(y(G)，E(G))表示頂點集為v(G)。邊熊為E(G)的圖。厶(G)鬏艿(G)分裂表