二、平面圖的特征找出一個圖是平面圖的充分必要條件的研-資料下載頁
2024-10-17 20:14本頁面
【導(dǎo)讀】找出一個圖是平面圖的充分必要條件的。一個非常簡潔的特征。首先介紹剖分的概念：。給定圖G的一個剖分是對G實行有限次下。刪去它的一條邊{u,v}后添加一個新的點。w以及新的邊{w,u}和{w,v}。也就是說在G的邊上插入有限個點便得。若圖G的一個子圖是Kn,n的剖分，則G. 中至少有2n個頂點度數(shù)大于等于n。例：G=(V,E)，|V|=7，若G中含有K5的剖。分，則不含有K5或K3,3的剖分.庫拉托斯基定理雖然很漂亮,但是在具體。因此以后仍有許多這方面。橋一次且僅一次。在這里幾何對偶常簡稱為對偶?？蓪*作幾何對偶,記為G**。關(guān)系,如下所述。由定義的過程可知,平面圖G的任何。關(guān)鍵是嵌入方式不同。色,稱G為k-可著色的。對于n個頂點構(gòu)成的回路Cn,當(dāng)n是偶數(shù)。數(shù)的上界則是有結(jié)論的。布魯克斯在1941年證明了這樣的。1976年6月美國伊利諾斯大學(xué)兩位教授阿培爾和。明了四色問題,終于解決了這個大難題。問題,尚未得到解決。著色稱為地圖的正常面著色。
【正文】 }。 ? (2)→( 3): T是無回路圖 ,且 e=n1,要證明 T是連通圖 ,且 e=n1。 即證明 T是連通圖 ,用反證法 , ? (3)→( 4):在 T是連通圖 ,且 e=n1的條件下 ,證明 T是無回路圖 ,且在 T的任兩個不相鄰的頂點之間添加一邊 ,恰得到一條回路 。 ? 1)首先證明 T是無回路的 。 ?對頂點數(shù) n采用歸納法 , ? n=2時 e=1,且連通 , 只能是下圖 顯然 T是無回路的。 ?假設(shè) n=k1時結(jié)論成立 ,考察 n=k時 ,由于 T是連通的 ,所以 ,每個頂點度數(shù) ?1(e=k1)。 可以證明 ,至少存在一個頂點 u,使 d(u)=1。 Why? ? 2)再證明如果在連通圖 T的任兩個不相鄰頂點之間添加一邊 ,記為 {vi,vj},則該邊與 T中從 vi到 vj的一條路 ? (vi,vi1,… , vis,vj) ?構(gòu)成一條回路 (vi,vi1,… , vis,vj,vi)。 ?若這條回路不唯一 ， 由于 T無回路 ， 而T∪ {vi,vj}得到了回路 ， 因此另一條回路C39。也含有邊 {vi,vj}， ? (4)→( 5): 在 T是無回路圖 ,且在 T的任兩個不相鄰的頂點之間添加一邊 ,恰得到一條回路的條件下證明 T是連通圖 ,但刪去任一邊后 ,便不連通 。 ?若 T不連通 , 則存在頂點 vi和 vj,在 vi與 vj之間沒有路 。 顯然 ,若加一邊 {vi,vj},不會產(chǎn)生回路 ,與假設(shè)矛盾 。 ?又由于 T無回路 ,則刪去任一邊 ,便不連通 ? (5)→( 6): 在 T是連通圖 ,但刪去任一邊后 ,便不連通的條件下證明 T的每一對不同的頂點之間有唯一的一條路 。 ?由于 T是連通的 ,任兩點之間有一條路 。如果某兩個頂點之間多于一條路 ,則 T中必含有回路 ,(Why?) 刪去該回路上任一邊 ,圖仍連通 ,與假設(shè)矛盾 。 ? (6)→( 1): 在 T的每一對不同的頂點之間有唯一的一條路的條件下 ， 證明 T是無回路的連通圖 。 顯然圖是連通的 。 若有回路 , 則回路上任兩點之間有兩條路 , 從而導(dǎo)致矛盾 。 ?推論：若 G是 n個頂點 ?個分支的森林 , 則 G有 n?條邊 。 ?定理 :在任一棵非平凡樹 T中 , 至少有兩片樹葉 。 ?證明 :由于 T是連通的 ,對 T的任一頂點vi,d(vi)?1,并且 e=n1,即所有頂點度數(shù)之和=2(n1). ?下面證明 T中至少有兩個頂點的度數(shù)為 1 。 ?作業(yè) : ?P131 8,9,11,12,14,15,16 ?P152 1,2,3,4,5,6,7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1