圖論平圖及著色

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

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

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