平面圖的線性著色.pdf

1、圖的著色問題是圖論里的一個(gè)重要分支，它來自于圖論里最著名的四色猜想。圖的著色理論不僅僅在離散數(shù)學(xué)和組合分析等數(shù)學(xué)理論中有許多應(yīng)用，而且在最優(yōu)化、交通運(yùn)輸、計(jì)算機(jī)理論和通訊網(wǎng)絡(luò)等方面也有著很廣泛的應(yīng)用。在生活中，安排會(huì)議或者是考試的日程表來避免沖突，以及在排放化學(xué)藥品的存儲(chǔ)來避免相互反應(yīng)等具體問題都可以使用圖的著色理論來解決。由于圖的著色理論有著很重要的理論和實(shí)用意義，所以圖的著色問題一直都是圖論研究中的熱門問題。
　　本文主要是研

2、究了平面圖的線性著色和幾種特殊圖的線性著色。線性著色是以正常的頂點(diǎn)著色為基礎(chǔ)，針對(duì)圖中的頂點(diǎn)進(jìn)行著色的。本文的主要內(nèi)容可以分為以下四部分：
　　第一部分（第一章）主要用來介紹圖論中著色問題的歷史起源和研究意義，以及本文的研究目的和主要內(nèi)容。
　　第二部分（第二章）主要介紹了圖的著色中的一些有關(guān)基本概念，重點(diǎn)介紹了線性著色的概念，并且對(duì)線性著色的研究現(xiàn)狀進(jìn)行了綜述。
　　第三部分（文章的三、四章）是本文的核心章節(jié)。在這部