第四章-平面圖與圖的著色I(xiàn)

2023/9/314.1平面圖定義4.1：若能把圖G畫在一個(gè)平面上，使任何兩條邊都不相交，就稱G可嵌入平面，或稱G是可平面圖?？善矫鎴D在平面上的一個(gè)嵌入稱為平面圖。2023/9/32v1v4v2v3(a)4.1平面圖e1e2e3e4e5e6v1v4v2v3(b)e1e2e3e4e5e6v1v4v3v2(c)e1e2e3e4e5e6可平面圖平面圖平面圖2023/9/334.1平面圖定義4.2：設(shè)G是一個(gè)平面圖，由G的一個(gè)初級(jí)回路圍成的一個(gè)區(qū)域內(nèi)如果不含任何結(jié)點(diǎn)及邊，就稱為G的一個(gè)面或域。包含這個(gè)域的各邊稱為該域的邊界。平面圖G的外邊的無(wú)限區(qū)域稱為無(wú)限域或外部區(qū)域，其他的域叫內(nèi)部域。2023/9/34v1v4v2v3(b)F1F2F3F44.1平面圖e1e2e3e4e5e6F1=v1

e1v2e6

v4e4v1邊界為：{e1

,e6

,e4}F2=v1

e5v3e3

v4e4v1邊界為：{e5

,e3

,e4}F3=v1

e1v2e2

v3e5v1邊界為：{e1

,e2

,e5}F4=v2

e2v3e3

v4e6v2邊界為：{e2

,e3

,e6}2023/9/35v1v4v2v3(c)F1F2F3F44.1平面圖e1e2e3e4e5e6F1=v1

e1v2e6

v4e4v1邊界為：{e1

,e6

,e4}F2=v1

e5v3e3

v4e4v1邊界為：{e5

,e3

,e4}F3=v2

e2v3e3

v4e6v2邊界為：{e2

,e3

,e6}F4=v1

e1v2e2

v3e5v1邊界為：{e1

,e2

,e5}2023/9/364.1平面圖

如果兩個(gè)域有共同的邊界，則稱它們是相鄰的，否則是不相鄰的。如果邊e不是割邊，則e一定是某兩個(gè)域的共同邊界。2023/9/374.1平面圖e7v1v4v2v3F1F2F3F7e1e2e3e4e5e6v5v8v6v7F4F5F6e8e9e10e11e12e13F1=v1

e1v2e6

v4e4v1與F2=v1

e5v3e3

v4e4v1相鄰共同邊界為：e4，割邊e7只是面F7的邊界。2023/9/384.1平面圖定理4.1設(shè)G是有n個(gè)結(jié)點(diǎn)和m條邊的平面連通圖，則G的面的數(shù)目d是

d＝m－n＋2（歐拉公式）證明：設(shè)連通圖G的支撐樹是T。T包含n－1條邊，不包含回路，因此T只有一個(gè)無(wú)限域。2023/9/394.1平面圖TF02023/9/3104.1平面圖

由G是平面圖，每加入一條余樹的邊e，它一定不與其他邊相交，即e一定在某個(gè)域的內(nèi)部，把該域分成兩部分。2023/9/3114.1平面圖TF0eF1F2eeF3F4F52023/9/3124.1平面圖這樣，加入G的m－n＋1條邊，生成了m－n＋1個(gè)新的域。加上無(wú)限域，共有d＝m－n＋2個(gè)域。2023/9/3134.1平面圖推論4.1有n個(gè)結(jié)點(diǎn)和m條邊的平面圖G有k個(gè)連通支，則n－m＋d＝k＋1。推論4.2對(duì)任一平面圖G，恒有

n－m＋d

2。v1v4v2v3F1F2F3F7e1e2e3e4e5e6v5v8v6v7F4F5F6e7e8e9e10e11e122023/9/3144.1平面圖定理4.2設(shè)有n個(gè)結(jié)點(diǎn)和m條邊的平面連通圖G沒有割邊，且每個(gè)域的邊界數(shù)至少是t，則

m

t(n－2)t－2亦即t(n－2)t－2m

m－n＋22mt證明：設(shè)G

有d個(gè)域，每個(gè)域的邊界數(shù)至少是t，且每條邊都與兩個(gè)不同的域相鄰。因此td2m。代入歐拉公式：2023/9/3154.2極大平面圖定義4.3：設(shè)G是有n

3個(gè)結(jié)點(diǎn)的簡(jiǎn)單平面圖，若在任意兩個(gè)不相鄰的結(jié)點(diǎn)vi，vj之間加入邊(vi，vj)，就會(huì)破壞圖的平面性，則稱G是極大平面圖。極大平面圖不是極大平面圖2023/9/3164.2極大平面圖v1v2v3v4v52023/9/3174.2極大平面圖設(shè)有n個(gè)結(jié)點(diǎn)和m條邊的極大平面圖G具有以下性質(zhì)：性質(zhì)1.

G是連通的。性質(zhì)2.

G不存在割邊。性質(zhì)3.

G的每個(gè)域的邊界數(shù)都是3（極大平面圖也稱為平面三角剖分）。性質(zhì)4.

3d=2m。2023/9/3184.2極大平面圖性質(zhì)3.G的每個(gè)域的邊界數(shù)都是3。證明：由G是簡(jiǎn)單圖，沒有自環(huán)和重邊，因此不存在邊界數(shù)為1和2的域。假設(shè)G存在邊界數(shù)大于3的域dj，不妨設(shè)dj是G的內(nèi)部域，域dj的邊界為：

dj=i1

e1

i2

e2

i3

e3

i4

e4i5…，這里結(jié)點(diǎn)i1,i2,i3,i4互不相同。e1i4dje2e3e4i1i2i3i52023/9/3194.2極大平面圖性質(zhì)3.G的每個(gè)域的邊界數(shù)都是3。證明：若結(jié)點(diǎn)i1和i3

不相鄰，則在域dj內(nèi)加入邊(i1,i3)后仍然是平面圖，與G是極大平面圖矛盾，因此邊(i1,i3)

一定存在于域dj之外。e1i4dje2e3e4i1i2i3i5e1i4dje2e3e4i1i2i3i52023/9/3204.2極大平面圖性質(zhì)3.G的每個(gè)域的邊界數(shù)都是3。證明：這時(shí)，在域dj之外不可能存在邊(i2,i4)

。亦即i2和i4

不相鄰，但在域dj內(nèi)加入邊(i2,i4)并不影響G的平面性，得到矛盾。e1i4dje2e3e4i1i2i3i52023/9/3214.2極大平面圖性質(zhì)4.3d=2m。證明：由性質(zhì)2，每條邊都是兩個(gè)不同域的邊界，再由性質(zhì)3即得。2023/9/3224.2極大平面圖定理4.2.1對(duì)有n個(gè)結(jié)點(diǎn)和m條邊的極大平面圖G，有

m＝3n－6，d＝2n－4證明：由極大平面圖的性質(zhì)4

3d=2m代入歐拉公式

d＝m－n＋2整理后即得。2023/9/3234.2極大平面圖定理4.2.2簡(jiǎn)單平面圖G中存在度小于6的結(jié)點(diǎn)。證明：設(shè)簡(jiǎn)單平面圖G的每個(gè)結(jié)點(diǎn)的度都不小于6。由

d(vi)＝2m，得到6n

2m

因?yàn)镚是簡(jiǎn)單平面圖，又有3d

2m。代入歐拉公式的一般形式：n－m＋d

2

有

0=1/3m－m＋2/3m

2，得到矛盾。vi

V2023/9/3244.2極大平面圖例4.2.27個(gè)結(jié)點(diǎn)的完全圖K7不是平面圖。證明：因?yàn)?/p>

7個(gè)結(jié)點(diǎn)的完全圖K7的每個(gè)結(jié)點(diǎn)的度均為6。由定理4.2.2即得證。2023/9/3254.3非平面圖如果對(duì)圖G的任意一種平面嵌入，都至少存在兩條邊，它們?cè)诓皇墙Y(jié)點(diǎn)處相交，稱G為非平面圖。圖平面圖非平面圖2023/9/3264.3非平面圖如果圖G不是簡(jiǎn)單圖，可首先刪去自環(huán)和重邊，因?yàn)樗鼈儾挥绊憟D的平面性。因此只考慮簡(jiǎn)單圖。考查在結(jié)點(diǎn)數(shù)固定情況下邊數(shù)最少的非平面圖。完全圖K3

，K4是可平面圖。任取一條邊e，圖K5

－e也是可平面圖。2023/9/3274.3非平面圖v1v4v2v3v1v2v3K3K4v1v2v3v4v5K5

－v3v5可平面圖2023/9/3284.3非平面圖定理4.3.1完全圖K5是非平面圖。證明：在完全圖K5

中，n＝5，m＝10。如果K5是可平面圖，應(yīng)有m

3n－6。而對(duì)于K5

，3n－6＝9，得到矛盾。由此得到：K5是結(jié)點(diǎn)數(shù)最少的非平面圖。2023/9/3294.3非平面圖例4.3.1完全二分圖K3,3中移去任一邊后是可平面圖。2023/9/3304.3非平面圖定理4.3.2完全二分圖K3,3是非平面圖。K3,3是有6個(gè)結(jié)點(diǎn)的圖中邊數(shù)最少的非平面圖。證明：假設(shè)K3,3是可平面圖，由于n＝6，m＝9。由歐拉公式，d＝5。但K3,3中不含三角形。因此每個(gè)域的邊界數(shù)至少是4，且每條邊都與兩個(gè)不同的域相鄰。所以4d

2m，即20

18，得到矛盾。有6個(gè)結(jié)點(diǎn)的圖中邊數(shù)m<9的圖均為平面圖。2023/9/3314.3非平面圖

K5和K3,3分別記為K(1)和K(2)。定義4.3.1：在圖K(1)和K(2)

上任意增加一些度為2的結(jié)點(diǎn)之后得到的圖稱為K(1)型和K(2)型圖，統(tǒng)稱為K型圖。2023/9/3324.3非平面圖K型(K(1)型和K(2)

型)圖均為非平面圖。2023/9/3334.3非平面圖定理4.3.3(庫(kù)拉圖斯基定理)：G是可平面圖的充要條件是G不存在在K型子圖。K(1)型子圖K(2)型子圖例4.3.2完全圖K6既含有K(1)型子圖，也含有K(2)型子圖，所以是非平面圖。如圖：2023/9/3344.4圖的平面性檢驗(yàn)可平面性檢驗(yàn)的預(yù)處理：1.如果G是非連通的，則分別檢驗(yàn)每一個(gè)連通分支。當(dāng)所有的連通分支都是可平面圖時(shí)，G才是可平面圖。v11v21B1B2B3v12v222023/9/3352.如果G中存在割點(diǎn)v，可把圖G從割點(diǎn)處分離，構(gòu)成若干個(gè)不含割點(diǎn)的連通子圖，稱為塊。4.4圖的平面性檢驗(yàn)2023/9/336G是可平面圖，當(dāng)且僅當(dāng)每個(gè)塊是可平面圖。4.4圖的平面性檢驗(yàn)v1v2v11v21B1B2B3v12v222023/9/3374.4圖的平面性檢驗(yàn)3.移去自環(huán)。v11B1v11B12023/9/3384.4圖的平面性檢驗(yàn)4.移去度為2的結(jié)點(diǎn)vi及其所關(guān)聯(lián)的邊，同時(shí)在vi的兩個(gè)鄰結(jié)點(diǎn)vj,vk之間加入邊(vj,vk)。v11B1B1原圖是可平面圖，當(dāng)且僅當(dāng)新圖是可平面圖。2023/9/3394.4圖的平面性檢驗(yàn)5.移去重邊。B1B12023/9/3404.4圖的平面性檢驗(yàn)反復(fù)運(yùn)用4和5。最后，如果

a.m<9或n<5,則G是可平面圖。

b.m>3n-6，則G是非平面的。

c.不滿足a和b，需要進(jìn)一步檢查。2023/9/3414.4圖的平面性檢驗(yàn)例4.4.1判斷下圖的可平面性。v1v2G由判定規(guī)則2，G有兩個(gè)割點(diǎn)v1和v2

；可分成3個(gè)塊。2023/9/3424.4圖的平面性檢驗(yàn)v11B1對(duì)塊B2，n<5，所以塊B2是平面圖。v21B2v12B3v22由判定規(guī)則4處理塊B1和B3

，得到如下的圖。2023/9/3434.4圖的平面性檢驗(yàn)B1B3v22由判定規(guī)則5

，得到如下的圖。B1B3v22對(duì)塊B3，m<9，所以塊B3是平面圖。2023/9/3444.4圖的平面性檢驗(yàn)由判定規(guī)則4處理塊B1，得到如下的圖。B1由判定規(guī)則5

，得到如下的圖。B1對(duì)塊B1，n<5，所以塊B1是平面圖。2023/9/3454.4圖的平面性檢驗(yàn)例4.4.1判斷下圖的可平面性。v1v2G所以圖G是可平面圖。2023/9/3464.4圖的平面性檢驗(yàn)圖G的平面嵌入如下：v1v2G2023/9/3474.4對(duì)偶圖給定一個(gè)平面圖G定義4.5.1滿足下列條件的圖G*

稱為G

的對(duì)偶圖。

1.在G中每個(gè)域Fi

內(nèi)設(shè)置一個(gè)結(jié)點(diǎn)vi*。

2.對(duì)域Fi和Fj的共同邊界ek，有一條邊

ek*＝(vi*,vj*)

E(G*)，并且與ek相交一次。

3.若邊ek位于域Fi之內(nèi)，則vi*有一自環(huán)ek*與ek相交一次。2023/9/3484.4對(duì)偶圖v1v2v3v4v5v4*v1*v2*v3*F1F2F3F4圖G

的對(duì)偶圖G*

：e1*e1e2e7*e4e2*e3*e3e4*e5e5*e6e6*e72023/9/3494.4對(duì)偶圖v4*v1*v2*v3*圖G

的對(duì)偶圖G*

：e1*e7*e2*e3*e4*e5*e6*2023/9/350

F1

F2

F4

F5

v3v4e1e2e3e4e5

F0

v1v2v54.4對(duì)偶圖求圖G

的對(duì)偶圖G*

：2023/9/351v2*4.4對(duì)偶圖

F0

F1

F2

F3

F4

F5

v1*v0*v3*v4*v5*v1v2v3v4v5e1e1*e2e3e4e5e2*e3*e4*e5*圖G

的對(duì)偶圖G*2023/9/352v2*4.4對(duì)偶圖v1*v0*v3*v4*v5*e1*e2*e3*e4*e5*圖G

的對(duì)偶圖G*2023/9/3534.4對(duì)偶圖v1v2v3v4v5v6v1*v2*v3*求圖G

的對(duì)偶圖G*

：2023/9/3544.4對(duì)偶圖v1*v2*v3*求圖G

的對(duì)偶圖G*

：2023/9/3554.4對(duì)偶圖性質(zhì)4.5.1如果G是平面圖，G一定有對(duì)偶圖G*

，而且G的對(duì)偶圖G*是唯一的。性質(zhì)4.5.2G*

是連通的。性質(zhì)4.5.3若G是平面連通圖，則(G*)*

＝G。性質(zhì)4.5.4平面連通圖G與其對(duì)偶圖G*

的結(jié)點(diǎn)、邊和域之間存在如下對(duì)應(yīng)關(guān)系：m*

＝m

，n*

＝d

，d*

＝n2023/9/3564.4對(duì)偶圖v1v2v3v4v5v4*v1*v2*v3*2023/9/3574.4對(duì)偶圖v1v2v3v4v5v6v1*v2*v3*2023/9/3584.4對(duì)偶圖性質(zhì)4.5.5設(shè)C

是平面圖G的一個(gè)初級(jí)回路，S*是G*中與C的各邊ei對(duì)應(yīng)的邊ei*的集合，則S*是G*的一個(gè)割集。證明：C把G的域分成了兩部分，因此E(G*)－S*把G*的結(jié)點(diǎn)分成不連通的兩部分。由G*是連通圖，G*被分開的兩部分都是連通的，因此S*是G*的一個(gè)割集。2023/9/3594.4對(duì)偶圖v1v2v3v4v5v4*v1*v2*v3*C＝v1v2v32023/9/3604.4對(duì)偶圖v4*v1*v2*v3*C＝v1v2v3S*＝{v2*v3*,v2*v3*,

v2*v4*,}2023/9/3614.4對(duì)偶圖例4.5.3設(shè)i

和j

是平面連通圖無(wú)限域邊界上的兩個(gè)結(jié)點(diǎn)，求G中分離i

和

j的所有割集。ij解：在G的無(wú)限域中添入邊(i,j),

得到圖G1。GG1作G1的對(duì)偶圖G1*。2023/9/3624.4對(duì)偶圖則G1*中除邊(i

,j

)之外的從i

到j(luò)

的初級(jí)道路所對(duì)應(yīng)的G的諸邊都構(gòu)成G中分離i

和j的割集。iji

j

例4.5.3設(shè)i

和j

是平面連通圖無(wú)限域邊界上的兩個(gè)結(jié)點(diǎn)，求G中分離i

和

j的所有割集。ij解：在G的無(wú)限域中添入邊(i,j),

得到圖G1。作G1的對(duì)偶圖G1*。2023/9/3634.4對(duì)偶圖例4.5.3設(shè)i

和j

是平面連通圖無(wú)限域邊界上的兩個(gè)結(jié)點(diǎn)，求G中分離

i

和

j的所有割集。解：在G的無(wú)限域中添入邊(i,j),

得到圖G1。作G1的對(duì)偶圖G1*。則G1*中除邊(i

,j

)之外的從i

到j(luò)

的初級(jí)道路所對(duì)應(yīng)的G的諸邊都構(gòu)成了G中分離i

和

j的割集。i

j

ij2023/9/3644.4對(duì)偶圖四色猜想－四色問題任何一張地圖都可以最多用四種顏色著色，使得具有共同邊界的國(guó)家染上不同的顏色。簡(jiǎn)稱為地圖是4－可著色的。

這里具有共同邊界是指有一整段共同邊界。2023/9/3654.4對(duì)偶圖四色猜想來自英國(guó),1852年由格里斯兄弟提出,1872年由數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出,從而成為世界數(shù)學(xué)難題。1976年6月哈肯和阿佩爾在美國(guó)伊利諾斯大學(xué)用兩臺(tái)不同的電子計(jì)算機(jī)，花了1200個(gè)小時(shí)，作了100億次判斷，完成了四色定理的證明。2023/9/3664.4對(duì)偶圖用1，2，3，4代表四種染色111222342023/9/3674.4對(duì)偶圖一張地圖可看成是一個(gè)平面圖G。作G的對(duì)偶圖G*111222232023/9/3684.4對(duì)偶圖對(duì)平面圖地圖G的域的著色可看成是G的對(duì)偶圖G*的結(jié)點(diǎn)的著色。111222232023/9/3694.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：由于自環(huán)和重邊不影響結(jié)點(diǎn)染色。所以可移去G中的自環(huán)和重邊，得到簡(jiǎn)單平面圖G0。2023/9/3704.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：對(duì)G0的結(jié)點(diǎn)數(shù)用歸納法證明。當(dāng)結(jié)點(diǎn)數(shù)n

5時(shí)，結(jié)論顯然成立；設(shè)當(dāng)簡(jiǎn)單平面圖G0

的結(jié)點(diǎn)數(shù)是n－1時(shí)結(jié)論成立?，F(xiàn)設(shè)G0是有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單平面圖。由定理4.2.2，G0中存在結(jié)點(diǎn)v，d(v)<6。在G0中移去結(jié)點(diǎn)v后得到的圖是G0

，即G0

＝G0－v。由歸納假設(shè)，G0

的結(jié)點(diǎn)是可5－可著色的。

2023/9/3714.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：對(duì)G0

的結(jié)點(diǎn)著好色之后，再把結(jié)點(diǎn)v放回到G0中。由于G0是平面圖，結(jié)點(diǎn)v

一定在G0

的某個(gè)域內(nèi)。若d(v)

4，或者d(v)＝5，同時(shí)v

的鄰點(diǎn)沒有用完5種顏色，再將G0

的結(jié)點(diǎn)著色中鄰接于v

的結(jié)點(diǎn)所未用的顏色給結(jié)點(diǎn)v

即可得G0的結(jié)點(diǎn)5-著色。2023/9/3724.5對(duì)偶圖vv2023/9/3732023/9/3744.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：如果G0中，結(jié)點(diǎn)v的鄰點(diǎn)恰好用了5種顏色，比如1,2,3,4,5。2023/9/3752023/9/3764.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：設(shè)在G0

的著色中，G0中與結(jié)點(diǎn)v鄰接的著顏色i

的結(jié)點(diǎn)記為vi。設(shè)G13是G0

＝G0－v的由著顏色1和3的結(jié)點(diǎn)導(dǎo)出的子圖。2023/9/3772023/9/3784.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：若v1和v3分別屬于G13的不同連通支，則將v1所在的連通支的各結(jié)點(diǎn)著的顏色1和3對(duì)換。對(duì)換后，在G0

的結(jié)點(diǎn)5－著色中，G0

的結(jié)點(diǎn)v

的鄰點(diǎn)沒有用到顏色1

，所以在G0中可用顏色1

給結(jié)點(diǎn)v著色，得G0的結(jié)點(diǎn)5-著色。2023/9/3794.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：如果v1和v3屬于G13的同一個(gè)連通支，則存在由v1到v3

的、結(jié)點(diǎn)交替著顏色1和3的道路P。在G0中P＋(v,v1)＋(v,v3)構(gòu)成一個(gè)回路C。C把v2與v4

、v5分隔在不同的區(qū)域。因此，在G0中不存在由v2到v4

的、結(jié)點(diǎn)交替著顏色2和4的道路。2023/9/3804.5對(duì)偶圖2023/9/3814.4對(duì)偶圖－5色定理定理4.5.2每一個(gè)平面圖G的結(jié)點(diǎn)是5－可著色的。證明：在G0

＝G0－v的由著顏色2和4的結(jié)點(diǎn)導(dǎo)出的子圖G24

中，v2和v4分別屬于G24的不同連通支。則將v2所在的連通支的各結(jié)點(diǎn)著的顏色2和4對(duì)換。對(duì)換后，在G0

的結(jié)點(diǎn)5－著色中，G0

的結(jié)點(diǎn)v

的鄰點(diǎn)沒有用到顏色2

，所以在G0中可用顏色2

給結(jié)點(diǎn)v著色，得G0的結(jié)點(diǎn)5-著色。2023/9/3824.2極大平面圖推論4.2.1設(shè)有n個(gè)結(jié)點(diǎn)和m條邊的任意簡(jiǎn)單平面圖G滿足m

3n－6，d

2n－4證明：設(shè)G的域的邊界數(shù)分別為E1,E2,…,Ed，由G中沒有自環(huán)和重邊，所以Ei

3，1i

d。如果G中沒有割邊，則

E1＋E2＋…＋Ed＝2m，若G有割邊，則E1＋E2＋…＋Ed

2m?？傊?m

E1＋E2＋…＋Ed3d。代入歐拉公式即得。2023/9/3834.4圖的平面性檢驗(yàn)設(shè)H是G的可平面子圖，如果在G－H中存在另一個(gè)G的平面子圖B，且B與H有2個(gè)以上共同結(jié)點(diǎn)，則稱B是G中H的片，片B與H的公共結(jié)點(diǎn)稱為片B的附著點(diǎn)。2023/9/3844.4圖的平面性檢驗(yàn)例4.4.2在圖G中，令H是回路(v1,v2,v3,v4)，則H是G的可平面子圖。v1v2v3v4v5G2023/9/385

4.4圖的平面性檢驗(yàn)在圖G中，H＝(v1,v2,v3,v4)有三個(gè)片：B1＝{(v2,v4)}，附著點(diǎn)是v2,v4

；B2＝{(v1,v3)}，附著點(diǎn)是v1,v3

；B3＝{(v1,v5),(v2,v5),(v3,v5),(v4,v5)}，附著點(diǎn)是v1,v2,v3,v4

；v1v2v3v4v4v1v2v3v1v2v3v4v5B1B2B32023/9/3864.4圖的平面性檢驗(yàn)可平面子圖H的片2023/9/3874.4圖的平面性檢驗(yàn)命題：設(shè)H是圖G的一個(gè)可平面子圖，H是子圖H的一個(gè)平面嵌入，令B是G中H的片。則只有當(dāng)片B的所有附著點(diǎn)都在H

的某個(gè)面

f

的邊界上時(shí)，片B才能畫在H

的一個(gè)面內(nèi)?！玽1v2v3v4v4v1v2v3v1v2v3v4v5B1B2B32023/9/3884.4圖的平面性檢驗(yàn)設(shè)H是例4.4.2的子圖H的一個(gè)平面嵌入。片B1＝{(v2,v4)}

畫在H

的內(nèi)部面上，得到的子圖是H1，H1的平面嵌入是H1

?！玽4v1v2v3B1H1～2023/9/3894.4圖的平面性檢驗(yàn)此時(shí)，片B2

的所有附著點(diǎn)都位于

H1

的外部面的邊界上。把B2畫在H1

的外部面上得到子圖H2。H2的平面嵌入是H2?！玽4v1v2v3