離散數(shù)學(xué)第七章第五節(jié)

1、1第7-5講 平面圖1. 平面圖的概念2. 歐拉公式3. 庫拉托夫斯基定理4. 課堂練習(xí)5. 第7-5講 作業(yè)21、平面圖的概念（1）定義1 能畫在一個(gè)平面上且任何兩邊除端點(diǎn)外互不相交的圖稱為平面圖。例：判斷下面各圖例：判斷下面各圖是否為平面圖。是否為平面圖。 (1) (2) (3)是平是平面面圖，圖，(4)不是平不是平面面圖。圖。31、平面圖的概念（2）定義2 平面圖G的某個(gè)平面表示將G所在的平面劃分成若干區(qū)域，每個(gè)區(qū)域叫圖G的一個(gè)面；包圍每個(gè)面的邊稱為該面的邊界；邊界上邊的條數(shù)叫該面的次數(shù)，面r的次數(shù)記作deg(r)。 將將平面圖平面圖G的一個(gè)邊不交叉的圖畫在一個(gè)平面上，稱為圖的一個(gè)邊不交

2、叉的圖畫在一個(gè)平面上，稱為圖G的一個(gè)的一個(gè)平面表示，也叫做相應(yīng)于，也叫做相應(yīng)于G的的地圖。 面積為無限的面積為無限的面叫面叫無限無限面面，或，或外部面外部面；面積為有限的面積為有限的面叫面叫有限有限面面，或，或內(nèi)部面內(nèi)部面。圖圖(1)有有4個(gè)面。個(gè)面。圖圖(2)有有3個(gè)面。個(gè)面。deg(r1)=3deg(r2)=5deg(r3)=441、平面圖的概念（3）定理1 有限平面圖各面次數(shù)之和等于邊數(shù)的2倍。證：因一條邊或是兩個(gè)面的證：因一條邊或是兩個(gè)面的公共邊，或公共邊，或在一個(gè)在一個(gè)面中作為該面面中作為該面的邊界被計(jì)算過兩次，所以各面次數(shù)之和等于邊數(shù)的兩倍的邊界被計(jì)算過兩次，所以各面次數(shù)之和等于邊

3、數(shù)的兩倍。圖圖(1)有有6條邊，條邊，4個(gè)面，每面次個(gè)面，每面次數(shù)皆為數(shù)皆為3。deg(r1)=3deg(r2)=5deg(r3)=4圖圖(2)有有6條邊，有條邊，有3個(gè)面，個(gè)面，各面次數(shù)之和為各面次數(shù)之和為12。52、歐拉公式（1）定理2 設(shè)G是連通平面圖，有v v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則 v-e+r=2 (歐拉公式)證：對(duì)對(duì)邊數(shù)用歸納法證明。邊數(shù)用歸納法證明。 若若G G為平凡圖，則為平凡圖，則v=1,e=0,r=1,v=1,e=0,r=1,公式成立。公式成立。 若若G G僅有一條邊，則僅有一條邊，則v=2,e=1,r=1,v=2,e=1,r=1,公式成立；或公式成立；或v=1,e=1,

4、r=2,v=1,e=1,r=2,公式仍然成公式仍然成立。立。 設(shè)設(shè)G G有有k k條邊時(shí)公式成立。當(dāng)條邊時(shí)公式成立。當(dāng)G G有有k+1k+1條邊時(shí)，設(shè)其結(jié)點(diǎn)數(shù)為條邊時(shí)，設(shè)其結(jié)點(diǎn)數(shù)為v v，面數(shù)為，面數(shù)為r r，可分兩種情況討論：可分兩種情況討論： (1)(1)如如G G中有度數(shù)為中有度數(shù)為1 1的結(jié)點(diǎn)的結(jié)點(diǎn)，刪除該結(jié)點(diǎn)及其關(guān)聯(lián)的一條邊得圖，刪除該結(jié)點(diǎn)及其關(guān)聯(lián)的一條邊得圖GG。顯。顯然，然， GG也是連通平面圖，設(shè)也是連通平面圖，設(shè)GG的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)依次為的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)依次為vv、e=ke=k、rr，按歸納假設(shè)應(yīng)滿足歐拉公式，即，按歸納假設(shè)應(yīng)滿足歐拉公式，即v-e+r=2v-e+r=

5、2，亦即，亦即(v-1)-(e-1)+r=2(v-1)-(e-1)+r=2，從而有，從而有v-e+r=2v-e+r=2。 (2)(2)如如G G中沒有度數(shù)為中沒有度數(shù)為1 1的結(jié)點(diǎn)的結(jié)點(diǎn)，則在有限面的邊界中刪除一條邊得圖，則在有限面的邊界中刪除一條邊得圖GG。 GG也是連通平面圖且邊數(shù)等于也是連通平面圖且邊數(shù)等于k k，按歸納假設(shè)應(yīng)滿足歐拉公式，即，按歸納假設(shè)應(yīng)滿足歐拉公式，即v-e+r=2v-e+r=2，亦即，亦即v-(e-1)+(r-1)=2v-(e-1)+(r-1)=2，從而有，從而有v-e+r=2v-e+r=2。 綜上所述，當(dāng)邊數(shù)為綜上所述，當(dāng)邊數(shù)為k+1k+1時(shí)公式成立。定理得證。時(shí)

6、公式成立。定理得證。62、歐拉公式（2）推論1 設(shè)G是有v v個(gè)結(jié)點(diǎn)、e條邊的連通簡單平面圖，且v3，則 e3v-6證：設(shè)設(shè)G G的面數(shù)為的面數(shù)為r,r,當(dāng)當(dāng)v=3,e=2v=3,e=2時(shí)，公式成立。時(shí)，公式成立。當(dāng)當(dāng)e e 3 3時(shí)，時(shí)，因因G G為為簡單圖，簡單圖，每面的次數(shù)不小于每面的次數(shù)不小于3 3。根據(jù)定理根據(jù)定理1 1可知，可知，2e2e 3r,3r,即即r r 2e/32e/3。再應(yīng)用歐拉公式得：。再應(yīng)用歐拉公式得： v-e+2e/3v-e+2e/3 2 2 即即 e e 3v-63v-6。 例如，應(yīng)用推論例如，應(yīng)用推論1可知可知K5不是平面圖不是平面圖 (以前從直觀上得到過這一

7、結(jié)論以前從直觀上得到過這一結(jié)論)。因。因K5是是連通簡單平面圖，連通簡單平面圖，v v=5, 3v-6=9=5, 3v-6=9，而，而e=10e=10，不滿足推論給出的條件。不滿足推論給出的條件。 推論推論1給出了結(jié)點(diǎn)數(shù)大于等于給出了結(jié)點(diǎn)數(shù)大于等于3的連通簡單平面圖應(yīng)滿足的的連通簡單平面圖應(yīng)滿足的必要條件，所以可用來判斷某些圖必要條件，所以可用來判斷某些圖不是平面圖。平面圖。72、歐拉公式（3）推論2 設(shè)G是v v個(gè)結(jié)點(diǎn)、e條邊的連通平面圖，且G的各面的次數(shù)大于等于4，則e2v-4 證：由所由所設(shè)，設(shè)，G G的的各面各面邊界邊數(shù)的總和大于等于邊界邊數(shù)的總和大于等于4r,4r,這里這里r r為為

8、G G的的面數(shù)。因每邊為兩個(gè)面的邊界或作為一個(gè)面的邊界時(shí)按兩條邊面數(shù)。因每邊為兩個(gè)面的邊界或作為一個(gè)面的邊界時(shí)按兩條邊計(jì)算，所以計(jì)算，所以2e2e 4r4r，即，即r r e/2e/2。再應(yīng)用歐拉公式得：。再應(yīng)用歐拉公式得： 2=v-e+r 2=v-e+r v-e+e/2=v-e/2 v-e+e/2=v-e/2 即即 e e 2v-42v-4。 例如，應(yīng)用推論例如，應(yīng)用推論1可知可知K3，3不不是平面圖是平面圖 。因。因K3，3是連通平面是連通平面圖，每個(gè)面由四條邊圍成，圖，每個(gè)面由四條邊圍成，v v=6, =6, 2v-4=82v-4=8，而，而e=9e=9，不滿足推論給，不滿足推論給出的條

9、件。出的條件。 推論推論2給出了各面次數(shù)大于等于給出了各面次數(shù)大于等于4的連通平面圖應(yīng)滿足的必的連通平面圖應(yīng)滿足的必要條件，所以可用來判斷某些圖要條件，所以可用來判斷某些圖不是平面圖。平面圖。83、庫拉托夫斯基定理（1）定義3 給定圖G1、G2，如果它們同構(gòu)，或通過反復(fù)插入或刪除度數(shù)為2的之后結(jié)點(diǎn)它們同構(gòu),則稱G1與G2在二度結(jié)點(diǎn)內(nèi)同構(gòu)。 插入或刪除2度結(jié)點(diǎn)示意圖 歐拉公式歐拉公式可用來判斷某些圖可用來判斷某些圖不是平面圖。但不能用來判斷平面圖。但不能用來判斷某圖是平面圖。波蘭數(shù)學(xué)家某圖是平面圖。波蘭數(shù)學(xué)家Kuratowski給出了一個(gè)判斷平面給出了一個(gè)判斷平面圖的充分必要條件。為此，圖的充分

10、必要條件。為此，先介紹先介紹“在二度結(jié)點(diǎn)內(nèi)同構(gòu)在二度結(jié)點(diǎn)內(nèi)同構(gòu)”的的概念。概念。93、庫拉托夫斯基定理（2）定理3 （Kuratowski定理）一個(gè)圖是平面圖，當(dāng)且僅當(dāng)它不包含與K3,3或K5在二度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。（定理3的證明非常復(fù)雜，從略） 歐拉公式歐拉公式可用來判斷某些圖可用來判斷某些圖不是平面圖。但不能用來判斷平面圖。但不能用來判斷某圖是平面圖。波蘭數(shù)學(xué)家給出了一個(gè)判斷平面圖的充分必某圖是平面圖。波蘭數(shù)學(xué)家給出了一個(gè)判斷平面圖的充分必要條件。要條件。103、庫拉托夫斯基定理（3）定理3 （Kuratowski定理）一個(gè)圖是平面圖，當(dāng)且僅當(dāng)它不包含與K3,3或K5在二度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖

11、。 用用KuratowskiKuratowski定理定理來判斷某圖是平面圖的例子來判斷某圖是平面圖的例子： 證明證明Petersen圖是非平面圖。圖是非平面圖。114、課堂練習(xí)(1)練習(xí)1 應(yīng)用歐拉公式應(yīng)用歐拉公式證明證明Petersen圖是非平面圖。圖是非平面圖。解：PetersenPetersen圖中，圖中，v=10v=10，e=15e=15，從，從圖上可以看出，每個(gè)面由五邊圍成，圖上可以看出，每個(gè)面由五邊圍成，根據(jù)定理根據(jù)定理7-5.17-5.1，有限平面圖各面次，有限平面圖各面次數(shù)之和等于邊數(shù)的兩倍。數(shù)之和等于邊數(shù)的兩倍。如果如果PetersenPetersen圖是平面圖，則圖是平面圖，則 2e=5r2e=5r所以所以 r=2e/5=6r=2e/5=6但是但是 v-e+r=10-15+6=1v-e+r=10-15+6=1 2 2這說明這說明PetersenPetersen圖不滿足歐拉公式，圖不滿足歐拉公式，故它不是平面圖。故它不是平面圖。124、課堂練習(xí)(2)練習(xí)2 設(shè)設(shè)G G是一個(gè)連通是一個(gè)連通平面圖，且至少有平面圖，且至少有3 3個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)。則。則G必必有一個(gè)結(jié)點(diǎn)有一個(gè)結(jié)點(diǎn)u，使得，使得deg(u) 5