若干圖類的著色問題.pdf

1、山東科技大學(xué)碩士學(xué)位論文若干圖類的著色問題姓名：段華申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：陳東靈2002.5.1碩士學(xué)位論文第一章序言圖的著色理論起源于150年前的“四色問題”或“四色猜想”。百余年來大批優(yōu)秀數(shù)學(xué)家為解決這個(gè)猜想花費(fèi)了大量的心血，盡管迄今仍沒有得到非計(jì)算機(jī)的理論性證明，但人們?cè)跊_擊“四色猜想”時(shí)所采用的思想、方法和技巧為圖論寶庫增添了一個(gè)又一個(gè)精彩結(jié)果，致使圖的著色理論發(fā)展成為一個(gè)有廣泛實(shí)際應(yīng)用和旺盛生命力的新

2、學(xué)科。1976年KAppel和WHaken在JKoch的協(xié)助下用計(jì)算機(jī)檢驗(yàn)了“四色猜想”是正確的?！?，從而“四色猜想”為“四色定理”所代替。在1997年，NRobertson，DSanders和RThomast21給出“四色定理”的一個(gè)簡化的計(jì)算機(jī)證明。這當(dāng)然是一個(gè)第一流的成就，但它在數(shù)學(xué)上和哲學(xué)上都引出許多新的問題，對(duì)許多數(shù)學(xué)家來說這個(gè)解決辦法并不是令人滿意的。離散系統(tǒng)中的許多問題表面上似乎與著色沒聯(lián)系，但最終要解決它們往往依賴于一個(gè)