平面圖和五色定理

《平面圖和五色定理》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、6.2平面圖和五色定理abcdfghxkya1b1c12df31hx31kg22y6.2平面圖和五色定理定義6.2.1如果能與這樣的一個(gè)圖同構(gòu)，其中的頂點(diǎn)在同一個(gè)平面上，而的邊只能在端點(diǎn)處相交，就稱為平面圖，而稱為的一個(gè)平面嵌入，或稱為在平面上的實(shí)現(xiàn)。如圖和就不具有這樣的性質(zhì)。一、平面圖的概念及性質(zhì)定義6.2.2平面圖的邊把整個(gè)平面分割成若干各連通的區(qū)域，這些區(qū)域的閉包稱為平面圖的面（包括外部無(wú)限區(qū)域，稱為外部面）。分別用和表示的面的集合和面的個(gè)數(shù)。定義6.2.3用表示平面圖中圍成面的周界。用（或）表示圍成面的周界的邊數(shù)，稱為的度。推論6.2.2在任何平面圖中，度為奇數(shù)的面的

2、個(gè)數(shù)為偶數(shù)。定理6.2.1如果G是平面圖，則問題：一個(gè)平面圖的面數(shù)是否會(huì)隨著這個(gè)平面圖的不同嵌入而改變？定理6.2.3（Euler公式）設(shè)是一個(gè)有個(gè)頂點(diǎn)、條邊和個(gè)面的連通平面圖，則證明：對(duì)面數(shù)進(jìn)行歸納證明。由于是連通的平面圖，所以當(dāng)時(shí)，是樹，因此。故假設(shè)對(duì)于一切面數(shù)少于的所有連通平面圖，Euler公式成立。現(xiàn)假設(shè)是一個(gè)有個(gè)頂點(diǎn)、條邊和個(gè)面的連通圖。由于，至少有一個(gè)回路，取這回路中的一條邊，則仍是連通平面圖，有個(gè)頂點(diǎn)，條邊和個(gè)面，根據(jù)歸納假設(shè)。即證畢。問題：對(duì)于非連通的平面圖，其相應(yīng)的點(diǎn)數(shù)、邊數(shù)和面數(shù)有什么關(guān)系？推論6.2.4若是階為的平面圖，的最短回路的長(zhǎng)度為，則證明：現(xiàn)在對(duì)

3、的每個(gè)面，由于假設(shè)，因此由定理6.2.1知不妨設(shè)該平面圖是連通的平面圖，則根據(jù)Euler公式，有因此，有推論6.2.4的一般情況：對(duì)簡(jiǎn)單平面圖，有由以上結(jié)論，容易驗(yàn)證和不是平面圖推論6.2.5設(shè)是簡(jiǎn)單平面圖，則。證明：反證法。假設(shè)是一個(gè)平面圖，但，則而對(duì)于簡(jiǎn)單平面圖，有矛盾。故對(duì)每一個(gè)簡(jiǎn)單平面圖，有。例：平面上有個(gè)點(diǎn)，其中任意兩個(gè)點(diǎn)之間的距離至少是1。證明在這個(gè)點(diǎn)中，距離恰好為1的點(diǎn)對(duì)數(shù)至多是。二、平面圖與正多面體凸多面體在平面上的投影是一個(gè)連通的平面圖，因此Euler公式也適用于凸多面體。為此我們可以用Euler公式討論正多面體。正4-面體正6—面體正8-面體—抽象化——抽

4、象化—正12-面體—抽象化—正20-面體定理6.2.6存在且只存在5種正多面體：正四面體、正方體、正八面體、正十二面體和正二十面體。證明：首先一個(gè)正多面體在平面上的投影所得平面圖是2連通的正則圖，而且每個(gè)面的度相同，即為。設(shè)平面圖是正則、每個(gè)面的度為，則，，并且即滿足上式且至少為3的正整數(shù)和只有五對(duì)。（見下表）相應(yīng)的正多面體33464正4-面體348126正6-體35203012正12-面體436128正8-面體53123020正20-面體正4-面體正8-面體正6-面體正12-面體正20-面體平面上看：三、平面圖的判別我們可以利用和的非平面性來給出兩個(gè)有關(guān)平面圖的判別定理找出

5、一個(gè)圖是平面圖的充分必要條件的研究持續(xù)了幾十年，直到1930年波蘭數(shù)學(xué)家?guī)炖蟹蛩够↘uratowski）給出了平面圖的一個(gè)非常簡(jiǎn)潔的特征。給定圖的一個(gè)剖分是對(duì)圖實(shí)現(xiàn)有限次過程而得到的另一個(gè)圖:即刪去的一條邊后，添一個(gè)新的頂點(diǎn)及兩條新的邊、。也就是說在的邊上插入有限個(gè)頂點(diǎn)便可得到的一個(gè)剖分。定理6.2.7（Kuratowski定理）圖是平面圖當(dāng)且僅當(dāng)它的任何子圖都不是或的剖分。定理6.2.8（Wangner定理）一個(gè)圖為平面圖當(dāng)且僅當(dāng)它的任何子圖都不能收縮為或。可得Petersen圖不是平面圖。收縮邊四、五色定理的證明我們將利用推論6.2.5的結(jié)論來證明每一個(gè)平面圖的點(diǎn)色數(shù)

6、不超過5定理6.2.9每一個(gè)平面圖的色數(shù)不超過5。證明：對(duì)平面圖的頂點(diǎn)數(shù)進(jìn)行歸納。當(dāng)時(shí)，結(jié)論顯然成立。不妨假設(shè)所給的平面圖連通。歸納假設(shè)對(duì)頂點(diǎn)數(shù)為的平面圖結(jié)論成立，下設(shè)是頂點(diǎn)數(shù)為的簡(jiǎn)單圖。設(shè)法證明。反證法：設(shè)。首先由推論6.2.5知，設(shè)，。作。此時(shí)是階為的平面圖，由歸納假設(shè)得。如果，只要將五種顏色分配給，即可得，矛盾，故。設(shè)已給的頂點(diǎn)染五種顏色，使中相鄰頂點(diǎn)染以不同的顏色。如果，可得矛盾。。設(shè)的五個(gè)鄰點(diǎn)依次為。分兩種情況：Case1五個(gè)點(diǎn)所染顏色有相同的，只要將在沒出現(xiàn)的顏色分配給，就有。矛盾。Case2五個(gè)點(diǎn)染得顏色各不相同。不妨設(shè)分別染。讓為的色劃分?，F(xiàn)考慮的子圖。如果在

7、中與不在同一個(gè)連通分支中，則可以把中含的連通分支內(nèi)的與兩種顏色互換，而中其余顏色不變，就得到的一個(gè)5染色。此時(shí)與同染這種顏色，與假設(shè)矛盾。所以與在同一連通分支中，于是在中存在一條到的路同樣考慮子圖，在中存在到的路。由路的構(gòu)造可知，與不相交（即無(wú)公共頂點(diǎn)）。但在中，回路將與分隔在兩個(gè)不同的區(qū)域內(nèi)，而是平面圖，所以路必與相交于某個(gè)頂點(diǎn)。由于，因此與相交與某個(gè)頂點(diǎn)，矛盾。證畢。一個(gè)非平面圖G是不能嵌入在一個(gè)平面上的，但它可以分解為若干個(gè)平面圖的并圖，即存在若干平面圖使，不妨設(shè)這些平面圖是G的生成子圖，我們將這