平面圖的線性著色.pdf

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

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