圖論平圖及著色

圖論平圖及著色第1頁(yè)，共21頁(yè)，2023年，2月20日，星期六平面圖定義1如果一個(gè)圖能畫(huà)在平面上，使得它的邊僅在端點(diǎn)相交，則稱(chēng)這個(gè)圖為平面圖，或說(shuō)它是可平面嵌入的，平面圖G的這樣一種畫(huà)法，稱(chēng)為G的一個(gè)平面嵌入。平面圖G的平面嵌入稱(chēng)為平圖。第2頁(yè)，共21頁(yè)，2023年，2月20日，星期六K3,，K4，K5

第3頁(yè)，共21頁(yè)，2023年，2月20日，星期六定義２一條連續(xù)的、自身不相交的封閉曲線稱(chēng)為Jordon曲線。J的外部，extJ，外點(diǎn)，extJ與J之并稱(chēng)為extJ的閉包，記為ExtJ；另一部分(不含曲線J)稱(chēng)為J的內(nèi)部，記為intJ，intJ的點(diǎn)稱(chēng)為J的內(nèi)點(diǎn)，intJ與J之并稱(chēng)為intJ的閉包，記為IntJ。引理設(shè)J是一條Jordon曲線，任何連接J的內(nèi)點(diǎn)與外點(diǎn)的曲線必與J相交。第4頁(yè)，共21頁(yè)，2023年，2月20日，星期六定義３設(shè)G是一個(gè)平圖，則G把平面劃分成若干個(gè)連通區(qū)域，每個(gè)連通區(qū)域的閉包稱(chēng)為G的一個(gè)面，其中恰有一個(gè)無(wú)界的面，稱(chēng)為外部面。第5頁(yè)，共21頁(yè)，2023年，2月20日，星期六定理1若G是連通平圖，則 υ－ε＋f＝２， 其中，f是G的面數(shù).(這個(gè)公式稱(chēng)為Euler公式)證明對(duì)G的邊數(shù)ε用歸納法，……第6頁(yè)，共21頁(yè)，2023年，2月20日，星期六推論1給定平面連通圖G，則G的所有平面嵌入有相同的面數(shù)。第7頁(yè)，共21頁(yè)，2023年，2月20日，星期六推論２若G是平面簡(jiǎn)單圖，υ≥３，則 ε≤３υ－６。證明設(shè)G為連通平圖，用d(Fi)表示面Fi的邊數(shù)，……第8頁(yè)，共21頁(yè)，2023年，2月20日，星期六推論３若平圖G的每個(gè)面由至少四條邊圍成，則 ε≤2υ－4。第9頁(yè)，共21頁(yè)，2023年，2月20日，星期六推論４K5與K3,3是非平面圖。第10頁(yè)，共21頁(yè)，2023年，2月20日，星期六定理２在平面簡(jiǎn)單圖G中，至少存在一個(gè)頂點(diǎn)v0，使d(v0)≤5。證明假設(shè)一個(gè)平面簡(jiǎn)單圖的所有頂點(diǎn)度數(shù)均大于５，則， 矛盾，因此，平面簡(jiǎn)單圖中至少有一個(gè)頂點(diǎn)v0，使d(v0)≤5。第11頁(yè)，共21頁(yè)，2023年，2月20日，星期六頂點(diǎn)著色定義設(shè)G是一個(gè)圖，對(duì)G的每個(gè)頂點(diǎn)著色，使得沒(méi)有兩個(gè)相鄰的頂點(diǎn)著上相同的顏色，這種著色稱(chēng)為圖的正常著色若圖G的頂點(diǎn)可用k種顏色正常著色，稱(chēng)G為k可著色的使G是k可著色的數(shù)k的最小值稱(chēng)為G的色數(shù)，記為χ(G)，如果χ(G)＝k，則稱(chēng)G是k色的。第12頁(yè)，共21頁(yè)，2023年，2月20日，星期六

第13頁(yè)，共21頁(yè)，2023年，2月20日，星期六假設(shè)G是簡(jiǎn)單連通圖。定理1 (1)對(duì)于完全圖Kn，有χ(Kn)＝n，χ(～Kn)＝1。 (2)對(duì)于n個(gè)頂點(diǎn)構(gòu)成的圈Cn，當(dāng)n是偶數(shù)時(shí)，χ(Cn)＝2，當(dāng)n是奇數(shù)時(shí)，χ(Cn)＝3。 (3)對(duì)于非平凡樹(shù)T，有χ(T)＝２。 (4)G是二分圖，當(dāng)且僅當(dāng)χ(G)＝２。第14頁(yè)，共21頁(yè)，2023年，2月20日，星期六定理２對(duì)于任意連通簡(jiǎn)單圖G，有 χ(G)≤1＋△(G)。證明往證G是1＋△(G)可著色的。對(duì)G的頂點(diǎn)數(shù)施行歸納法，……第15頁(yè)，共21頁(yè)，2023年，2月20日，星期六作業(yè)證明圖G是2可著色的，當(dāng)且僅當(dāng)G中無(wú)奇圈。一個(gè)圖G稱(chēng)為臨界的，如果對(duì)G的每個(gè)真子圖Ｈ，有χ(Ｈ)＜χ(G)。k色的臨界圖稱(chēng)為k臨界圖。證明若G是k臨界圖，則δ≥k－1。證明每個(gè)k色圖至少有k個(gè)度不小于k－1的頂點(diǎn)。第16頁(yè)，共21頁(yè)，2023年，2月20日，星期六面著色定義1設(shè)e是圖G的一條邊，如果 ω(G－e)＞ω(G)， 則稱(chēng)e是G的割邊。第17頁(yè)，共21頁(yè)，2023年，2月20日，星期六定義２一個(gè)沒(méi)有割邊的連通平圖，稱(chēng)為地圖。第18頁(yè)，共21頁(yè)，2023年，2月20日，星期六定義３設(shè)G是一個(gè)地圖，對(duì)G的每個(gè)面著色，使得沒(méi)有兩個(gè)相鄰的面著上相同的顏色，這種著色稱(chēng)為地圖的正常面著色地圖G可用k種顏色正常面著色，稱(chēng)G是k面可著色的使得G是k面可著色的數(shù)k的最小值稱(chēng)為G的面色數(shù)，記為χ*(G)，若χ*(G)＝k，則稱(chēng)G是k面色的。第19頁(yè)，共21頁(yè)，2023年，2月20日，星期六地圖的k面可著色問(wèn)題，可以轉(zhuǎn)化為平面圖的k可著色問(wèn)題。定理1*(五色定