離散課件 17平面圖

第十七章

平面圖17.1平面圖的基本概念17.2歐拉公式17.3平面圖的判斷17.4平面圖的對偶圖定義1.如果能將無向圖G畫在平面上使得除頂點外無邊相交,則稱G是可平面圖,簡稱平面圖.畫出的無邊相交的圖稱為G的平面嵌入.無平面嵌入的圖稱為非平面圖.

17.1平面圖的基本概念平面圖平面嵌入平面嵌入定理1.

平面圖的子圖是平面圖,非平面圖的母圖是非平面圖.定義2.

給定平面圖G的平面嵌入,G的邊將平面劃分成若干區(qū)域,每個區(qū)域都稱為G的一個面.其中有一個面的面積無限,稱為外部面(無限面),其余面的面積有限,稱為內(nèi)部面(有限面).注:對于任意平面嵌入G,外部面一定存在,內(nèi)部面不一定存在.內(nèi)部面不存在?G是樹(連通).具有6個面的平面嵌入,其中f1是外部面,其余5個面是內(nèi)部面定義3.面與它周界上的頂點和邊是關(guān)聯(lián)的.注:若e是割邊,則只有一個面和e關(guān)聯(lián);否則有兩個面和e關(guān)聯(lián).定義4.面f的度是指和它關(guān)聯(lián)的邊的條數(shù),記作dG(f).注:割邊對面的度的貢獻為2.d(f2)=4,d(f5)=6定理2.若G是平面嵌入,則d(f)=2|E(G)|.定義5.設(shè)G是簡單平面圖,若在G的任意兩不相鄰頂點之間加一條邊,所得圖為非平面圖,則稱G是極大平面圖.若在非平面圖G中任意刪除一條邊,所得圖為平面圖,則稱G是極小非平面圖.極大平面圖極小非平面圖定理3.設(shè)G是簡單連通平面圖,則G為極大平面圖當且僅當G的每個面的度為3.17.2歐拉公式定理1.

(歐拉公式)設(shè)連通平面嵌入G的頂點數(shù),邊數(shù)和面數(shù)分別為n,m和r,則n-m+r=2.定理1.(歐拉公式的推廣)設(shè)有k(k1)個連通分支的平面嵌入G的頂點數(shù),邊數(shù)和面數(shù)分別為n,m和r,則n-m+r=k+1.推論1.設(shè)G是n(n3)點m邊的簡單平面圖,則m3n-6.注:G是n(n3)點m邊的極大平面圖當且僅當m=3n-6.推論2.若G是簡單平面圖,則(G)5.推論3.

K5是非平面圖.推論4.

K3,3是非平面圖.例：有三座城市A1,A2,A3，要修建高速公路與另外三座城市B1,B2,B3直接相連通.能否設(shè)計一個公路網(wǎng)絡(luò)使任意兩條高速公路彼此不交叉？解：用點代表城市，兩城市之間修建高速公路則連邊.問題轉(zhuǎn)化為公路網(wǎng)絡(luò)是否為平面圖？K3,3是非平面圖，故所求公路網(wǎng)絡(luò)不存在.17.3平面圖的判斷定義1.邊稱為被剖分,是指刪去它,并換上一條連接它的兩個端點而長為2的路.邊e

邊e被剖分定義2.圖G的一個剖分圖是指把G的邊進行一系列剖分而得到的圖.K4的一個剖分圖定理1.(Kuratowski定理)一個圖是平面圖當且僅當它不包含K5或K3,3的剖分圖.定理1.(Kuratowski定理)一個圖是平面圖當且僅當它經(jīng)收縮變換后不含子圖K5或K3,3.例1.證明Petersen圖是非平面圖.證法一:利用歐拉公式.證法二:利用定理1.證法三:利用定理1.17.4平面嵌入的對偶圖定義1.設(shè)G是一個平面圖的平面嵌入,構(gòu)造G的對偶圖G*如下:對于G的每個面f,都有G*的頂點f*與之對應(yīng),對于G的每條邊e,都有G*的邊e*與之對應(yīng);G*中的頂點f*和g*由邊e*連接當且僅當G中與頂點f*和g*對應(yīng)的面f和g被邊e分隔.注:平面嵌入的對偶圖是平面圖.其平面嵌入的畫法:在G的每個面f中放置頂點f*,然后畫出邊e*,使它穿過G的邊e恰好一次(且不穿過G的其它邊).注:e*是G*的環(huán)當且僅當e是G的割邊.GG*平面嵌入G與其對偶圖G*之間的關(guān)系:(1)n*=r;(2)m*=m;(3)r*=n;(4)d(fi)=dG*(vi*);其中n,m,r分別表示頂點數(shù),邊數(shù)和面數(shù);fi表示G中的一個面,