特殊平面圖與平面圖的對偶-展示頁
2025-05-22 00:09本頁面
【正文】 成非平面圖。這樣，就啟發(fā)我們研究平面圖的極圖問題。 極大可平面圖的平面嵌入稱為極大平面圖。 引理 設(shè) G是極大平面圖，則 G必然連通；若 G的階數(shù)大于等于 3，則 G無割邊。 若不然， G至少兩個(gè)連通分支。 1 0 x t 0 1 2 ?1 ? 0 1 n 5 把 G1畫在 G2的外部面上，并在 G1,G2上分別取一點(diǎn) u與 v.連接 u與 v得到一個(gè)新平面圖 G*。 (2) 當(dāng) G的階數(shù) n≥3 時(shí)，我們證明 G中沒有割邊。 u v e G1 G2 G f 1 0 x t 0 1 2 ?1 ? 0 1 n 6 設(shè) u在 G1中，而 v在 G2中。設(shè) G2至少含有兩個(gè)頂點(diǎn)。 由于 G是單圖，所以，在 G2的外部面上存在不等于點(diǎn)v的點(diǎn) t。這與 G的極大性相矛盾。 定理 1 設(shè) G是至少有 3個(gè)頂點(diǎn)的平面圖，則 G是極大平面圖，當(dāng)且僅當(dāng) G的每個(gè)面的次數(shù)是 3且為單圖。 證明：“必要性” 由引理知， G是單圖、 G無割邊。 假設(shè) G中某個(gè)面 f 的次數(shù)大于等于 4。如下圖所示 : 1 0 x t 0 1 2 ?1 ? 0 1 n 8 如果 v1與 v3不鄰接，則連接 v1v3，沒有破壞 G的平面性，這與 G是極大平面圖矛盾。但邊 v1v3與邊v2v4在 f 外交叉，與 G是平面圖矛盾！ 所以， G的每個(gè)面次數(shù)一定是 3. 定理的充分性是顯然的。 (2) ф=2n4. 證明：因?yàn)?G是極大平面圖，所以，每個(gè)面的次數(shù)為 3.由次數(shù)公式： 2 d e g ( ) 3fmf ?????? 由歐拉公式： 2 nm? ? ? ? 所以得： 2 23 m n m? ? ? 1 0 x t 0 1 2 ?1 ? 0 1 n 10 所以得： 36mn?? 又 2mn ?? ? ? 所以： 24n? ?? 注：頂點(diǎn)數(shù)相同的極大平面圖并不唯一。 極大外平面圖及其性質(zhì) 定義 2 若一個(gè)可平面圖 G存在一種平面嵌入，使得其所有頂點(diǎn)均在某個(gè)面的邊界上，稱該圖為外可平面圖。 外可平面圖 外平面圖 1 f 外平面圖 2 f 1 0 x t 0 1 2 ?1 ? 0 1 n 12 注：對外可平面圖 G來說，一定存在一種外平面嵌入，使得 G的頂點(diǎn)均在外部面的邊界上。 下面研究極大外平面圖的性質(zhì)。極大外可平面圖的外平面嵌入，稱為極大外平面圖。 證明：對 G的階數(shù)作數(shù)學(xué)歸納。 當(dāng) n=k+1時(shí)，首先，注意到 G必有一個(gè) 2度頂點(diǎn) u在 G的外部面上。由歸納假設(shè)， G1有 k2個(gè)內(nèi)部面。于是定理 2得證。 1 0 x t 0 1 2 ?1 ? 0 1 n 14 定理 3 設(shè) G是一個(gè)有 n (n≥3)個(gè)點(diǎn)，且所有點(diǎn)均在外部面上的外平面圖，則 G是極大外平面圖，當(dāng)且僅當(dāng)其外部面的邊界是圈，內(nèi)部面是三角形。 證明：先證明必要性。 容易知道： G的外部面邊界一定為閉跡，否則， G不能為極大外平面圖。若W不是圈，則存在 i與 j, 使 vi=vj=， G可以示意如下：
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1