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

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

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

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