平面圖的3著色及線性著色.pdf

1、圖的著色問題來源于圖論中最著名的四色猜想，它是圖論中的一個重要分支。圖的著色理論不僅在離散數(shù)學(xué)與組合分析等數(shù)學(xué)理論中有應(yīng)用，它在最優(yōu)化、交通運輸、通訊網(wǎng)絡(luò)和計算機(jī)理論等方面也有著廣泛的應(yīng)用。生活中安排會議或考試的日程以避免沖突，以及安排化學(xué)藥品的存儲以避免相互反應(yīng)等具體問題也都可以用圖的著色理論來解決?；趫D的著色理論有著重要的理論意義和實用意義，圖的著色問題一直是圖論研究中的熱點問題。
　　 本文主要研究了平面圖的3著色與線性

2、著色。它們都是針對圖中的頂點進(jìn)行著色的，其中線性著色以正常頂點著色為基礎(chǔ)，3著色即只用了3種顏色的正常頂點著色。主要內(nèi)容可分為四部分：
　　 第一部分(第一章)主要介紹了圖論中著色問題的歷史背景，以及本文的研究目的與主要內(nèi)容。
　　 第二部分(第二章)介紹了圖的著色中的一些基本概念，重點介紹了正常頂點著色和線性著色的概念，并對兩種著色的研究現(xiàn)狀進(jìn)行了綜述。
　　 第三部分(文章的三、四章)是本論文的核心部分。在這

3、一部分中，探討了平面圖的3著色和線性著色問題。第三章首先通過分析全由3度頂點構(gòu)成的偶圈的結(jié)構(gòu)，發(fā)現(xiàn)運用著色技巧可以實現(xiàn)著色延拓，給出了一個引理來說明最小反例圖的結(jié)構(gòu)；然后通過對歐拉公式作適當(dāng)變形，巧妙設(shè)計權(quán)值分配規(guī)則，給出了平面圖3可著色的3個充分條件。第四章中通過分析平面圖的結(jié)構(gòu)，結(jié)合線性著色的特點，運用已知引理在一定程度上縮小了平面圖線性著色色數(shù)的上界。
　　 第四部分(第五章)總結(jié)了本文研究所得到的結(jié)論，指出了本文的創(chuàng)新之