圖論特殊平面圖與平面圖的對偶圖

圖論課件特殊平面圖與平面圖的對偶圖1第一頁，共三十四頁，2022年，8月28日本次課主要內(nèi)容(一)、一些特殊平面圖(二)、平面圖的對偶圖特殊平面圖與平面圖的對偶圖

1、極大平面圖及其性質(zhì)

2、極大外平面圖及其性質(zhì)2第二頁，共三十四頁，2022年，8月28日

1、極大平面圖及其性質(zhì)(一)、一些特殊平面圖對于一個簡單平面圖來說，在不鄰接頂點對間加邊，當(dāng)邊數(shù)增加到一定數(shù)量時，就會變成非平面圖。這樣，就啟發(fā)我們研究平面圖的極圖問題。定義1設(shè)G是簡單可平面圖，如果G是Ki(1≦i≦4),或者在G的任意非鄰接頂點間添加一條邊后，得到的圖均是非可平面圖，則稱G是極大可平面圖。極大可平面圖的平面嵌入稱為極大平面圖。3第三頁，共三十四頁，2022年，8月28日注：只有在單圖前提下才能定義極大平面圖。引理設(shè)G是極大平面圖，則G必然連通；若G的階數(shù)大于等于3，則G無割邊。極大平面圖非極大平面圖極大平面圖

(1)先證明G連通。若不然，G至少兩個連通分支。設(shè)G1與G2是G的任意兩個連通分支。4第四頁，共三十四頁，2022年，8月28日把G1畫在G2的外部面上，并在G1,G2上分別取一點u與v.連接u與v得到一個新平面圖G*。但這與G是極大平面圖相矛盾。

(2)當(dāng)G的階數(shù)n≥3時，我們證明G中沒有割邊。若不然，設(shè)G中有割邊e=uv，則G-uv不連通，恰有兩個連通分支G1與G2。設(shè)u在G1中，而v在G2中。由于n≥3,所以，至少有一個分支包含兩個以上的頂點。設(shè)G2至少含有兩個頂點。又設(shè)G1中含有點u的面是f,將G2畫在f內(nèi)。由于G是單圖，所以，在G2的外部面上存在不等于點v的點t?，F(xiàn)在，在G中連接點u與t得新平面圖G*,它比G多一條邊。這與G的極大性相矛盾。5第五頁，共三十四頁，2022年，8月28日下面證明極大平面圖的一個重要性質(zhì)。定理1設(shè)G是至少有3個頂點的平面圖，則G是極大平面圖，當(dāng)且僅當(dāng)G的每個面的次數(shù)是3且為單圖。注：該定理可以簡單記為是“極大平面圖的三角形特征”，即每個面的邊界是三角形。證明：“必要性”由引理知，G是單圖、G無割邊且G的每個面的次數(shù)至少是3。假設(shè)G中某個面f的次數(shù)大于等于4。記f的邊界是v1v2v3v4…vk。如下圖所示。6第六頁，共三十四頁，2022年，8月28日如果v1與v3不鄰接，則連接v1v3，沒有破壞G的平面性，這與G是極大平面圖矛盾。所以v1v3必須鄰接，但必須在f外連線；同理v2與v4也必須在f外連線。但邊v1v3與邊v2v4在f外交叉，與G是平面圖矛盾！所以，G的每個面次數(shù)一定是3.定理的充分性是顯然的。v1v2v3v4v5vkf7第七頁，共三十四頁，2022年，8月28日推論：設(shè)G是n個點，m條邊和ф?zhèn)€面的極大平面圖，且n≥3.則：(1)m=3n-6;(2)ф=2n-4.證明：因為G是極大平面圖，所以，每個面的次數(shù)為3.由次數(shù)公式：由歐拉公式：所以得：8第八頁，共三十四頁，2022年，8月28日所以得：又所以：注：頂點數(shù)相同的極大平面圖并不唯一。例如：正20面體非正20面體9第九頁，共三十四頁，2022年，8月28日還在研究中的問題是：頂點數(shù)相同的極大平面圖的個數(shù)和結(jié)構(gòu)問題。

2、極大外平面圖及其性質(zhì)與極大平面圖相對應(yīng)的圖是極小平面圖。定義2若一個可平面圖G存在一種平面嵌入，使得其所有頂點均在某個面的邊界上，稱該圖為外可平面圖。外可平面圖的一種外平面嵌入，稱為外平面圖。外可平面圖外平面圖1外平面圖210第十頁，共三十四頁，2022年，8月28日注：對外可平面圖G來說，一定存在一種外平面嵌入，使得G的頂點均在外部面的邊界上。這由球極投影法可以說明。下面研究極大外平面圖的性質(zhì)。定義3設(shè)G是一個簡單外可平面圖，若在G中任意不鄰接頂點間添上一條邊后，G成為非外可平面圖，則稱G是極大外可平面圖。極大外可平面圖的外平面嵌入，稱為極大外平面圖。極大外平面圖11第十一頁，共三十四頁，2022年，8月28日引理設(shè)G是一個連通簡單外可平面圖，則在G中有一個度數(shù)至多是2的頂點。證明我們對G的階數(shù)n作數(shù)學(xué)歸納。當(dāng)n≦3時，引理結(jié)論顯然成立；當(dāng)n=4時，由于K4不能是外可平面圖，所以，四階的外可平面圖至少有一個頂點度數(shù)不超過2。事實上，更強一點的結(jié)論是：當(dāng)n=4時，有兩個不鄰接頂點，其度數(shù)不超過2.設(shè)當(dāng)G是一個階數(shù)小于n的簡單連通外可平面圖時，存在兩個不鄰接頂點，其度數(shù)不超過2?？紤]G是一個階數(shù)等于n的簡單連通外可平面圖。情形1，如果G有割點x12第十二頁，共三十四頁，2022年，8月28日由歸納假設(shè)，G-x的兩個不同分支中分別有一個異于x的頂點z與z1,使得度數(shù)不超過2。這說明G中有兩個不鄰接頂點,使得度數(shù)都不超過2；x情形2若G是2連通的?？紤]G的任意一種外平面嵌入。則G的外部面邊界一定是圈。否則，容易推出G有割點。設(shè)C是G的外平面嵌入的外部面邊界。若除C外，圖中沒有其它的邊，則G=C,顯然G中有不鄰接點，度數(shù)不超過2；13第十三頁，共三十四頁，2022年，8月28日若除C外，圖中至少有邊xy。如下圖所示：xy則在C上的兩條xy路上的點在G中的兩個導(dǎo)出子圖H1與H2是外平面圖。有歸納假設(shè)，在H1,H2中分別存在異于x,y的點z與z1,使得，它們的度數(shù)不超過2.xyzz114第十四頁，共三十四頁，2022年，8月28日定理2設(shè)G是一個有n(n≥3)個點，且所有點均在外部面上的極大外平面圖，則G有n-2個內(nèi)部面。證明：對G的階數(shù)作數(shù)學(xué)歸納。當(dāng)n=3時，G是三角形，顯然只有一個內(nèi)部面；設(shè)當(dāng)n=k時，結(jié)論成立。當(dāng)n=k+1時，首先，注意到G必有一個2度頂點u在G的外部面上。(這可以由上面引理得到)考慮G1=G-v。由歸納假設(shè)，G1有k-2個內(nèi)部面。這樣G有k-1個內(nèi)部面。于是定理2得證。15第十五頁，共三十四頁，2022年，8月28日定理3設(shè)G是一個有n(n≥3)個點，且所有點均在外部面上的外平面圖，則G是極大外平面圖，當(dāng)且僅當(dāng)其外部面的邊界是圈，內(nèi)部面是三角形。注：這是極大外平面圖的典型特征。證明：先證明必要性。

(1)證明G的邊界是圈。設(shè)W=v1v2…vnv1是G的外部面邊界。若W不是圈，則存在i與j,使得：1≦i,j≦n,且j-i≠±1(modn),使vi=vj=v.此時，G可以示意如下：W

vi-1

v1vnv2vi+1vj-1vj+1v16第十六頁，共三十四頁，2022年，8月28日

vi-1與vi+1不能鄰接。否則W不能構(gòu)成G的外部面邊界。這樣，我們連接vi-1與vi+1：

vi-1

v1vnv2vi+1vj-1vj+1v得到一個新外平面圖。這與G的極大性矛盾。

(2)證明G的內(nèi)部面是三角形。首先，注意到，G的內(nèi)部面必須是圈。因為，G的外部面的邊界是生成圈，所以G是2連通的，所以，G的每個面的邊界必是圈。17第十七頁，共三十四頁，2022年，8月28日其次，設(shè)C是G中任意一個內(nèi)部面的邊界。如果C的長度大于等于4，則C中一定存在不鄰接頂點，連接這兩點得到一個新平面圖，這與G的極大性矛盾。又由于G是單圖，所以C的長度只能為3.下面證明充分性。設(shè)G是一個外平面圖，內(nèi)部面是三角形，外部面是圈W.如果G不是極大外平面圖，那么存在不鄰接頂點u與v,使得G+uv是外平面圖。但是，G+uv不能是外平面圖。因為，若邊uv經(jīng)過W的內(nèi)部，則它要與G的其它邊相交；若uv經(jīng)過W的外部，導(dǎo)致所有點不能在在G的同一個面上。所以，G是極大外平面圖。18第十八頁，共三十四頁，2022年，8月28日定理4每個至少有7個頂點的外可平面圖的補圖不是外可平面圖，且7是這個數(shù)目的最小者。我們用枚舉方法證明。證明：對于n=7的極大外可平面圖來說，只有4個。如下圖所示。直接驗證：它們的補圖均不是外可平面的。而當(dāng)n=6時，我們可以找到一個外可平面圖G(見下圖),使得其補圖是外可平面圖。19第十九頁，共三十四頁，2022年，8月28日(二)、平面圖的對偶圖

1、對偶圖的定義

定義4給定平面圖G，G的對偶圖G*如下構(gòu)造：

(1)在G的每個面fi內(nèi)取一個點vi*作為G*的一個頂點；

(2)對G的一條邊e,若e是面fi與fj的公共邊，則連接vi*與vj*，且連線穿過邊e;若e是面fi中的割邊，則以vi為頂點20第二十頁，共三十四頁，2022年，8月28日作環(huán)，且讓它與e相交。例如，作出平面圖G的對偶圖G*G21第二十一頁，共三十四頁，2022年，8月28日

2、對偶圖的性質(zhì)

(1)、G與G*的對應(yīng)關(guān)系

1)G*的頂點數(shù)等于G的面數(shù)；

2)G*的邊數(shù)等于G的邊數(shù)；

3)G*的面數(shù)等于G的頂點數(shù)；

4)d(v*)=deg(f)對偶圖面邊割邊環(huán)邊割集回路點邊環(huán)割邊回路邊割集對應(yīng)平面圖G22第二十二頁，共三十四頁，2022年，8月28日

(2)、定理5定理5平面圖G的對偶圖必然連通證明：在G*中任意取兩點vi*與vj*。我們證明該兩點連通即可！用一條曲線l把vi*和vj*連接起來，且l不與G*的任意頂點相交。顯然，曲線l從vi*到vj*經(jīng)過的面邊序列，對應(yīng)從vi*到vj*的點邊序列，該點邊序列就是該兩點在G*中的通路。注:(1)由定理5知：(G*)*不一定等于G;23第二十三頁，共三十四頁，2022年，8月28日

證明：“必要性”

(2)G是平面圖，則當(dāng)且僅當(dāng)G是連通的。(習(xí)題第26題)由于G是平面圖，由定理5，G*是連通的。而由G*是平面圖，再由定理5，(G*)*是連通的。所以，由得：G是連通的?！俺浞中浴庇蓪ε紙D的定義知，平面圖G與其對偶圖G*嵌入在同一平面上，當(dāng)G連通時，容易知道：G*的無界面f**中僅含G的唯一頂點v,而除v外，G中其它頂點u均與G*的有限面形成一一對應(yīng)，且對應(yīng)頂點間鄰接關(guān)系保持不變，即：24第二十四頁，共三十四頁，2022年，8月28日

(3)同構(gòu)的平面圖可以有不同構(gòu)的對偶圖。

例如，下面的兩個圖：G1G2

但這是因為：G2中有次數(shù)是1的面，而G1沒有次數(shù)是1的面。所以，它們的對偶圖不能同構(gòu)。25第二十五頁，共三十四頁，2022年，8月28日

例2證明：

(1)B是平面圖G的極小邊割集，當(dāng)且僅當(dāng)

是G*的圈。

(2)歐拉平面圖的對偶圖是偶圖。示意圖26第二十六頁，共三十四頁，2022年，8月28日證明:(1)

對B的邊數(shù)作數(shù)學(xué)歸納。示意圖

當(dāng)B的邊數(shù)n=1時，B中邊是割邊

顯然，在G*中對應(yīng)環(huán)。所以，結(jié)論成立。

設(shè)對B的邊數(shù)n<k時，結(jié)論成立。考慮n=k的情形。

設(shè)c1

∈B,于是B-c1是G-c1=G1的一個極小邊割集。由歸納假設(shè)：是G1*的一個圈。且圈C1*上的頂點對應(yīng)于G1中的面f,f的邊界上有極小邊割集B-e1的邊。27第二十七頁，共三十四頁，2022年，8月28日現(xiàn)在，把e1加入到G1中，恢復(fù)G。示意圖G1由于G是平面圖，其作用相當(dāng)于圈C1*上的一個頂點對應(yīng)于G1中的一個平面區(qū)域f,被e1劃分成兩個頂點f1*與f2*,并在其間連以e1所對應(yīng)的邊e1*。所以，B對應(yīng)在G*中的C*仍然是一個圈。由歸納法，結(jié)論得到證明。示意圖28第二十八頁，共三十四頁，2022年，8月28日充分性：

G*中的一個圈，對應(yīng)于G中的邊的集合B顯然是G中的一個邊割集。示意圖若該割集不是極小邊割集，則它是G中極小邊割集之和。而由必要性知道：每個極小邊割集對應(yīng)G*的一個圈，于是推出B在G*中對應(yīng)的邊集合是圈之并。但這與假設(shè)矛盾。

(2)因歐拉圖的任意邊割集均有偶數(shù)條邊。于是由(1),G*中不含奇圈。所以G*是偶圖。29第二十九頁，共三十四頁，2022年，