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

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

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

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