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

1、山東科技大學(xué)碩士學(xué)位論文若干圖類的關(guān)聯(lián)色數(shù)與全色數(shù)姓名：王淑棟申請學(xué)位級別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：陳東靈2000.5.1碩士學(xué)位論文第一章引言圖的著色理論起源于1852年的“四色猜想”，即：在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家著有相同的顏色。后來，人們把國家(和外部區(qū)域)都看成點，當(dāng)相應(yīng)的兩個國家相鄰時，這兩個點用一條線來連結(jié)，這樣，“四色猜想”就轉(zhuǎn)化為圖論中的著色問題，即將每一個可平面

2、圖的點用四種或更少的顏色來著色，使得兩個相鄰的點著有不同的顏色。從此，圖著色理論的研究就一直在圖論中占有舉足輕重的位置12]，其主要原因如下：首先，圖著色理論可將一些對象按照一定的規(guī)則進(jìn)行分類，在現(xiàn)實生活中有著相當(dāng)重要的作用，如：時間表問題、排序問題、排課表問題、交通狀態(tài)、車隊保養(yǎng)、垃圾運(yùn)輸表、電路安排、貯藏問題、可移動無線電計劃表、任務(wù)的分配等啪Ⅲ都與圖著色理論密切相關(guān)；其次，圖著色理論在離散數(shù)學(xué)上居于要位，離散數(shù)學(xué)上許多貌似無關(guān)的問

3、題都可轉(zhuǎn)化為圖著色問題，例：極圖理論中的Erd6s和Simonovits定理：給定圖G，不包含子圖G的具有一個頂點的圖的邊的最大數(shù)廠G，G)的性態(tài)取決于G的色數(shù)如)：lim』％盟=乏x砸(G)2。1976年，美國伊利諾大學(xué)的KAppel和WHaken花費(fèi)大量的時間用計算機(jī)證明了數(shù)學(xué)史上懸掛多年的四色猜想：1997年，Neilrobertson等又給出了一個簡化的計算機(jī)證明[40l，但至今尚未有嚴(yán)密的理論性(非計算機(jī))證明。近幾年來，關(guān)于