極大平面圖的構(gòu)造方法與幾類特殊圖的色數(shù)分析.pdf

1、圖論是離散數(shù)學(xué)的重要分支之一。著色問(wèn)題是圖論中研究較早的領(lǐng)域，也是圖論的重要研究?jī)?nèi)容，最近幾年來(lái)一直是圖論研究中的熱點(diǎn)問(wèn)題，但至今著色問(wèn)題仍是數(shù)學(xué)中未解決的難題之一。由于還未找到求圖色數(shù)的有效算法，甚至還未找到有較好性能比的有效近似算法，著色理論的應(yīng)用受到了很大的限制，這有待于我們?nèi)ミM(jìn)一步的研究。 本文首先簡(jiǎn)單介紹了目前國(guó)內(nèi)外關(guān)于圖的著色問(wèn)題的研究現(xiàn)狀以及研究意義。其次，通過(guò)研究極大平面圖的構(gòu)成原理，給出了構(gòu)造極大平面圖的加點(diǎn)法

2、，并證明了這種方法的可靠性。接著，本文給出了簡(jiǎn)單連通圖的色數(shù)不大于2的充要條件。接下來(lái)，本文證明了任意一個(gè)簡(jiǎn)單平面圖都是某個(gè)極大平面圖的生成子圖，則任意一個(gè)簡(jiǎn)單平面圖色數(shù)的上界是相應(yīng)的極大平面圖的色數(shù)。接著，本文證明了頂點(diǎn)度都為偶數(shù)的極大平面圖的色數(shù)為3。最后，本文在證明極大平面圖都可以5.著色的基礎(chǔ)上，用數(shù)學(xué)歸納法證明了部分加點(diǎn)法產(chǎn)生的極大平面圖是可以4.著色的，并對(duì)其余的極大平面圖提出了一個(gè)猜想，若這個(gè)猜想成立，則可以證明極大平面圖