若干圖類的關聯色數與全色數.pdf

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

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

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