二、平面圖的特征找出一個圖是平面圖的充分必要條件的研(存儲版)
【正文】 : 如果相鄰兩國著上不同的顏色 , 那么畫任何一張地圖只需要四種顏色就夠了 。 使 G的k面可著色的數(shù) k的最小值稱為 G的面色數(shù) , 記為 ?*(G)。 ?因為 G是 k可著色的 ,G中任何兩個相鄰的頂點有不同的顏色 , 所以 G*中任何兩個相鄰面著上不同的顏色 , 因此 G*是 k面可著色的 。 ?證明： (1) G是 2面可著色的 ， 則它是一個歐拉圖 ? (2) G是歐拉圖 ， 則 G是 2面可著色的 第七章 樹 ? ?定義 ：一個連通無回路的圖稱為 樹 ,記為 T。 ? (2)T是無回路圖 ,且 e=n1,其中 e是邊數(shù) 。 即證明 T是連通圖 ,用反證法 , ? (3)→( 4):在 T是連通圖 ,且 e=n1的條件下 ,證明 T是無回路圖 ,且在 T的任兩個不相鄰的頂點之間添加一邊 ,恰得到一條回路 。 ?若 T不連通 , 則存在頂點 vi和 vj,在 vi與 vj之間沒有路 。 ?推論：若 G是 n個頂點 ?個分支的森林 , 則 G有 n?條邊 。 顯然圖是連通的 。 ?若這條回路不唯一 ， 由于 T無回路 ， 而T∪ {vi,vj}得到了回路 ， 因此另一條回路C39。 假設 n=k時結論成立 ,現(xiàn)考察 n=k+1時 ,由于連通無回路以及定理 (若圖 G中每個頂點度數(shù)至少為 2,則 G包含一條回路 ), 可以知道至少有一個頂點度數(shù)為 1的點 u,它的關聯(lián)邊為 {u,v}。 ?除了定義 給出樹的定義外還有幾個樹的等價定義 , 即下面的定理 。 ?刪去 v0及其關聯(lián)邊得到 G39。 ?證明： (1)設 G是沒有自環(huán)的平面圖 , 則它的對偶 G*沒有橋 ， 所以是一個地圖 。 ?定義 ：設 G是一個地圖 , 對 G的每個面著色 ,使得沒有兩個相鄰的面著上相同的顏色 , 這種著色稱為地圖的 正常面著色 。 布魯克斯定理如下 , 證明從略 。 ?證明：只要證明圖 G用 1+?(G)種顏色就可正常著色 。 ?設 G是連通 、 沒有自環(huán)的圖 ,如果有多重邊 ,則可刪去多重邊 ,用一條邊代替 , 因此下面考慮連通簡單圖 G。 ?由定義 的過程可知 , 平面圖 G的任何兩個幾何對偶必同構 。顯然 G* 有多重邊當且僅當 G~中存在兩個面至少有兩條公共邊。 ? (4)若圖 G不是平面圖 ， 則或者 G含有 K5的剖分 ， 或者 G含有 K3,3的剖分 。 ?也就是說在 G的邊上插入有限個點便得到 G的一個剖分 。 ?例： G=(V,E)， |V|=7， 若 G中含有 K5的剖分 ， 則 不含有 K5或
教學課件相關推薦
鄂ICP備17016276號-1