資源描述：
《二：平面圖、對偶和作色、樹和生成樹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、7－5平面圖1、平面圖定義：設(shè)圖G=是一個無向圖，如果能夠把G的所有結(jié)點和邊畫在平面上，且使得任何兩條邊除了端點外沒有其他的交點，就稱G是一個平面圖。注意：有些圖從表面上看有幾條邊是相交的，但是改畫之后，仍然是平面圖。BB'K3,3此圖是非平面圖K5是非平面圖2、面、面的邊界定義：設(shè)G是一個連通平面圖，由圖中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既不包含圖的結(jié)點，也不包含圖的邊，這樣的區(qū)域稱為G的一個面，包圍該面的諸邊所構(gòu)成的回路稱為這個面的邊界。面的邊界的回路長度稱作該面的次數(shù)，記為deg(r)。ABCDEFr4r1r2r3r5deg(r1)=deg(r2)=deg(r3)=deg(r4)
2、=deg(r5)=無限面33543定理1一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。ABC圖中只有一個面r，由回路ABCBA所圍成,deg(r)=4=2×2圖中有兩個面r1,r2,r1由回路BCDB圍成，r2由回路ABCDBA圍成，deg(r1)+deg(r2)=3+5=2×4ABCDr1r2定理2(歐拉定理)設(shè)有一個連通的平面圖G，共有v個結(jié)點e條邊和r個面，則歐拉公式v－ｅ＋r＝２成立。證明：對ｅ歸納定理3設(shè)Ｇ是一個有ｖ個結(jié)點ｅ條邊的連通簡單平面圖，若v≥3，則ｅ≤３v－６。用來判斷某些圖是非平面圖K53×5－6＝9＜10設(shè)有r個面，則２e≥３r推論：如果圖Ｇ＝<Ｖ,Ｅ>是連通的簡單
3、平面圖，若v≥3，且每個區(qū)域至少由四條邊圍成，則有ｅ≤２v－４。K3,3作業(yè)Ｐ317(1)(2)(4)7－6對偶與著色這個問題最早起源于地圖著色，一個地圖中相鄰兩個國家以不同的顏色，那么最少需用多少種？一百多年前，英國格色里(Guthrie)提出用四種猜想即可對地圖進行著色的猜想，1879年肯普(Kempe)給出該猜想的第一個證明，但到了1890年希伍德(Hewood)發(fā)現(xiàn)肯普的證明是錯誤的，指出肯普的方法，雖不能證明用四種顏色就夠了，但可證明用五種就夠了，此后四色問題一直成為數(shù)學家感興趣而未解決的難題，到了1976年美國數(shù)學家阿佩爾和黑肯宣布：用電子計算機證明了四色猜想是正確的，從此有了
4、“四色理論”。1、對偶定義給定平面圖G=，它具有面F1,F2,…,Fn，若有圖G*=滿足下列條件：(a)對于圖的任何一個面Fi，內(nèi)部有且僅有一個結(jié)點vi*∈V*；(b)對于圖的面Fi和Fj的公共邊界ek，有且僅有一條邊e*k∈E*，使得e*k=(v*i,vj*)，且e*k與ek相交；(c)當且僅當ek只是一個面Fi的邊界時，v*i存在一個環(huán)e*k與ek相交。則稱G*是G的對偶圖。注意：若G*是G的對偶圖，則G也是G*的對偶圖。例:P318圖7-6.1、圖7-6.2定義若圖G的對偶圖G*同構(gòu)于G，則稱G是自對偶圖。從對偶圖的概念我們可以看到，對地圖的著色問題可以歸結(jié)為
5、對平面圖的結(jié)點進行著色的問題，因此四色問題可以歸結(jié)為證明對于任何一個平面圖，一定可以用四種顏色進行著色，使得鄰接的結(jié)點都有不同的顏色。2、著色圖G的正常著色（簡稱著色）是指對它的每一個結(jié)點指定一種顏色，使得沒有兩個鄰接的結(jié)點有同一種顏色。如果圖G在著色時用了n種顏色，我們稱G為n-色的。最小著色數(shù)用x(G)表示。雖然目前還沒有一個簡單的方法，可以確定任一圖G是n-色的。但我們可以用韋爾奇鮑威爾(WelchPowell)對圖G著色：a)將圖G中的結(jié)點按照度數(shù)的遞減次序進行排列（這種排列可能并不是唯一的，因為有些點有相同度數(shù)）；b)用第一種顏色對第一點著色，并且并且按排列次序，對與前面著色點不
6、鄰接的每個點著上同一種顏色；c)用第二種顏色對尚未著色的點重復b)，用第三種顏色繼續(xù)這種做法，直到所有點全部著上色為止。定理1對于n個結(jié)點的完全圖Kn，有x(Kn)=n。證明：因為完全圖的每個結(jié)點與其它各個結(jié)點都鄰接，故n個結(jié)點的著色數(shù)不能少于n，又n個結(jié)點的著色數(shù)最多為n，故x(Kn)=n。定理2設(shè)G為一個至少具有三個結(jié)點的連通平面圖，則G中至少有一點u，使得deg(u)≤5。證明：設(shè)G=，
7、V
8、=v，
9、E
10、=e，若G中每個結(jié)點u，都有deg(u)≥6,但因故2e≥6v，所以e≥3v>3v-6，與ｅ≤3v-6矛盾。定理3任意平面圖G最多是5-色的。7-7樹與生成樹一、樹定義：一
11、個連通且無回路的無向圖稱為樹。樹中度數(shù)為1的結(jié)點稱為樹葉，度數(shù)大于1的結(jié)點稱為分支點或內(nèi)點。一個無回路的無向圖稱作森林，它的每個連通分圖是樹。孤立結(jié)點可以看成是一個連通分支，但一般情況下孤立結(jié)點不看成是一棵樹。除非有特殊說明。定理1以下關(guān)于樹的定義是等價的。無回路的連通圖。無回路且e=v-1，其中e是邊數(shù)，v是結(jié)點數(shù)。連通且e=v-1。無回路，但增加一條新邊，得到一個且僅有一個回路。連通，但刪去任一邊后便不連通。每一對結(jié)
