2023/10/101五宮殿問題五座宮殿兩兩有路相通，但要求不交叉1930年Kuratowski給出了充足必要條件，嚴(yán)格證明了五宮修路問題是無解。第1頁2023/10/102平面圖基本概念可平面圖(planargraph)或平面圖(planegraph):能夠畫在平面上,使得邊與邊不在非頂點處相交圖平面嵌入(imbedding):畫在平面上使得邊與邊不在非頂點處相交非平面圖(planegraph):無平面嵌入圖.K1,K2,K3,K4都是平面圖；完全二部圖K1,n,K2,n也是平面圖第2頁2023/10/103平面圖定理定理17.1平面圖子圖都是平面圖,非平面圖母圖都是非平面圖

由定理17.1立即可知,Kn(n≤4)和K2,n(n≥1)所有子圖都是平面圖;含K5或K3,3作為子圖圖都是非面圖，尤其地Kn(n≥5)和Ks,t(s,t≥3)都是非平面圖定理17.2

設(shè)G是平面圖，則在G中加平行邊或環(huán)后所得圖還是平面圖第3頁2023/10/104面(face)面(face):G邊將G所在平面劃提成若干個區(qū)域，每個區(qū)域稱為G一種面，記成R其中面積無限區(qū)域稱為無限面或外部面，常記成R0，面積有限區(qū)域稱為有限面或內(nèi)部面面邊界(boundary):與R關(guān)聯(lián)邊和頂點(包圍R所有邊)組成回路組(不連通時也許是多條回路)面次數(shù)(degree):deg(R)=邊界長度第4頁5個面.

R1邊界為圈abdc,deg(R1)=4;R2邊界為圈efg,deg(R2)=3;R3邊界為環(huán)h,deg(R3)=1;

R4邊界為圈kjl,deg(R4)=3.

外部面R0邊界由abefgdc和kjihil組成，deg(R0)=13.2023/10/105第5頁2023/10/106平面嵌入非唯一同一種平面圖能夠有不一樣形狀平面嵌入，但它們都是同構(gòu)，面?zhèn)€數(shù)保持不一樣,常記為r.另外，還能夠?qū)⒁环N平面嵌入中某個有限面變換成無限面，無限面變換成有限面，得到不一樣形狀另一種平面嵌入。第6頁2023/10/107有關(guān)面握手定理定理17.3：

ri=1deg(Ri)=2m.與點度數(shù)非常類似!

ni=1d(vi)=2m.第7頁2023/10/108極大(maximal)平面圖極大平面圖:是簡單平面圖,不過在任意兩個不相鄰頂點之間加邊就是非平面圖。K5-e,K4第8頁2023/10/109極大平面圖性質(zhì)1(定理17.4)極大平面圖是連通。證明：若不連通，則最少有兩個連通分枝，分別取頂點u和v，連接u,v仍然是平面圖，矛盾！當(dāng)n3時，極大平面圖是沒有割點和橋。第9頁2023/10/1010極大平面圖性質(zhì)2(定理17.5)n(3)階簡單連通平面圖是極大平面圖

R,deg(R)=3事實上是充要條件。第10頁2023/10/1011極小(minimal)平面圖極小平面圖:若在非平面圖G中任意刪除一條邊,所得圖為平面圖。K5,K3,3都是極小非平面圖.第11頁2023/10/1012頂點,邊與面關(guān)系歐拉公式:設(shè)G是連通平面圖,則n-m+r=2

其中r是G面數(shù).證明對邊數(shù)m作歸納法.(1)m＝0時,G為孤立點,此時n＝1,r＝1,結(jié)論自然成立.(2)設(shè)m＝k-1(k≥1)時結(jié)論成立,要證明m＝k時結(jié)論成立.第12頁首先,若G為樹,任取一樹葉v并刪除它,得G'＝G-v,

G'中有n'＝n-1個頂點m'＝m-1條邊,r'＝r,由歸納假設(shè)有下式成立;n'-m'+r'＝2,即(n-1)-(m-1)+r＝2,整頓后得n-m+r＝2.其次,G不是樹,證明則G中必有初級回路.設(shè)C為一初級回路,e在C上.令G'＝G-e,由于e在C上,因此,G'仍連通,在G'中,n'＝m',m'＝m-1,r'＝r-1,利用歸納假設(shè)可得

n-m+r＝2.2023/10/1013第13頁2023/10/1014頂點,邊與面關(guān)系歐拉公式(推廣形式)

:設(shè)G是平面圖,則n-m+r=1+k

其中r是G面數(shù),k是G連通分支數(shù)證明：設(shè)G有連通分支G1,G2,…,Gk,并設(shè)Gi頂點數(shù),邊數(shù),面數(shù)分別為ni,mi,ri,i=1,2,…,k.由歐拉公式ni-mi+ri=2由于每個Gi有一種外部面,而G只有一種外部面,因此G面數(shù)r=

ki=1ri-k+1.而m=

ki=1mi,n=

ki=1ni.于是2k=

ki=1(ni-mi+ri)=

ki=1ni-

ki=1mi+

ki=1ri=n-m+r-1.經(jīng)整頓得n-m+r=k+1.第14頁2023/10/1015平面圖中邊與頂點個數(shù)關(guān)系定理8:設(shè)G是連通平面圖,G各面次數(shù)最少是d(3),則m(n-2)[d/(d-2)]定理9:設(shè)平面圖G有k個連通分支,G

各面次數(shù)最少是d(3),則m(n-k-1)[d/(d-2)]第15頁2023/10/1016K5和K3,3都不是平面圖.定理10:設(shè)n(3)階簡單平面圖G有m條邊,則m3n-6.定理11

:設(shè)n(3)階簡單極大平面圖G有m條邊,則m=3n-6.定理12:設(shè)G是簡單平面圖,則(G)5.第16頁2023/10/1017極大平面圖充要條件定理7:n(3)階簡單連通平面圖是極大平面圖

R,deg(R)=3證明：() 因2m=3r,r=2+m-n,故m=3n-6.

若G不是極大平面圖，則G中一定存在不相鄰頂點u，v，使得G’＝G∪(u，v)還是簡單平面圖，而G’邊數(shù)m’=m+1，n’=n.故 m’>m=3n-6=3n’-6, 與G’是簡單平面圖矛盾。第17頁2023/10/1018小結(jié)平面圖連通平面圖簡單平面圖極大平面圖n-m+r=k+1n-m+r=2m3(n-2)m=3(n-2)m(n-k-1)[d/(d-2)]m(n-2)[d/(d-2)]第18頁2023/10/1019平面圖判斷同胚Kuratowski定理第19頁2023/10/1020同胚(homomorphism)插入2度頂點w:把(u,v)變成(u,w),(w,v)刪除2度頂點w:deg(w)=2,把(u,w),(w,v)變成(u,v)同胚:G1與G2同構(gòu),或通過反復(fù)插入或刪除2度頂點后同構(gòu)uuvvw第20頁2023/10/1021邊收縮設(shè)e=(u,v)E,刪除邊e,且用一種新頂點w替代e兩個端點，與u,v關(guān)聯(lián)所有邊都關(guān)聯(lián)到w上，得到圖稱為是e收縮。第21頁2023/10/1022Kuratowski定理定理13:圖G是平面圖

G沒有與K5或K3,3同胚子圖定理14:圖G是平面圖

G沒有能夠邊收縮到K5或K3,3子圖第22頁2023/10/1023例第23頁2023/10/1024同胚例(1)K3,3第24頁2023/10/1025同胚例(2)K3,3第25頁2023/10/1026邊收縮例(2)K5第26頁2023/10/1027同胚例(3)K5K3,3第27頁2023/10/1028對偶圖(dualgraph)對偶圖:平面圖G=<V,E>對偶圖是G*=<V*,E*>:在G每一種面Ri中放置一種點vi*,若e是面Ri和Rj邊界公共邊，則對應(yīng)點vi*和vj*之間有一條邊e*

與e相交。第28頁2023/10/1029對偶圖對偶圖:平面圖G=<V,E>對偶圖是G*=<V*,E*>,設(shè)G和G*面集合是R和R*,則V*與R,E*與E,都是一一對應(yīng).環(huán)與橋?qū)?yīng)第29頁2023/10/1030對偶圖性質(zhì)對偶圖是連通平面圖環(huán)與橋互相對偶平行邊對偶于2個面之間多條邊界G1

G2,不一定G1*

G2*第30頁2023/10/1031對偶圖性質(zhì)2n*=r,m*=m,r*=n-k+1,dG*(vi*)=deg