《ppt特殊平面圖與平面圖的對偶.ppt》由會員分享，可在線閱讀，更多相關(guān)《ppt特殊平面圖與平面圖的對偶.ppt（33頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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