特殊平面圖與平面圖的對(duì)偶-資料下載頁(yè)
2025-05-10 00:09本頁(yè)面
【正文】 (1) B是平面圖 G的極小邊割集，當(dāng)且僅當(dāng) 是 G*的圈。 (2) 歐拉平面圖的對(duì)偶圖是偶圖。 示意圖 1 0 x t 0 1 2 ?1 ? 0 1 n 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ù) nk 時(shí)，結(jié)論成立?？紤] n=k的情形。 設(shè) c1 ∈ B, 于是 Bc1是 Gc1=G1的一個(gè)極小邊割集。由歸納假設(shè)： ? ?1 1 1* ( * ) *c E G c B c C? ? ? ? 是 G1*的一個(gè)圈。且圈 C1*上的頂點(diǎn)對(duì)應(yīng)于 G1中的面 f, f 的邊界上有極小邊割集 Be1的邊。 1 0 x t 0 1 2 ?1 ? 0 1 n 29 現(xiàn)在，把 e1加入到 G1中，恢復(fù) G。 示意圖 G1 由于 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é)論得到證明。 示意圖 1 0 x t 0 1 2 ?1 ? 0 1 n 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*是偶圖。 1 0 x t 0 1 2 ?1 ? 0 1 n 31 例 3 設(shè) T是連通平面圖 G的生成樹(shù)， ? ?* * ( * ) ( )E e E G e E T? ? ? 證明： T*=G*[E*]是 G*中的生成樹(shù)。 (習(xí)題第 27題 ) 示意圖 1 0 x t 0 1 2 ?1 ? 0 1 n 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*的圈。 1 0 x t 0 1 2 ?1 ? 0 1 n 33 又因在 G中，每去掉 T的余樹(shù)中的一條邊， G的面減少一個(gè)，當(dāng) T的余樹(shù)中的邊全去掉時(shí)， G變成一顆樹(shù) T. 于是，有： ( * ) ( ) ( ) 1 ( * ) 1E T E T G V G?? ? ? ? ? 所以， T*是 G*的生成樹(shù)。
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1