圖論ppt20電子科技大學(xué)楊春

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1Email: 圖論及其應(yīng)用圖論及其應(yīng)用任課教師：楊春任課教師：楊春數(shù)學(xué)科學(xué)學(xué)院數(shù)學(xué)科學(xué)學(xué)院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2第六章第六章 平面圖平面圖主要內(nèi)容主要內(nèi)容一、平面圖概念與性質(zhì)一、平面圖概念與性質(zhì)二、特殊平面圖與平面圖的對偶圖二、特殊平面圖與平面圖的對偶圖三、平面圖的判定與涉及平面性不變量三、平面圖的判定與涉及平面性不變量教學(xué)時數(shù)教學(xué)時數(shù)安排安排8學(xué)時講授本章內(nèi)容學(xué)時講授本章內(nèi)容四、平面性算法四、

2、平面性算法 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3本次課主要內(nèi)容本次課主要內(nèi)容(一一)、平面圖的概念、平面圖的概念(二二)、平面圖性質(zhì)、平面圖性質(zhì)平面圖概念與性質(zhì)平面圖概念與性質(zhì)(三三)、圖的嵌入性問題簡介、圖的嵌入性問題簡介(四四)、凸多面體與平面圖、凸多面體與平面圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 圖的平面性問題是圖論典型問題之一。生活中許多問題圖的平面性問題是圖論典型問題之一。生活中許多問題都與該問題有關(guān)。都與該問題有關(guān)。(一一)、平面圖

3、的概念、平面圖的概念 例子例子1：電路板設(shè)計(jì)問題：電路板設(shè)計(jì)問題 在電路板設(shè)計(jì)時，需要考慮的問題之一是連接電路元件在電路板設(shè)計(jì)時，需要考慮的問題之一是連接電路元件間的導(dǎo)線間不能交叉。否則，當(dāng)絕緣層破損時，會出現(xiàn)短間的導(dǎo)線間不能交叉。否則，當(dāng)絕緣層破損時，會出現(xiàn)短路故障。路故障。 顯然，電路板可以模型為一個圖，顯然，電路板可以模型為一個圖，“要求電路元件間連要求電路元件間連接導(dǎo)線互不交叉接導(dǎo)線互不交叉”，對應(yīng)于，對應(yīng)于“要求圖中的邊不能相互交叉要求圖中的邊不能相互交叉”。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 例子例子2：

4、空調(diào)管道的設(shè)計(jì)：空調(diào)管道的設(shè)計(jì) 某娛樂中心有某娛樂中心有6個景點(diǎn)，位置分布如下圖。個景點(diǎn)，位置分布如下圖。A1A4A5A3A2A6 分析者認(rèn)為：分析者認(rèn)為：(1) A1與與A4, (2) A2與與A5, (3) A3與與A6間人流較間人流較少，其它景點(diǎn)之間人流量大，必須投資鋪設(shè)空調(diào)管道，但少，其它景點(diǎn)之間人流量大，必須投資鋪設(shè)空調(diào)管道，但要求空調(diào)管道間不能交叉。如何設(shè)計(jì)？要求空調(diào)管道間不能交叉。如何設(shè)計(jì)？ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 如果把每個景點(diǎn)分別模型為一個點(diǎn)，景點(diǎn)間連線，當(dāng)且如果把每個景點(diǎn)分別模型為一個點(diǎn)

5、，景點(diǎn)間連線，當(dāng)且僅當(dāng)兩景點(diǎn)間要鋪設(shè)空調(diào)管道。那么，上面問題直接對應(yīng)僅當(dāng)兩景點(diǎn)間要鋪設(shè)空調(diào)管道。那么，上面問題直接對應(yīng)的圖為：的圖為：A6A5A4A3A2A1 于是，問題轉(zhuǎn)化為：能否把上圖畫在平面上，使得邊不于是，問題轉(zhuǎn)化為：能否把上圖畫在平面上，使得邊不會相互交叉？會相互交叉？ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 通過嘗試，可以把上圖畫為：通過嘗試，可以把上圖畫為： 于是，鋪設(shè)方案為：于是，鋪設(shè)方案為：A6A5A4A3A2A1A1A4A5A3A2A6 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1

6、.5 2 1 0.5 0 0.5 1 n 8 問題：要求把問題：要求把3種公用設(shè)施種公用設(shè)施(煤氣，水和電煤氣，水和電)分別用煤氣管分別用煤氣管道、水管和電線連接到道、水管和電線連接到3間房子里，要求任何一根線或管道間房子里，要求任何一根線或管道不與另外的線或管道相交，能否辦到？不與另外的線或管道相交，能否辦到？ 例子例子3：3間房子和間房子和3種設(shè)施問題種設(shè)施問題 上面問題可以模型為如下偶圖：上面問題可以模型為如下偶圖：H3H2H1EWG 問題轉(zhuǎn)化為，能否把上面偶圖畫在平面上，使得邊與邊問題轉(zhuǎn)化為，能否把上面偶圖畫在平面上，使得邊與邊之間不會交叉？之間不會交叉？ 0.8 1 0.6 0.4

7、0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 上面的例子都涉及同一個圖論問題：能否把一個圖畫在上面的例子都涉及同一個圖論問題：能否把一個圖畫在平面上，使得邊與邊之間沒有交叉？平面上，使得邊與邊之間沒有交叉？ 針對這一問題，我們引入如下概念針對這一問題，我們引入如下概念 定義定義1 如果能把圖如果能把圖G畫在平面上，使得除頂點(diǎn)外，邊與邊畫在平面上，使得除頂點(diǎn)外，邊與邊之間沒有交叉，稱之間沒有交叉，稱G可以嵌入平面，或稱可以嵌入平面，或稱G是可平面圖。可是可平面圖。可平面圖平面圖G的邊不交叉的一種畫法，稱為的邊不交叉的一種畫法，稱為G的一種平面嵌入，的一種平面

8、嵌入，G的平面嵌入表示的圖稱為平面圖。的平面嵌入表示的圖稱為平面圖。H3H2H1EWG圖圖GH3H2H1EWG圖圖G的平面嵌入的平面嵌入 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 注注: (1) 可平面圖概念和平面圖概念有時可以等同看待；可平面圖概念和平面圖概念有時可以等同看待； (2) 圖的平面性問題主要涉及如下幾個方面：圖的平面性問題主要涉及如下幾個方面：1) 平面圖的平面圖的性質(zhì)；性質(zhì)；2) 平面圖的判定；平面圖的判定；3) 平面嵌入方法平面嵌入方法(平面性算法平面性算法) ;4）涉及圖的平面性問題的拓?fù)洳蛔兞?。涉?/p>

9、圖的平面性問題的拓?fù)洳蛔兞俊?由由 圖的平面性問題研究引申出圖的一般嵌入性問題的研圖的平面性問題研究引申出圖的一般嵌入性問題的研究，形成了拓?fù)鋱D論的主要內(nèi)容。我國數(shù)學(xué)家吳文俊、劉究，形成了拓?fù)鋱D論的主要內(nèi)容。我國數(shù)學(xué)家吳文俊、劉彥佩等在該方向都有重要結(jié)果。劉彥佩的專著是彥佩等在該方向都有重要結(jié)果。劉彥佩的專著是圖的上圖的上可嵌入性理論可嵌入性理論(1994)，化學(xué)工業(yè)出版社出版。，化學(xué)工業(yè)出版社出版。 歷史上，波蘭數(shù)學(xué)家?guī)炖兴够?、美國?shù)學(xué)家惠特尼、歷史上，波蘭數(shù)學(xué)家?guī)炖兴够?、美國?shù)學(xué)家惠特尼、生于英國的加拿大數(shù)學(xué)家托特，我國數(shù)學(xué)家吳文俊等都在生于英國的加拿大數(shù)學(xué)家托特，我國數(shù)學(xué)家吳文俊等都

10、在拓?fù)鋱D論中有過精湛的研究。拓?fù)鋱D論中有過精湛的研究。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11(二二)、平面圖性質(zhì)、平面圖性質(zhì) 定義定義2 (1) 一個平面圖一個平面圖G把平面分成若干連通片，這些連把平面分成若干連通片，這些連通片稱為通片稱為G的區(qū)域，或的區(qū)域，或G的一個面。的一個面。G的面組成的集合用的面組成的集合用表示。表示。 在上圖在上圖G中，共有中，共有4個面。其中個面。其中f4是外部面，其余是內(nèi)部是外部面，其余是內(nèi)部面。面。= =f1, f2, f3, f4。平面圖平面圖Gf1f3f2f4 (2) 面積有限的區(qū)

11、域稱為平面圖面積有限的區(qū)域稱為平面圖G的內(nèi)部面，否則稱為的內(nèi)部面，否則稱為G的外部面。的外部面。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 (3) 在在G中，頂點(diǎn)和邊都與某個給定區(qū)域關(guān)聯(lián)的子圖，稱中，頂點(diǎn)和邊都與某個給定區(qū)域關(guān)聯(lián)的子圖，稱為該面的邊界。某面為該面的邊界。某面 f 的邊界中含有的邊數(shù)的邊界中含有的邊數(shù)(割邊計(jì)算割邊計(jì)算2次次)稱為該面稱為該面 f 的次數(shù)的次數(shù), 記為記為deg ( f )。平面圖平面圖Gf1f3f2f4 在上圖中，紅色邊在在上圖中，紅色邊在G中的導(dǎo)出子圖為面中的導(dǎo)出子圖為面 f3 的邊界。的

12、邊界。1deg()1f2deg()3f3deg()6f4deg()6f 1、平面圖的次數(shù)公式、平面圖的次數(shù)公式 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 定理定理1 設(shè)設(shè)G=(n, m)是平面圖，則：是平面圖，則：deg()2ffm 證明：對證明：對G的任意一條邊的任意一條邊e, 如果如果e是某面割邊，那么由面是某面割邊，那么由面的次數(shù)定義，該邊給的次數(shù)定義，該邊給G的總次數(shù)貢獻(xiàn)的總次數(shù)貢獻(xiàn)2次；如果次；如果e不是割邊，不是割邊，那么，它必然是兩個面的公共邊，因此，由面的次數(shù)定義，那么，它必然是兩個面的公共邊，因此，由面的

13、次數(shù)定義，它也給總次數(shù)貢獻(xiàn)它也給總次數(shù)貢獻(xiàn)2次。于是有：次。于是有：deg()2ffm 2、平面圖的歐拉公式、平面圖的歐拉公式 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 定理定理2(歐拉公式歐拉公式) 設(shè)設(shè)G=(n, m)是連通平面圖，是連通平面圖，是是G G的面的面數(shù)，則：數(shù)，則：2nm 證明：情形證明：情形1，如果，如果G是樹，那么是樹，那么m=n-1, =1。在這種情。在這種情況下，容易驗(yàn)證，定理中的恒等式是成立的。況下，容易驗(yàn)證，定理中的恒等式是成立的。 情形情形2，G不是樹的連通平面圖。不是樹的連通平面圖。 假設(shè)

14、在這種情形下，歐拉恒等式不成立。則存在一個含假設(shè)在這種情形下，歐拉恒等式不成立。則存在一個含有最少邊數(shù)的連通平面圖有最少邊數(shù)的連通平面圖G, 使得它不滿足歐拉恒等式。設(shè)使得它不滿足歐拉恒等式。設(shè)這個最少邊數(shù)連通平面圖這個最少邊數(shù)連通平面圖G=(n, m), 面數(shù)為面數(shù)為，則：，則：2nm 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 因?yàn)橐驗(yàn)镚不是樹，所以存在非割邊不是樹，所以存在非割邊e。顯然，。顯然，G-e是連通平面是連通平面圖，邊數(shù)為圖，邊數(shù)為m-1, 頂點(diǎn)數(shù)為頂點(diǎn)數(shù)為n, 面數(shù)為面數(shù)為-1。 由最少性假設(shè)，由最少性假設(shè)

15、，G-e滿足歐拉等式：滿足歐拉等式： 化簡得：化簡得：(1)(1)2nm2nm 這是一個矛盾。這是一個矛盾。 注：該定理可以采用對面數(shù)注：該定理可以采用對面數(shù)作數(shù)學(xué)歸納證明。作數(shù)學(xué)歸納證明。 3、歐拉公式的幾個有趣推論、歐拉公式的幾個有趣推論 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 推論推論1 設(shè)設(shè)G是具有是具有個面?zhèn)€面k k個連通分支的平面圖，則：個連通分支的平面圖，則：1nmk 證明：對第證明：對第i (1ik)ik)個分支來說，設(shè)頂點(diǎn)數(shù)為個分支來說，設(shè)頂點(diǎn)數(shù)為n ni i，邊數(shù)，邊數(shù)為為m mi i，面數(shù)為，面數(shù)為

16、i i, ,由歐拉公式：由歐拉公式：2iiinm 所以，所以，12kiiiinmk 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 而：而：1112kkkiiiiiinmk1kiinn1kiimm11kiik 所以得：所以得：1nmk 推論推論2 設(shè)設(shè)G是具有是具有n n個點(diǎn)個點(diǎn)m m條邊條邊個面的連通平面圖，如個面的連通平面圖，如果對果對G G的每個面的每個面f f , ,有：有：deg (deg (f f) ) l 3,3,則：則：(2)2lmnl 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

17、1 0.5 0 0.5 1 n 18 證明：一方面，由次數(shù)公式得：證明：一方面，由次數(shù)公式得：22deg()fmmfll 另一方面，由歐拉公式得：另一方面，由歐拉公式得：2nm 所以有：所以有：22mnml 整理得：整理得：(2)2lmnl 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 注注: (1)上面推論上面推論2也可以敘述為：也可以敘述為： 設(shè)設(shè)G=(n, m)是連通圖，如果：是連通圖，如果：(2)2lmnl 則則G是非可平面圖。是非可平面圖。 (2) 推論推論2的條件是的條件是G是平面圖的必要條件是平面圖的必要條件,不

18、是充分條件。不是充分條件。 例例1 求證：求證：K3,3是非可平面圖。是非可平面圖。 證明：注意到，證明：注意到，K3,3是偶圖，不存在奇圈，所以，每是偶圖，不存在奇圈，所以，每個面的次數(shù)至少是個面的次數(shù)至少是4,即即 l=4 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 所以，所以， 而而m=9，這樣有：，這樣有： 所以，由推論所以，由推論2，K3,3是非平面圖。是非平面圖。4(2)(62)822lnl(2)2lmnl 推論推論3 設(shè)設(shè)G是具有是具有n n個點(diǎn)個點(diǎn)m m條邊條邊個面的簡單平面圖，個面的簡單平面圖，則：則：36

19、mn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 證明：情形證明：情形1，G連通。連通。 因?yàn)橐驗(yàn)镚是簡單圖，所以每個面的次數(shù)至少為是簡單圖，所以每個面的次數(shù)至少為3，即，即l=3。于是，由推論于是，由推論2得：得： 情形情形2，若，若G不連通。設(shè)不連通。設(shè)G1,G2,Gk是連通分支。是連通分支。36mn 一方面一方面,由推論由推論1：1nmk 另一方面，由次數(shù)公式得：另一方面，由次數(shù)公式得：23m 所以得：所以得：33(1)36mnkn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5

20、 0 0.5 1 n 22 例例2，證明：，證明：K5是非可平面圖。是非可平面圖。 證明：證明：K5是簡單圖，是簡單圖，m=10, n=5。3n-6=9。 得，得， ，所以，所以K5是非可平面圖。是非可平面圖。36mn 推論推論4 設(shè)設(shè)G是具有是具有n n個點(diǎn)個點(diǎn)m m條邊的連通平面圖，若條邊的連通平面圖，若G G的的每個圈均由長度是每個圈均由長度是 l 的圈圍成，則：的圈圍成，則：(2)(2)m ll n 證明：由次數(shù)公式，歐拉公式容易得證。證明：由次數(shù)公式，歐拉公式容易得證。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23

21、推論推論5 設(shè)設(shè)G是具有是具有n n個點(diǎn)個點(diǎn)m m條邊的簡單平面圖，則：條邊的簡單平面圖，則：5 證明：若不然，設(shè)證明：若不然，設(shè)6 由握手定理：由握手定理：()6( )236v V Gnd vmmn 這與這與G是簡單平面圖矛盾。是簡單平面圖矛盾。 注：該結(jié)論是證明注：該結(jié)論是證明“5色定理色定理”的出發(fā)點(diǎn)。的出發(fā)點(diǎn)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24 定理定理3 一個連通平面圖是一個連通平面圖是2連通的，當(dāng)且僅當(dāng)它的每連通的，當(dāng)且僅當(dāng)它的每個面的邊界是圈。個面的邊界是圈。 證明：證明：“必要性必要性”： 不失一般

22、性，假設(shè)不失一般性，假設(shè)G沒有環(huán)，那沒有環(huán)，那么么G沒有割邊，也沒有割點(diǎn)。所以，每個面的邊界一定沒有割邊，也沒有割點(diǎn)。所以，每個面的邊界一定是一條閉跡。是一條閉跡。 設(shè)設(shè)C是是G的任意面的一個邊界，我們證明，它一定為圈。的任意面的一個邊界，我們證明，它一定為圈。 若不然，設(shè)若不然，設(shè)C是是G的某面的邊界，但它不是圈。的某面的邊界，但它不是圈。 因因C是一條閉跡且不是圈，因此，是一條閉跡且不是圈，因此，C中存在子圈。設(shè)該中存在子圈。設(shè)該子圈是子圈是W1.因因C是某面的邊界，所以是某面的邊界，所以W1與與C的關(guān)系可以表的關(guān)系可以表示為下圖的形式：示為下圖的形式： 0.8 1 0.6 0.4 0.2

23、 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25vvj-1v1v2vi-1vi+1vnW1 容易知道：容易知道：v為為G的割點(diǎn)。矛盾！的割點(diǎn)。矛盾！ “充分性充分性” 設(shè)平面圖設(shè)平面圖G的每個面的邊界均為圈。此時的每個面的邊界均為圈。此時刪去刪去G中任意一個點(diǎn)不破壞中任意一個點(diǎn)不破壞G的連通性，這表明的連通性，這表明G是是2連連通的。通的。 推論推論6 若一個平面圖是若一個平面圖是2連通的，則它的每條邊恰在兩連通的，則它的每條邊恰在兩個面的邊界上。個面的邊界上。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1

24、 n 26(三三)、圖的嵌入性問題簡介、圖的嵌入性問題簡介 在圖的平面嵌入的基礎(chǔ)上，簡單介紹：在圖的平面嵌入的基礎(chǔ)上，簡單介紹： 1、曲面嵌入、曲面嵌入 1)、球面嵌入、球面嵌入 定理定理4 G可球面嵌入當(dāng)且僅當(dāng)可球面嵌入當(dāng)且僅當(dāng)G可平面嵌入。可平面嵌入。 證明：我們用建立球極平面射影的方法給出證明。證明：我們用建立球極平面射影的方法給出證明。 將求面將求面S放在一個平面放在一個平面P上，設(shè)切點(diǎn)為上，設(shè)切點(diǎn)為O，過，過O作垂直作垂直于于P的直線，該直線與的直線，該直線與S相交于相交于z。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n

25、 27 2)、環(huán)面嵌入、環(huán)面嵌入 環(huán)面的形狀像一個汽車輪胎的表面。環(huán)面的形狀像一個汽車輪胎的表面。PzyOx球極投影示意圖球極投影示意圖 作映射作映射 f : S -z P。定義。定義 f (x) = y, 使得使得x ,y , z三點(diǎn)三點(diǎn)共線。該映射稱為球極平面射影。共線。該映射稱為球極平面射影。 通過通過f, 可以把嵌入球面的圖映射為嵌入平面的圖。反可以把嵌入球面的圖映射為嵌入平面的圖。反之亦然。之亦然。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 例例3 將將K4, K5, K3,3嵌入到環(huán)面上。嵌入到環(huán)面上。 3)

26、定向曲面嵌入定向曲面嵌入K4的環(huán)面嵌入的環(huán)面嵌入K5的環(huán)面嵌入的環(huán)面嵌入K3,3的環(huán)面嵌入的環(huán)面嵌入 這是目前嵌入性問題研究熱點(diǎn)。國內(nèi)：劉彥佩，黃元這是目前嵌入性問題研究熱點(diǎn)。國內(nèi)：劉彥佩，黃元秋等是從事該方向研究的代表。秋等是從事該方向研究的代表。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 2、圖的、圖的3維空間嵌入維空間嵌入 定理定理5 所有圖均可嵌入所有圖均可嵌入R3中。中。 證明：在證明：在R3中作空間曲線：中作空間曲線：23:xtlytzt 把圖把圖G的頂點(diǎn)放在該直線的不同位置，則的頂點(diǎn)放在該直線的不同位置，則G

27、的任意邊不的任意邊不相交。相交。 事實(shí)上，對處于曲線事實(shí)上，對處于曲線 l 上的任意上的任意4個相異頂點(diǎn)，它們對個相異頂點(diǎn)，它們對應(yīng)的參數(shù)值分別為：應(yīng)的參數(shù)值分別為：t1,t2,t3,t4。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 因?yàn)椋阂驗(yàn)椋?311123222233332344411011tttttttttttt 所以，上面所以，上面4點(diǎn)不共面。點(diǎn)不共面。(四四)、凸多面體與平面圖、凸多面體與平面圖 一個多面體稱為凸多面體，如果在體上任取兩點(diǎn)，其一個多面體稱為凸多面體，如果在體上任取兩點(diǎn)，其連線均在體上。連線均在體上。 凸多面體的一維骨架：把一個凸多面體壓縮在平面上，凸多面體的一維骨架：把一個凸多面體壓縮在平面上，得到一個對應(yīng)的平面圖，該平面圖稱為該凸多面體的一得到一個對應(yīng)的平面圖，該平面圖稱為該凸多面體的一維骨架。維骨架。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 定理定理6 存在且只存在存在且只存在5種正多面體：它們是正四、六、種正多面體：它們是正四、六、八、十二、二十面體。八、十二、二十面體。 證明：任取一個正證明：任取一個正面體，其頂點(diǎn)數(shù)、棱數(shù)分別是面體，其頂點(diǎn)數(shù)、棱