圖論第17章平面圖

1、圖論第17章平面圖在一塊地上蓋有三座房子，并且挖了三口井供房主人使用。由于土質(zhì)和氣候等關(guān)系，這些井中的這一個或那一個常常干枯。因此各座房子的主人有時要到這個井去打水，有時要到那個井去打水，三個井都可能需要去。不久，這三個房子的主人相互間變成了冤家，于是決定修建各家通往三個井的小道，使得他們在去三個井的途中不會相遇。請問：你能否幫他們設(shè)計(jì)整個小道路線，滿足他請問：你能否幫他們設(shè)計(jì)整個小道路線，滿足他們的要求？們的要求？平面圖問題的應(yīng)用對于許多問題，一個圖怎樣畫出來無關(guān)緊要，只要與原來的圖同構(gòu)怎樣畫都可以。但是有些時候的實(shí)際問題要求我們在平面上完成該圖，使得不是節(jié)點(diǎn)的地方不能有邊相交出現(xiàn)。例如單層

2、印刷電路板，集成電路的布線，通訊和交通中的某些問題等，這就是可平面圖問題。雖然交通立交橋、多層電路板已廣泛出現(xiàn)在現(xiàn)實(shí)生活中，但可平面圖問題仍然是其最基本的問題。與平面圖緊密相關(guān)的一個主題就是與平面圖緊密相關(guān)的一個主題就是圖的著色，這是，這是圖論中最為重要最具影響力的主題，也具有很好的圖論中最為重要最具影響力的主題，也具有很好的應(yīng)用。如常見的會議或考試日程的安排等與調(diào)度和應(yīng)用。如常見的會議或考試日程的安排等與調(diào)度和指派等有關(guān)的問題。指派等有關(guān)的問題。 定義定義 17.1如果能將無向圖G畫在平面上使得除頂點(diǎn)外無處相交，則稱G是可平面圖，簡稱平面圖。畫出的無邊相交的圖稱為G的平面嵌入，無平面嵌入的圖

3、稱為非平面圖。定理定理 17.1 平面圖的子圖都是平面圖，非平面圖的母圖都是非平面圖。定理定理 17.2 設(shè)G是平面圖，則在G中增加平行邊或環(huán)后所得的圖仍然為平面圖。定義定義 17.2給定平面圖G的平面嵌入，G的邊將平面劃分成若干個區(qū)域，每個區(qū)域都稱為G的一個面。其中有一個面的面積無限，稱為無限面或者外部面。其余的面的面積有限，稱為有限面或內(nèi)部面。包圍每個面的所有邊組成的回路組稱為該面的邊界，邊界的長度稱為面的次數(shù)。定理定理 17.2定理定理 17.3 平面圖所有面的次數(shù)之和等于邊數(shù)的兩倍。邊界必須是回路定義定義 17.3設(shè)G為簡單平面圖，若在G的任意不相鄰的頂點(diǎn)u，v之間加邊(u,v)，所得

4、圖為非平面圖， 則稱G為極大平面圖。定理定理 17.4極大平面圖是連通的。并且其階數(shù)大于等于3時沒有割點(diǎn)和橋。定理定理 17.5設(shè)G是n(n3)階簡單連通的平面圖，G為極大平面圖當(dāng)且僅當(dāng)G的每個面的次數(shù)均為3。證： 充分性留在第二節(jié)的最后證明，下面只證必要性。 由簡單平面圖，知G中無環(huán)和平行邊。由前面定理可知，G中無割點(diǎn)和橋，于是G中各面的次數(shù)大于或等于3。下面只需證明G各面的次數(shù)不可能大于3.假設(shè)面Ri的次數(shù)deg(Ri)=s4,如圖所示。 在G中，若v1與v3不相鄰，在Ri內(nèi)加邊(v1，v3)不破壞平面性，這與G是極大平面圖矛盾，因而v1與v3必相鄰，由于Ri的存在，邊(v1，v3)必在R

5、i外。 類似地，v2與v4也必相鄰，且邊(v2，v4)也必在Ri外部 。于是必產(chǎn)生(v1，v3)與(v2，v4)相交于Ri的外部，這又矛盾于G是平面圖。所以G的每個面為3條邊所圍，也就是各面次數(shù)均為3，得證。設(shè)G是n(n3)階簡單連通的平面圖，G為極大平面圖當(dāng)且僅當(dāng)G的每個面的次數(shù)均為3。定義定義 17.4若在非平面圖G中任意刪除一條邊，所得圖為平面圖，則稱G為極小非平面圖。圖形編號頂點(diǎn)數(shù)V面數(shù)F棱數(shù)EV+FE（1） 4462（2） 86122（3） 68 122（4） 98 152（5） 99 162圖形編號頂點(diǎn)數(shù)V面數(shù)F棱數(shù)EV+FE（1） 5582（2） 128164（3） 78123定

6、理定理 17.6設(shè)連通平面圖的G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n、m和r，則有n-m+r = 2成立。既然觀察到所有的簡單多面體都具有該性質(zhì)，不妨使用數(shù)學(xué)歸納法邊數(shù)m為0，G為平凡圖，此時n=1, m=0, r=1，結(jié)論成立。設(shè)m=k時結(jié)論也成立。當(dāng)m=k+1時，G存在如下情況：若G是樹，且存在至少一條邊，則至少存在兩片樹葉。設(shè)v為樹葉，令G=G-v，則G的邊數(shù)為k，此時有n-m+r=2，n=n+1，m=m+1，r=r，因此有n-m+r=2成立。若G中包含圈，設(shè)e是圈上某邊，令G=G-e，則G邊數(shù)為k，此時有n=n，m=m+1，r=r+1，因此有n-m+r=2成立有此結(jié)論得證。n=1, m=0,

7、r=1n=2, m=1, r=1n=3, m=2, r=1n=3, m=3, r=2n=4, m=4, r=2n=4, m=5, r=3n=4, m=6, r=4定理定理 17.7 對于具有k(k2)個連通分支的平面圖G，有n-m+r=k+1其中n,m,r分別為G的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)設(shè)G的連通分支分別為G1, G2, . , Gk，且對于Gi，頂點(diǎn)數(shù)，邊數(shù)和面數(shù)分別為ni，mi，ri。則由歐拉公式有ni-mi+ri=2。由于所有的連通分支具有相同的外部面，因此有r=(ri -1)+1= rik+1;而n= ni ，m= mi 。由此n-m+r=2k-k+1=k+1。n-m+r=2n-m+r=2

8、(1+1)(1+1)n-m+r=3n-m+r=3(2+1)(2+1)n-m+r=4n-m+r=4(3+1)(3+1)n-m+r=4n-m+r=4n-m+r=4n-m+r=4定理定理 17.8設(shè)G是連通的平面圖，且每個面的次數(shù)至少為l(l3)，則G的邊數(shù)m與頂點(diǎn)數(shù)n有如下關(guān)系：)2(2mnll定理定理17.9設(shè)平面圖G有k(k2)個連通分支,每個面的次數(shù)至少為l(l3)，則G的邊數(shù)m與頂點(diǎn)數(shù)n有如下關(guān)系：) 1(2mknll定理定理 17.10設(shè)G是n(n3)階m條邊的簡單平面圖，則m3n-6。當(dāng)G是連通圖的情況下，若G是樹，則m=n-13n-6(n3)。若G中存在圈，則圈的長度大于等于3。從而

9、各面的次數(shù)至少為3。根據(jù)定理17.8有m(l/l-2)(n-2)，當(dāng)l3時，(l/l-2)3。因此有m3n-6成立。當(dāng)G是非連通圖的情況下，若G有k個連通分支G1, G2, , Gk，都有mi3ni-6。顯然m=mi 3ni -6k3ni -6=3n-6。定理定理 17.11設(shè)G是n(n3)階m條邊的極大平面圖，則m=3n-6。根據(jù)歐拉公式有r=2+m-n，又因?yàn)镚是極大平面圖，任意面的次數(shù)為3。因此有2m=3r。代入后有m=3n-6。定理定理 17.12設(shè)G是簡單平面圖，則G的最小度5。若最小度至少為6，則根據(jù)握手定理有2m6n，即m3n，與定理7.10矛盾。設(shè)G是n(n3)階簡單連通的平面

10、圖，G為極大平面圖當(dāng)且僅當(dāng)G的每個面的次數(shù)均為3。定理定理 17.5充分性充分性 根據(jù)定理7.3，且在每個面3次的情況下有3r=2mG是連通圖，根據(jù)歐拉公式有r=2+m-n。因此有m=3n-6。若G不是極大平面圖，則存在不相鄰的頂點(diǎn)u，v，使得在增加之后，G仍然是平面圖，故m3n-6。與定理7.11矛盾。定義定義17.5設(shè)e=(u , v)為圖G的一條邊，在G中刪除e，增加新的頂點(diǎn)w，使u，v均與w相鄰，稱為在G中插入2度頂點(diǎn)w。設(shè)w為G中一個2度頂點(diǎn)，w與u，v相鄰，刪除w，增加新邊(u, v)，稱為在G中消去2度頂點(diǎn)w。若兩個圖G1與G2同構(gòu)，或通過反復(fù)插入、消去2度頂點(diǎn)后同構(gòu)，則稱G1與

11、G2同胚。定理定理 17.13圖G是平面圖當(dāng)且僅當(dāng)G中既不含K5同胚子圖子圖也不含K3,3同胚子圖子圖.定理定理 17.14圖G是平面圖當(dāng)且僅當(dāng)G中既不含可以收縮到K5的子圖子圖也不含可以收縮到K3,3的子圖子圖.定義定義17.6 設(shè)G是一個平面圖的平面嵌入，構(gòu)造圖G*如下：在G的每一個面Ri中放置一個頂點(diǎn)v*i，設(shè)e為G的一條邊，若e在G的面Ri和Rj的公共邊界上，則做邊e*=(v*i , v*j)與e相交，且不與其它任何邊相交。若e為G中的橋且在面Ri的邊界上，則作以v*i為端點(diǎn)的環(huán)e*=(v*i , v*i)。稱G*為G的對偶圖。定理定理 17.15 設(shè)G*是連通平面圖G的對偶圖，n*,m*,r*和n,m,r分別為G*和G的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)，則1）n*=r2) m*=m3) r*=n4) 設(shè)G*的頂點(diǎn)v*i位于G的面Ri中，則dG*(v*i)=deg(Ri)。 定理定理 17.16 設(shè)G*是具有k(k2)個連通分支的平面圖G