《ppt特殊平面圖與平面圖的對(duì)偶.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《ppt特殊平面圖與平面圖的對(duì)偶.ppt（33頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1 Email yc517922 圖論及其應(yīng)用 任課教師 楊春 數(shù)學(xué)科學(xué)學(xué)院 2 本次課主要內(nèi)容 一 一些特殊平面圖 二 平面圖的對(duì)偶圖 特殊平面圖與平面圖的對(duì)偶圖 1 極大平面圖及其性質(zhì) 2 極大外平面圖及其性質(zhì) 3 1 極大平面圖及其性質(zhì) 一 一些特殊平面圖 對(duì)于一個(gè)簡(jiǎn)單平面圖來(lái)說(shuō) 在不鄰接頂點(diǎn)對(duì)間加邊 當(dāng)邊數(shù)增加到一定數(shù)量時(shí) 就會(huì)變成非平面圖 這樣 就啟發(fā)我們研究平面圖的極圖問(wèn)題 定義1設(shè)G是簡(jiǎn)單可平面圖 如果G是Ki 1 i 4 或者在G的任意非鄰接頂點(diǎn)間添加一條邊后 得到的圖均是非可平面圖 則稱(chēng)G是極大可平面圖 極大可平面圖的平面嵌入稱(chēng)為極大平面圖 4 注 只有在單圖前提下才能定義極大平面圖 引理設(shè)G是極大平面圖 則G必然連通 若G的階數(shù)大于等于3 則G無(wú)割邊 1 先證明G連通 若不然 G至少兩個(gè)連通分支 設(shè)G1與G2是G的任意兩個(gè)連通分支 5 把G1畫(huà)在G2的外部面上 并在G1 G2上分別取一點(diǎn)u與v 連接u與v得到一個(gè)新平面圖G 但這與G是極大平面圖相矛盾 2 當(dāng)G的階數(shù)n 3時(shí) 我們證明G中沒(méi)有割邊 若不然 設(shè)G中有割邊e uv 則G uv不連通 恰有兩個(gè)連通分支G1與G2 6 設(shè)u在G1中 而v在G2中 由于n 3 所以 至少有一個(gè)分支包含兩個(gè)以上的頂點(diǎn) 設(shè)G2至少含有兩個(gè)頂點(diǎn) 又設(shè)G1中含有點(diǎn)u的面是f 將G2畫(huà)在f內(nèi) 由于G是單圖 所以 在G2的外部面上存在不等于點(diǎn)v的點(diǎn)t 現(xiàn)在 在G中連接點(diǎn)u與t得新平面圖G 它比G多一條邊 這與G的極大性相矛盾 7 下面證明極大平面圖的一個(gè)重要性質(zhì) 定理1設(shè)G是至少有3個(gè)頂點(diǎn)的平面圖 則G是極大平面圖 當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)是3且為單圖 注 該定理可以簡(jiǎn)單記為是 極大平面圖的三角形特征 即每個(gè)面的邊界是三角形 證明 必要性 由引理知 G是單圖 G無(wú)割邊 于是G的每個(gè)面的次數(shù)至少是3 假設(shè)G中某個(gè)面f的次數(shù)大于等于4 記f的邊界是v1v2v3v4 vk 如下圖所示 8 如果v1與v3不鄰接 則連接v1v3 沒(méi)有破壞G的平面性 這與G是極大平面圖矛盾 所以v1v3必須鄰接 但必須在f外連線(xiàn) 同理v2與v4也必須在f外連線(xiàn) 但邊v1v3與邊v2v4在f外交叉 與G是平面圖矛盾 所以 G的每個(gè)面次數(shù)一定是3 定理的充分性是顯然的 9 推論 設(shè)G是n個(gè)點(diǎn) m條邊和 個(gè)面的極大平面圖 且n 3 則 1 m 3n 6 2 2n 4 證明 因?yàn)镚是極大平面圖 所以 每個(gè)面的次數(shù)為3 由次數(shù)公式 由歐拉公式 所以得 10 所以得 又 所以 注 頂點(diǎn)數(shù)相同的極大平面圖并不唯一 例如 11 還在研究中的問(wèn)題是 頂點(diǎn)數(shù)相同的極大平面圖的個(gè)數(shù)和結(jié)構(gòu)問(wèn)題 2 極大外平面圖及其性質(zhì) 定義2若一個(gè)可平面圖G存在一種平面嵌入 使得其所有頂點(diǎn)均在某個(gè)面的邊界上 稱(chēng)該圖為外可平面圖 外可平面圖的一種外平面嵌入 稱(chēng)為外平面圖 12 注 對(duì)外可平面圖G來(lái)說(shuō) 一定存在一種外平面嵌入 使得G的頂點(diǎn)均在外部面的邊界上 這由球極投影法可以說(shuō)明 下面研究極大外平面圖的性質(zhì) 定義3設(shè)G是一個(gè)簡(jiǎn)單外可平面圖 若在G中任意不鄰接頂點(diǎn)間添上一條邊后 G成為非外可平面圖 則稱(chēng)G是極大外可平面圖 極大外可平面圖的外平面嵌入 稱(chēng)為極大外平面圖 13 定理2設(shè)G是一個(gè)有n n 3 個(gè)點(diǎn) 且所有點(diǎn)均在外部面上的極大外平面圖 則G有n 2個(gè)內(nèi)部面 證明 對(duì)G的階數(shù)作數(shù)學(xué)歸納 當(dāng)n 3時(shí) G是三角形 顯然只有一個(gè)內(nèi)部面 設(shè)當(dāng)n k時(shí) 結(jié)論成立 當(dāng)n k 1時(shí) 首先 注意到G必有一個(gè)2度頂點(diǎn)u在G的外部面上 這可以由上面引理得到 考慮G1 G v 由歸納假設(shè) G1有k 2個(gè)內(nèi)部面 這樣G有k 1個(gè)內(nèi)部面 于是定理2得證 引理設(shè)G是一個(gè)連通簡(jiǎn)單外可平面圖 則在G中有一個(gè)度數(shù)至多是2的頂點(diǎn) 14 定理3設(shè)G是一個(gè)有n n 3 個(gè)點(diǎn) 且所有點(diǎn)均在外部面上的外平面圖 則G是極大外平面圖 當(dāng)且僅當(dāng)其外部面的邊界是圈 內(nèi)部面是三角形 注 這是極大外平面圖的典型特征 證明 先證明必要性 1 證明G的邊界是圈 容易知道 G的外部面邊界一定為閉跡 否則 G不能為極大外平面圖 設(shè)W v1v2 vnv1是G的外部面邊界 若W不是圈 則存在i與j 使vi vj v 此時(shí) G可以示意如下 15 vi 1與vi 1不能鄰接 否則W不能構(gòu)成G的外部面邊界 這樣 我們連接vi 1與vi 1 得到一個(gè)新外平面圖 這與G的極大性矛盾 2 證明G的內(nèi)部面是三角形 首先 注意到 G的內(nèi)部面必須是圈 因?yàn)?G的外部面的邊界是生成圈 所以G是2連通的 所以 G的每個(gè)面的邊界必是圈 16 其次 設(shè)C是G中任意一個(gè)內(nèi)部面的邊界 如果C的長(zhǎng)度大于等于4 則C中一定存在不鄰接頂點(diǎn) 連接這兩點(diǎn)得到一個(gè)新平面圖 這與G的極大性矛盾 又由于G是單圖 所以C的長(zhǎng)度只能為3 下面證明充分性 設(shè)G是一個(gè)外平面圖 內(nèi)部面是三角形 外部面是圈W 如果G不是極大外平面圖 那么存在不鄰接頂點(diǎn)u與v 使得G uv是外平面圖 但是 G uv不能是外平面圖 因?yàn)?若邊uv經(jīng)過(guò)W的內(nèi)部 則它要與G的其它邊相交 若uv經(jīng)過(guò)W的外部 導(dǎo)致所有點(diǎn)不能在G的同一個(gè)面上 所以 G是極大外平面圖 17 定理4每個(gè)至少有7個(gè)頂點(diǎn)的外可平面圖的補(bǔ)圖不是外可平面圖 且7是這個(gè)數(shù)目的最小者 我們用枚舉方法證明 證明 對(duì)于n 7的極大外可平面圖來(lái)說(shuō) 只有4個(gè) 如下圖所示 直接驗(yàn)證 它們的補(bǔ)圖均不是外可平面的 而當(dāng)n 6時(shí) 我們可以找到一個(gè)外可平面圖G 見(jiàn)下圖 使得其補(bǔ)圖是外可平面圖 18 二 平面圖的對(duì)偶圖 1 對(duì)偶圖的定義 定義4給定平面圖G G的對(duì)偶圖G 如下構(gòu)造 1 在G的每個(gè)面fi內(nèi)取一個(gè)點(diǎn)vi 作為G 的一個(gè)頂點(diǎn) 2 對(duì)G的一條邊e 若e是面fi與fj的公共邊 則連接vi 與vj 且連線(xiàn)穿過(guò)邊e 若e是面fi中的割邊 則以vi為頂點(diǎn) 19 作環(huán) 且讓它與e相交 例如 作出平面圖G的對(duì)偶圖G 20 2 對(duì)偶圖的性質(zhì) 1 G與G 的對(duì)應(yīng)關(guān)系 1 G 的頂點(diǎn)數(shù)等于G的面數(shù) 2 G 的邊數(shù)等于G的邊數(shù) 3 G 的面數(shù)等于G的頂點(diǎn)數(shù) 4 d v deg f 21 2 定理5 定理5平面圖G的對(duì)偶圖必然連通 證明 在G 中任意取兩點(diǎn)vi 與vj 我們證明該兩點(diǎn)連通即可 用一條曲線(xiàn)l把vi 和vj 連接起來(lái) 且l不與G 的任意頂點(diǎn)相交 顯然 曲線(xiàn)l從vi 到vj 經(jīng)過(guò)的面邊序列 對(duì)應(yīng)從vi 到vj 的點(diǎn)邊序列 該點(diǎn)邊序列就是該兩點(diǎn)在G 中的通路 注 1 由定理5知 G 不一定等于G 22 證明 必要性 2 G是平面圖 則當(dāng)且僅當(dāng)G是連通的 習(xí)題第26題 由于G是平面圖 由定理5 G 是連通的 而由G 是平面圖 再由定理5 G 是連通的 所以 由得 G是連通的 充分性 由對(duì)偶圖的定義知 平面圖G與其對(duì)偶圖G 嵌入在同一平面上 當(dāng)G連通時(shí) 容易知道 G 的無(wú)界面f 中僅含G的唯一頂點(diǎn)v 而除v外 G中其它頂點(diǎn)u均與G 的有限面形成一一對(duì)應(yīng) 于是 G中頂點(diǎn)和G 頂點(diǎn)在這種自然對(duì)應(yīng)方式下一一對(duì)應(yīng) 且對(duì)應(yīng)頂點(diǎn)間鄰接關(guān)系保持不變 故 23 3 同構(gòu)的平面圖可以有不同構(gòu)的對(duì)偶圖 例如 下面的兩個(gè)圖 但 這是因?yàn)?G2中有次數(shù)是1的面 而G1沒(méi)有次數(shù)是1的面 所以 它們的對(duì)偶圖不能同構(gòu) 24 第一次上交作業(yè) 第3章習(xí)題3 1 7 9 16 第4章習(xí)題4 3 7 10 12 第5章習(xí)題5 1 2 6 7 13 19 25 作業(yè) P143 146習(xí)題5 3 4 5 6 8 25 26 27 其中25 26 27結(jié)合課件學(xué)習(xí) 26 ThankYou 27 例2證明 1 B是平面圖G的極小邊割集 當(dāng)且僅當(dāng) 是G 的圈 2 歐拉平面圖的對(duì)偶圖是偶圖 28 證明 1 對(duì)B的邊數(shù)作數(shù)學(xué)歸納 當(dāng)B的邊數(shù)n 1時(shí) B中邊是割邊 顯然 在G 中對(duì)應(yīng)環(huán) 所以 結(jié)論成立 設(shè)對(duì)B的邊數(shù)n k時(shí) 結(jié)論成立 考慮n k的情形 設(shè)c1 B 于是B c1是G c1 G1的一個(gè)極小邊割集 由歸納假設(shè) 是G1 的一個(gè)圈 且圈C1 上的頂點(diǎn)對(duì)應(yīng)于G1中的面f f的邊界上有極小邊割集B e1的邊 29 現(xiàn)在 把e1加入到G1中 恢復(fù)G 由于G是平面圖 其作用相當(dāng)于圈C1 上的一個(gè)頂點(diǎn)對(duì)應(yīng)于G1中的一個(gè)平面區(qū)域f 被e1劃分成兩個(gè)頂點(diǎn)f1 與f2 并在其間連以e1所對(duì)應(yīng)的邊e1 所以 B對(duì)應(yīng)在G 中的C 仍然是一個(gè)圈 由歸納法 結(jié)論得到證明 30 充分性 G 中的一個(gè)圈 對(duì)應(yīng)于G中 的邊的集合B顯然是G中的一個(gè)邊割集 若該割集不是極小邊割集 則它是G中極小邊割集之和 而由必要性知道 每個(gè)極小邊割集對(duì)應(yīng)G 的一個(gè)圈 于是推出B在G 中對(duì)應(yīng)的邊集合是圈之并 但這與假設(shè)矛盾 2 因歐拉圖的任意邊割集均有偶數(shù)條邊 于是由 1 G 中不含奇圈 所以G 是偶圖 31 例3設(shè)T是連通平面圖G的生成樹(shù) 證明 T G E 是G 中的生成樹(shù) 習(xí)題第27題 32 證明 情形1 如果G是樹(shù) 在這種情況下 E 則T 是平凡圖 而G 的生成樹(shù)也是平凡圖 所以 結(jié)論成立 情形2 如果G不是樹(shù) 因G的每個(gè)面必然含有邊e不屬于E T 即G 的每個(gè)頂點(diǎn)必然和E 中的某邊關(guān)聯(lián) 于是T 必然是G 的生成子圖 下面證明 T 中沒(méi)有圈 若T 中有圈 則由例2知 T的余樹(shù)中含有G的極小邊割集 但我們又可以證明 如果T是連通圖G的生成樹(shù) 那么 T的余樹(shù)不含G的極小邊割集 這樣 T 不能含G 的圈 33 又因在G中 每去掉T的余樹(shù)中的一條邊 G的面減少一個(gè) 當(dāng)T的余樹(shù)中的邊全去掉時(shí) G變成一顆樹(shù)T 于是 有 所以 T 是G 的生成樹(shù)