特殊平面圖與平面圖的對(duì)偶(編輯修改稿)
2025-06-15 00:09 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 界是圈，內(nèi)部面是三角形。 注：這是極大外平面圖的典型特征。 證明：先證明必要性。 (1) 證明 G的邊界是圈。 容易知道： G的外部面邊界一定為閉跡，否則， G不能為極大外平面圖。設(shè) W=v1v2…v nv1是 G的外部面邊界。若W不是圈，則存在 i與 j, 使 vi=vj=， G可以示意如下： W vi1 v1 vn v2 vi+1 vj1 vj+1 v 1 0 x t 0 1 2 ?1 ? 0 1 n 15 vi1與 vi+1不能鄰接。否則 W不能構(gòu)成 G的外部面邊界。這樣，我們連接 vi1與 vi+1： vi1 v1 vn v2 vi+1 vj1 vj+1 v 得到一個(gè)新外平面圖。這與 G的極大性矛盾。 (2) 證明 G的內(nèi)部面是三角形。 首先，注意到， G的內(nèi)部面必須是圈。因?yàn)椋?G的外部面的邊界是生成圈，所以 G是 2連通的，所以， G的每個(gè)面的邊界必是圈。 1 0 x t 0 1 2 ?1 ? 0 1 n 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是極大外平面圖。 1 0 x t 0 1 2 ?1 ? 0 1 n 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ǔ)圖是外可平面圖。 1 0 x t 0 1 2 ?1 ? 0 1 n 18 G G(二 )、平面圖的對(duì)偶圖 對(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*，且連線穿過(guò)邊 e。若 e是面 fi 中的割邊，則以 vi為頂點(diǎn) 1 0 x t 0 1 2 ?1 ? 0 1 n 19 作環(huán)，且讓它與 e相交。 例如，作出平面圖 G的對(duì)偶圖 G* G 1 0 x t 0 1 2 ?1 ? 0 1 n 20 對(duì)偶圖的性質(zhì) (1)、 G與 G*的對(duì)應(yīng)關(guān)系 1) G*的頂點(diǎn)數(shù)等于
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1