1、1 第廿九講2第七章第七章 圖論圖論7-5 7-5 平面圖平面圖定義定義7-5.17-5.1設設G=G=是一個是一個無向圖無向圖，如果能夠把，如果能夠把G G的所有結點和邊畫的所有結點和邊畫在平面上，且使得任何兩條邊除了端點外沒有其他的交點，在平面上，且使得任何兩條邊除了端點外沒有其他的交點，則稱則稱G G是一個是一個平面圖平面圖。 。 。 。 。3第七章第七章 圖論圖論定義定義7-5.27-5.2設設G G是一是一連通平面圖連通平面圖，由圖中的邊所包圍的區域，在區域，由圖中的邊所包圍的區域，在區域中既不包含圖的結點，也不包含圖的邊，這樣的區域稱為中既不包含圖的結點，也不包含圖的邊，這樣的區域

2、稱為G G的一個的一個面面，包圍該面的諸邊所構成的，包圍該面的諸邊所構成的回路回路稱為這個面的稱為這個面的邊界邊界。v3 。 。 。 。 。v1v2v4v5v6v7r1r2r3r44第七章第七章 圖論圖論定理定理7-5.17-5.1一個一個有限有限平面圖，面的次數之和等于其邊數的兩倍。平面圖，面的次數之和等于其邊數的兩倍。證證: : 因為任何一條邊，或者是兩個面的公共邊，或者在一因為任何一條邊，或者是兩個面的公共邊，或者在一個面中作為邊界被重復計算兩次，故面的次數之和等于個面中作為邊界被重復計算兩次，故面的次數之和等于其邊數的兩倍。其邊數的兩倍。v3 。 。 。 。 。v1v2v4v5v6v7

3、r1r2r3r45第七章第七章 圖論圖論定理定理7-5.27-5.2（歐拉定理）（歐拉定理） 設有一個設有一個連通連通的平面圖的平面圖G G，共有，共有v v個結點、個結點、e e條邊和條邊和r r個個面，則歐拉公式面，則歐拉公式 v-e+r=2 v-e+r=2 成立。成立。證證:(1) :(1) 若若G G為一孤立結點圖，則為一孤立結點圖，則v=1,e=0,r=1,v=1,e=0,r=1,故故v-e+r=2v-e+r=2成立。成立。(2) (2) 若若G G為一條邊，則為一條邊，則v=2,e=1,r=1,v=2,e=1,r=1,故故v-e+r=2v-e+r=2成立。成立。(3) (3) 若若

4、G G為為k k條邊時，歐拉公式成立，即條邊時，歐拉公式成立，即v vk k-e-ek k+r+rk k=2=2。下面。下面考察考察G G為為k+1k+1條邊時的情況。條邊時的情況。 在在k k條邊的連通圖上增加一條邊，使其仍為連通圖，只條邊的連通圖上增加一條邊，使其仍為連通圖，只有兩種情況：有兩種情況：6第七章第七章 圖論圖論例例1 1：證明：證明若若G G是每個面至少由是每個面至少由k(k3)k(k3)條邊圍成的連通條邊圍成的連通平面圖，則平面圖，則e k(v-2)/(k-2)e k(v-2)/(k-2)。證明：證明：由由定理定理7-5.17-5.1 及已知得及已知得2e kr2e kr再

5、結合再結合定理定理7-5.27-5.2得結論。得結論。例例2 2 證明證明在在6 6個結點個結點1212條邊的連通簡單平面圖中，每個條邊的連通簡單平面圖中，每個面是用面是用3 3條邊圍成的。條邊圍成的。證明：證明：由由定理定理7-5.27-5.2 得得 r=8r=8再由再由定理定理7-5.1 7-5.1 及及 每個面的次數至少為每個面的次數至少為3 3故結論成立。故結論成立。7第七章第七章 圖論圖論定理定理7-5.37-5.3設設G G是一個有是一個有v v個結點個結點e e條邊的連通簡單平面圖，若條邊的連通簡單平面圖，若v3v3，則則e3v-6e3v-6。證證: :當當v=3,e=2v=3,

6、e=2時，顯然成立。時，顯然成立。（對于無限面而言）（對于無限面而言）除此之外，設連通簡單平面圖除此之外，設連通簡單平面圖G G的面數為的面數為r r，若，若e3,e3,則每一則每一面的次數不小于面的次數不小于3 3，由前面定理知各面數之和為，由前面定理知各面數之和為2e2e，因此，因此2e 3r 2e 3r 代入歐拉定理：代入歐拉定理：v-e+r=2v-e+r=2二式結合得：二式結合得： e3v-6e3v-6提示：提示：此定理可作為判定某圖此定理可作為判定某圖G G是平面圖的必要條件，是平面圖的必要條件，而非充分條件。而非充分條件。8第七章第七章 圖論圖論例例3 3 判斷下圖是否為平面圖。判

7、斷下圖是否為平面圖。K K5 5 。 。 。 。證明：證明：K K3,33,3不是平面圖。不是平面圖。( (反證法反證法) )若是，則任取若是，則任取3 3個結點，其中必有兩個結點不鄰接，個結點，其中必有兩個結點不鄰接，故每個面的次數都不小于故每個面的次數都不小于4 4，于是有，于是有4r2e4r2e，代入歐拉公式代入歐拉公式 v-e+r=2 v-e+r=2 可得可得2v-4e2v-4e由此可判定由此可判定K K3,33,3不是平面圖。不是平面圖。K K3,33,39第七章第七章 圖論圖論例例4 4 證明證明小于小于3030條邊的簡單平面圖至少有一個結點度條邊的簡單平面圖至少有一個結點度數小于

8、等于數小于等于4 4。證明：證明：( (反證法反證法 ) )握手定理握手定理定理定理7-5.37-5.310第七章第七章 圖論圖論定義定義7-5.37-5.3給定兩個圖給定兩個圖G G1 1和和G G2 2，如果它們是同構的，或者通過反復插，如果它們是同構的，或者通過反復插入或刪除度為入或刪除度為2 2的結點后，使的結點后，使G G1 1和和G G2 2同構，則稱該兩圖是同構，則稱該兩圖是在在2 2度結點內同構度結點內同構的。的。定義定義7-5.47-5.4（KruatowskiKruatowski定理）定理）一個圖是平面圖當且僅當它不包含與一個圖是平面圖當且僅當它不包含與K K5 5或或K

9、K3,33,3 在在2 2度結度結點內同構點內同構的子圖。的子圖。 。 。 。 。 。 。 。 。 。11第七章第七章 圖論圖論例例5 5 證明證明下圖為非平面圖。下圖為非平面圖。證明證明1 1：應用結論應用結論e k(v-2)/(k-2)e k(v-2)/(k-2)。證明證明2 2：應用應用KruatowskiKruatowski定理定理 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 12第七章第七章 圖論圖論7-6 7-6 對偶圖與著色對偶圖與著色平面圖的應用平面圖的應用定義定義7-6.17-6.1給定給定平面圖平面圖G=G=，它具有面，它具有

10、面F F1 1,F,F2 2,F,Fn n, ,若有圖若有圖G G* *=V= 滿足下列條件：滿足下列條件：(a)(a)對于圖對于圖G G的任一面的任一面F Fi i ，內部有且僅有一個結點，內部有且僅有一個結點v vi i* * V V* * 。(b)(b)對于圖對于圖G G的面的面F Fi i，F Fj j的公共邊界的公共邊界e ek k，存在且僅存在一條邊，存在且僅存在一條邊e ek k* * E E* * ，使得，使得e ek k* *=(v=(vi i* *,v,vj j* *) )，且，且e ek k* *與與e ek k相交。相交。(c)(c)當且僅當當且僅當e ek k只是一個

11、面只是一個面F Fi i的邊界時，的邊界時，v vi i* *存在一個環存在一個環e ek k* *和和e ek k相交。相交。則稱是則稱是G G* *圖圖G G的的對偶對偶圖。圖。顯然，顯然， G G也是圖也是圖G G* *的的對偶對偶圖。圖。13第七章第七章 圖論圖論14第七章第七章 圖論圖論定義定義7-6.27-6.2如果圖如果圖G G的對偶圖的對偶圖G G* *同構于同構于G G，則稱，則稱G G是是自對偶自對偶圖。圖。證明：對自對偶圖證明：對自對偶圖G G有有e=2v-2.e=2v-2.顯然，顯然， 平面圖著色問題就轉換為對鄰接結點著不同色的問平面圖著色問題就轉換為對鄰接結點著不同色

12、的問題。題。對于圖對于圖G G著色時，需要的最少顏色數稱為著色時，需要的最少顏色數稱為G G的著色數，記作的著色數，記作x(G)x(G)。15第七章第七章 圖論圖論Welch PowellWelch Powell法法a)a)將圖將圖G G的結點按度數的遞減次序排列。的結點按度數的遞減次序排列。b)b)用第一種顏色對第一個點著色，并按排列順序，對與前用第一種顏色對第一個點著色，并按排列順序，對與前面著色點面著色點不不鄰接的每一點著上同樣的顏色。鄰接的每一點著上同樣的顏色。c)c)用第二種顏色對尚未著色的點重復用第二種顏色對尚未著色的點重復b) b) ，用第三種顏色重，用第三種顏色重復這種做法，直

13、至所有點全部著色為止。復這種做法，直至所有點全部著色為止。例：對下圖著色。例：對下圖著色。16第七章第七章 圖論圖論定理定理7-6.17-6.1對于對于n n個結點的完全圖個結點的完全圖K Kn n, ,有有x(Kx(Kn n)=n)=n。證明：證明：( (略略) )定理定理7-6.27-6.2設設G G為一個至少具有三個結點的連通平面圖，則為一個至少具有三個結點的連通平面圖，則G G中必有一中必有一個結點個結點u u，使得，使得deg(u)5deg(u)5。證明證明: : ( (握手定理握手定理 及及 定理定理7-5.3 7-5.3 若若v3v3，則，則e3v-6e3v-6) )* *定理定

14、理7-6.37-6.3任意平面圖任意平面圖G G最多是最多是5-5-色的。色的。17第七章第七章 圖論圖論7-7 7-7 無向樹及其性質無向樹及其性質定義定義7-7.1 7-7.1 v連通無回路的無向圖稱為連通無回路的無向圖稱為無向樹無向樹，簡稱，簡稱樹樹, ,常用常用T T表示樹。表示樹。v平凡圖稱為平凡圖稱為平凡樹。平凡樹。v若無向圖若無向圖G G至少有兩個連通分支，則稱至少有兩個連通分支，則稱G G為為森林森林。v在無向樹中，度為在無向樹中，度為1 1的結點稱為的結點稱為樹葉樹葉，度數大于或等于，度數大于或等于2 2的結點稱為的結點稱為分支點分支點或或內點內點。 。 。 。 。 。 。

15、。 。 。18第七章第七章 圖論圖論定理定理7-7.17-7.1 設設G=G=是是n n階階m m條邊的無向圖條邊的無向圖, ,則下面各則下面各命題是等價的：命題是等價的：（1 1）G G是樹。是樹。（2 2）G G中任意兩個結點之間有且僅有一條路。中任意兩個結點之間有且僅有一條路。（3 3）G G中無回路且中無回路且m=n-1m=n-1。（4 4）G G是連通的且是連通的且m=n-1m=n-1。 (5) G(5) G是連通的且是連通的且G G中任何邊均為橋。中任何邊均為橋。 (6) G(6) G中沒有回路，但在任何兩個不同的結點之間加一條中沒有回路，但在任何兩個不同的結點之間加一條新邊，在所

16、得的圖中得到唯一的一個含新邊的圈。新邊，在所得的圖中得到唯一的一個含新邊的圈。19第七章第七章 圖論圖論（1 1）G G是樹。是樹。（2 2）G G中任意兩個結點之間有且僅有一條路。中任意兩個結點之間有且僅有一條路。證明：證明：（1 1）（2 2）G G是樹，根據定義知是樹，根據定義知G G是連通無回路的圖。是連通無回路的圖。 GG是連通的是連通的 GG中任意兩個結點之間存在路。中任意兩個結點之間存在路。假設任意兩個結點假設任意兩個結點u,vu,v之間存在不同的路徑之間存在不同的路徑T T1 1,T,T2 2, ,則則G G中必中必存在存在T T1 1和和T T2 2構成的回路，與已知矛盾。所

17、以構成的回路，與已知矛盾。所以G G中任意兩個中任意兩個結點之間結點之間路徑唯一路徑唯一。20第七章第七章 圖論圖論（2 2）G G中任意兩個結點之間有且僅有一條路。中任意兩個結點之間有且僅有一條路。（3 3）G G中無回路且中無回路且m=n-1m=n-1。 證明：證明：（2 2）（3 3） G G中無環，否則存在環的結點與其自身之間存在長度為中無環，否則存在環的結點與其自身之間存在長度為0 0和和1 1的兩條路，與已知矛盾；若的兩條路，與已知矛盾；若G G中存在長度大于等于中存在長度大于等于2 2的圈，的圈，則圈上各點之間都存在兩條不同的路徑，與已知矛盾。故則圈上各點之間都存在兩條不同的路徑

18、，與已知矛盾。故G G中中無回路無回路。 當當G G是平凡圖時是平凡圖時,m=n-1,m=n-1顯然成立。顯然成立。 設當設當n=k(k1)n=k(k1)時也成立，當時也成立，當n=k+1n=k+1時，設時，設e=(u,v)e=(u,v)為為G G中中一條邊，由于一條邊，由于G G中無回路，所以中無回路，所以G-eG-e為兩個連通分支為兩個連通分支G G1 1,G,G2 2. .設設n ni i,m,mi i (i=1,2)(i=1,2)分別為分別為G G1i1i中的結點數和邊數，很明顯中的結點數和邊數，很明顯n ni ik,k,由由歸納假設知歸納假設知m mi i= n= ni i-1,-1

19、,則則m= mm= m1 1+m+m2 2+1=n+1=n1 1-1+n-1+n2 2-1+1=n-1-1+1=n-121第七章第七章 圖論圖論（3 3）G G中無回路且中無回路且m=n-1m=n-1。（4 4）G G是連通的且是連通的且m=n-1m=n-1。 證明：證明：（3 3）（4 4） 只需證明只需證明G 是連通的是連通的.若若G不是連通的不是連通的,設設G 有有s(s2)個連通分支個連通分支G1,G2, ,GS 。 由于由于Gi (s i11)中均無回路，因而中均無回路，因而Gi全為樹，設全為樹，設Gi中中的的結點數和邊數設結點數和邊數設n ni i,m,mi i . .由前面證明可知，由前面證明可知， mi = ni 1。于。于是，是， m= = = - s=n-ssiim1siin1) 1(siin1由于由于s2，與，與m=n-1m=n-1矛盾。矛盾。22第七章第七章 圖論圖論（4 4）G G是連通的且是連通的且m=n-1m=n-1。 (5) G(5) G是連通的且是連通的且G G中任何邊均為橋。中任何邊均為橋。證明：證明：（4 4）（5 5） 只需證明只需證明G中每條邊均為橋中每條邊均為橋.eE ，均有，均有E(G-e)=n-1-1=n-2，由于，由于n階圖階圖G是連通的至是連通的至少需要