二、平面圖的特征找出一個(gè)圖是平面圖的充分必要條件的研-wenkub.com
2024-10-13 20:14 本頁面
【正文】 ?定理 :在任一棵非平凡樹 T中 , 至少有兩片樹葉 。 ? (6)→( 1): 在 T的每一對(duì)不同的頂點(diǎn)之間有唯一的一條路的條件下 ， 證明 T是無回路的連通圖 。 顯然 ,若加一邊 {vi,vj},不會(huì)產(chǎn)生回路 ,與假設(shè)矛盾 。 Why? ? 2)再證明如果在連通圖 T的任兩個(gè)不相鄰頂點(diǎn)之間添加一邊 ,記為 {vi,vj},則該邊與 T中從 vi到 vj的一條路 ? (vi,vi1,… , vis,vj) ?構(gòu)成一條回路 (vi,vi1,… , vis,vj,vi)。 ? 1)首先證明 T是無回路的 。 ? 證明： (1)→( 2): T是無回路的連通圖要證明 T是無回路圖 ,且 e=n1， 即證明 e=n1 ? 對(duì)頂點(diǎn)數(shù) n采用歸納法 ,n=2時(shí) ,因?yàn)?T是無回路的連通圖 ，顯然只能是下圖所示： 故結(jié)論成立。 ? (3)T是連通圖 ,且 e=n1。 (平凡圖即只有一個(gè)點(diǎn) ) 圖 (a)是一棵樹； (b)是森林 ,也就是無回路的圖 ,它的每個(gè)分支是一棵樹。 樹中度數(shù)為 1的頂點(diǎn)稱為 樹葉 (或稱懸掛點(diǎn) )。 ?考慮 n個(gè)頂點(diǎn)的平面簡(jiǎn)單圖 G, ?由定理 , G中存在頂點(diǎn) v0,使 d(v0)?5。 ? (2) G*是 k面可著色的 ?定理 (五色定理 )：任何平面圖 G是 5可著色的 。 ?定理 :：設(shè) G是沒有自環(huán)的平面圖 , G*是G的對(duì)偶 ,則 G是 k可著色當(dāng)且僅當(dāng) G*是 k面可著色 。 若 ?*(G)=k,則稱 G是 k面色的 。 地圖中每一邊是兩個(gè)面的公共邊 ,兩個(gè)面相鄰是指這兩個(gè)面至少有一條公共邊 (而不是公共點(diǎn) ), 并且使相鄰兩個(gè)面著上不同的顏色 , 所以地圖是沒有橋的 。 ?這就是地圖的四色問題 ?一百多年來 , 許多數(shù)學(xué)家的證明都失敗了 。 ?布魯克斯 (Brooks)在 1941年證明了這樣的結(jié)果 , 使 ? (G)=1+?(G)的圖只有兩類 : 或是奇回路 , 或是完全圖 。 ?現(xiàn)設(shè) G有 n個(gè)頂點(diǎn) , 頂點(diǎn)的最大度數(shù)是 ?,如果刪去任一點(diǎn) v及其關(guān)聯(lián)的邊 , 得到 n1個(gè)頂點(diǎn)的圖G39。 ?定理 ：如果圖 G的頂點(diǎn)的最大度數(shù)為 ?(G),則 ?(G)?1+? (G)。 ? (3)對(duì)于 n個(gè)頂點(diǎn)構(gòu)成的回路 Cn,當(dāng) n是偶數(shù)時(shí) , ?(Cn)=2。 ?如下圖 (a)中的圖的色數(shù)是 4, (b)中的圖的色數(shù)是 3。 ?定義 :設(shè) G是一個(gè)沒有自環(huán)的圖 , 對(duì) G的每個(gè)頂點(diǎn)著色 , 使得沒有兩個(gè)相鄰的頂點(diǎn)著上相同的顏色 ,這種著色稱為圖的正常著色 。 ?定理 ： G是連通平面圖當(dāng)且僅當(dāng) G**同構(gòu)于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1