圖論平面圖的判定與涉及平面性的不變量ppt課件

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 圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院應(yīng)用數(shù)學(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 本次課主要內(nèi)容本次課主要內(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 這次課要解決的問(wèn)題是：給出判定一個(gè)圖是否是可這次課要解決的

2、問(wèn)題是：給出判定一個(gè)圖是否是可平面圖的充分必要條件。平面圖的充分必要條件。(一一)、平面圖的判定、平面圖的判定 在本章第一次課中，我們已經(jīng)明確：對(duì)于在本章第一次課中，我們已經(jīng)明確：對(duì)于3階以上的階以上的具有具有m條邊的圖條邊的圖G來(lái)說(shuō)，如果來(lái)說(shuō)，如果G滿足如下條件之一：滿足如下條件之一： (1)m3n-6; (2) K5是是G的一個(gè)子圖；的一個(gè)子圖；(3) K3,3是是G的一個(gè)的一個(gè)子圖，那么，子圖，那么，G是非可平面圖。是非可平面圖。 但上面的條件僅為但上面的條件僅為G是非可平面圖的充分條件。是非可平面圖的充分條件。 最早給出圖的平面性判定充要條件的是波蘭數(shù)學(xué)家最早給出圖的平面性判定充要條件

3、的是波蘭數(shù)學(xué)家?guī)炖兴够鶐?kù)拉托斯基(30年代給出年代給出)。后來(lái)，美國(guó)數(shù)學(xué)家惠特尼，。后來(lái)，美國(guó)數(shù)學(xué)家惠特尼，加拿大數(shù)學(xué)家托特，我國(guó)數(shù)學(xué)家吳文俊等都給出了不同加拿大數(shù)學(xué)家托特，我國(guó)數(shù)學(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 所以，我們稱(chēng)所以，我們稱(chēng)K5與與K3,3為庫(kù)拉托斯基圖。為庫(kù)拉托斯基圖。 我們主要介紹波蘭數(shù)學(xué)家?guī)炖兴够慕Y(jié)果。我們主要介紹波蘭數(shù)學(xué)家?guī)炖兴够慕Y(jié)果。 庫(kù)拉托斯基定理主要基于庫(kù)拉托斯基定理主要基于K5和和K3,3是非可平面圖這是非可平面圖這一事實(shí)而提出的平

4、面性判定方法。一事實(shí)而提出的平面性判定方法。 一個(gè)自然的猜測(cè)是：一個(gè)自然的猜測(cè)是：G是可平面圖的充分必要條件是是可平面圖的充分必要條件是G不含子圖不含子圖K5和和K3,3。 上面命題必要性顯然成立！但充分性能成立嗎？上面命題必要性顯然成立！但充分性能成立嗎？ 十分遺憾！下面例子給出了回答：十分遺憾！下面例子給出了回答：NO! 下面的圖下面的圖G是一個(gè)點(diǎn)數(shù)為是一個(gè)點(diǎn)數(shù)為5，邊數(shù)為，邊數(shù)為9的極大平面圖。的極大平面圖。思索思索 F=GK3 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 注：注：F由由G的的3個(gè)拷貝組成，分別是個(gè)拷貝組成，

5、分別是G1,G2,G3。三個(gè)。三個(gè)拷貝中的邊沒(méi)有畫(huà)出。圖中虛線不是對(duì)應(yīng)的拷貝中的邊沒(méi)有畫(huà)出。圖中虛線不是對(duì)應(yīng)的Gi中邊。中邊。Gu5u4u3u2u1v5v4v3v2v1w5w4w3w2w13FGKG3G2G1 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 可以證明：可以證明：F中不含中不含K5和和K3,3，且，且F是非可平面圖。是非可平面圖。 盡管我們的直覺(jué)猜測(cè)錯(cuò)了，但庫(kù)拉托斯基還是基于盡管我們的直覺(jué)猜測(cè)錯(cuò)了，但庫(kù)拉托斯基還是基于K5與與K3,3得到了圖的平面性判據(jù)。得到了圖的平面性判據(jù)。 1、相關(guān)概念、相關(guān)概念 定義定義1 在圖在

6、圖G的邊上插入一個(gè)的邊上插入一個(gè)2度頂點(diǎn)，使一條邊分度頂點(diǎn)，使一條邊分成兩條邊，稱(chēng)將圖在成兩條邊，稱(chēng)將圖在2度頂點(diǎn)內(nèi)擴(kuò)充；去掉一個(gè)圖的度頂點(diǎn)內(nèi)擴(kuò)充；去掉一個(gè)圖的2度度頂點(diǎn)，使關(guān)聯(lián)它們的兩條邊合并成一條邊，稱(chēng)將圖頂點(diǎn)，使關(guān)聯(lián)它們的兩條邊合并成一條邊，稱(chēng)將圖G在在2度頂點(diǎn)內(nèi)收縮。度頂點(diǎn)內(nèi)收縮。 在在2度頂點(diǎn)內(nèi)收縮度頂點(diǎn)內(nèi)收縮在在2度頂點(diǎn)內(nèi)擴(kuò)充度頂點(diǎn)內(nèi)擴(kuò)充 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 兩個(gè)圖兩個(gè)圖G1與與G2說(shuō)是同胚的，假設(shè)說(shuō)是同胚的，假設(shè) ，或，或者通過(guò)反復(fù)在者通過(guò)反復(fù)在2度頂點(diǎn)內(nèi)擴(kuò)充和收縮后能夠變成一對(duì)同

7、度頂點(diǎn)內(nèi)擴(kuò)充和收縮后能夠變成一對(duì)同構(gòu)的圖。構(gòu)的圖。 12GGG3G2G1 上面的上面的G1, G2, G3 是同胚的。是同胚的。 注：圖的平面性在同胚意義下不變。注：圖的平面性在同胚意義下不變。 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 定理定理1 (庫(kù)拉托斯基定理庫(kù)拉托斯基定理) 圖圖G是可平面的，當(dāng)且僅當(dāng)是可平面的，當(dāng)且僅當(dāng)它不含它不含K5或或K3,3同胚的子圖。同胚的子圖。 例例1 求證：下面兩圖均是非平面圖。求證：下面兩圖均是非平面圖。圖圖 G1G1圖圖 G2G2 證明：對(duì)于證明：對(duì)于G1來(lái)說(shuō)，按來(lái)說(shuō)，按G1在在2度頂點(diǎn)

8、內(nèi)收縮后，可度頂點(diǎn)內(nèi)收縮后，可得到得到K5。所以，由庫(kù)拉托斯基定理知。所以，由庫(kù)拉托斯基定理知G1是非可平面圖。是非可平面圖。 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 對(duì)于對(duì)于G2來(lái)說(shuō)，先取如下子圖來(lái)說(shuō)，先取如下子圖 G2G2的一個(gè)子圖的一個(gè)子圖 對(duì)上面子圖，按對(duì)上面子圖，按2度頂點(diǎn)收縮得與之同胚子圖度頂點(diǎn)收縮得與之同胚子圖K3,3:K3,3 所以，所以，G2是非可平面圖。是非可平面圖。 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 確定下圖是否是可平面圖。

9、確定下圖是否是可平面圖。u1u2v1v2y1y2x1x2w1w2 分析：我們根據(jù)圖的結(jié)構(gòu)形式，懷疑該圖是非可平分析：我們根據(jù)圖的結(jié)構(gòu)形式，懷疑該圖是非可平面圖。但我們必須找到證據(jù)！面圖。但我們必須找到證據(jù)！ 當(dāng)然我們可能考慮是否當(dāng)然我們可能考慮是否m3n-6。遺憾的是該圖不滿。遺憾的是該圖不滿足這個(gè)不等式！足這個(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 u1u2v1v2y1y2x1x2w1w2 所以，我們要在該圖中尋找一個(gè)與所以，我們要在該圖中尋找一個(gè)與k5或或K3,3同胚的同胚的子圖！子圖！ 由于該圖的最大度為由于該

10、圖的最大度為4的頂點(diǎn)才的頂點(diǎn)才4個(gè)，所以，不存在與個(gè)，所以，不存在與K5同胚的子圖。因此，只有尋找與同胚的子圖。因此，只有尋找與K3,3同胚的子圖！同胚的子圖！ 解：取解：取G中紅色邊的一個(gè)導(dǎo)出子圖：中紅色邊的一個(gè)導(dǎo)出子圖： 也就是得到也就是得到G的如下形式的一個(gè)子圖：的如下形式的一個(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 上圖顯然和上圖顯然和K3,3同胚。由庫(kù)拉托斯基定理知，同胚。由庫(kù)拉托斯基定理知，G是非可是非可平面的。平面的。u1u2v1v2y1y2x1x2w1w2 注：注： (1) 庫(kù)拉托斯基定理可以等價(jià)敘述為

11、：庫(kù)拉托斯基定理可以等價(jià)敘述為： 庫(kù)拉托斯基定理：圖庫(kù)拉托斯基定理：圖G是非可平面的，當(dāng)且僅當(dāng)它含有是非可平面的，當(dāng)且僅當(dāng)它含有K5或或K3,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 (2) 庫(kù)拉托斯基庫(kù)拉托斯基 (1896-1980) 波蘭數(shù)學(xué)家。波蘭數(shù)學(xué)家。1913年開(kāi)始年開(kāi)始在蘇格蘭格拉斯哥大學(xué)學(xué)習(xí)工程學(xué)，在蘇格蘭格拉斯哥大學(xué)學(xué)習(xí)工程學(xué)，1915年回到波蘭發(fā)沙年回到波蘭發(fā)沙大學(xué)轉(zhuǎn)學(xué)數(shù)學(xué)，主攻拓?fù)鋵W(xué)。大學(xué)轉(zhuǎn)學(xué)數(shù)學(xué)，主攻拓?fù)鋵W(xué)。1921年獲博士學(xué)位。年獲博士學(xué)位。1930年年在利沃夫大學(xué)作數(shù)學(xué)教授期

12、間，發(fā)現(xiàn)并證明了圖論中的庫(kù)在利沃夫大學(xué)作數(shù)學(xué)教授期間，發(fā)現(xiàn)并證明了圖論中的庫(kù)拉托斯基定理。拉托斯基定理。1939年后到發(fā)沙大學(xué)做數(shù)學(xué)教授。他的一年后到發(fā)沙大學(xué)做數(shù)學(xué)教授。他的一生主要研究拓?fù)鋵W(xué)與集合論。生主要研究拓?fù)鋵W(xué)與集合論。 庫(kù)拉托斯基定理：圖庫(kù)拉托斯基定理：圖G是非可平面的，當(dāng)且僅當(dāng)它含是非可平面的，當(dāng)且僅當(dāng)它含有有K5或或K3,3同胚的子圖。同胚的子圖。 定義定義2 給定圖給定圖G, 去掉去掉G中的環(huán)，用單邊代替平行邊而中的環(huán)，用單邊代替平行邊而得到的圖稱(chēng)為得到的圖稱(chēng)為G的基礎(chǔ)簡(jiǎn)單圖。的基礎(chǔ)簡(jiǎn)單圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5

13、 0 0.5 1 n 定理定理2 (1) 圖圖G是可平面的，當(dāng)且僅當(dāng)它的基礎(chǔ)簡(jiǎn)單圖是可平面的，當(dāng)且僅當(dāng)它的基礎(chǔ)簡(jiǎn)單圖是可平面的；是可平面的； (2) 圖圖G是可平面圖當(dāng)且僅當(dāng)是可平面圖當(dāng)且僅當(dāng)G的每個(gè)塊是可平面圖。的每個(gè)塊是可平面圖。 證明：證明： (1) 由平面圖的定義，該命題顯然成立。由平面圖的定義，該命題顯然成立。 (2) 必要性顯然。下面證明充分性。必要性顯然。下面證明充分性。 不失一般性，假設(shè)不失一般性，假設(shè)G連通。我們對(duì)連通。我們對(duì)G的塊數(shù)的塊數(shù)n作數(shù)學(xué)歸作數(shù)學(xué)歸納證明。納證明。 當(dāng)當(dāng)n=1時(shí)，由條件，結(jié)論顯然成立；時(shí)，由條件，結(jié)論顯然成立； 設(shè)當(dāng)設(shè)當(dāng)nk 時(shí)，若時(shí)，若G的每個(gè)塊是

14、可平面的，有的每個(gè)塊是可平面的，有G是可平是可平面的。下面考慮面的。下面考慮n=k時(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 設(shè)點(diǎn)設(shè)點(diǎn)v是是G的割點(diǎn)，則按照的割點(diǎn)，則按照v，G可以分成兩個(gè)邊不重可以分成兩個(gè)邊不重子圖子圖G1與與G2, 即即G=G1G2,且且G1G2=v。vG2G1 按歸納假設(shè)，按歸納假設(shè)，G1與與G2都是可平面圖。取都是可平面圖。取G1與與G2的平的平面嵌入滿足點(diǎn)面嵌入滿足點(diǎn)v都在外部面邊界上，則把它們?cè)邳c(diǎn)都在外部面邊界上，則把它們?cè)邳c(diǎn)v處對(duì)處對(duì)接后，將得到接后，將得到G的平面嵌入。即證的平

15、面嵌入。即證G是可平面圖。是可平面圖。 關(guān)于圖的可平面性刻畫(huà)，數(shù)學(xué)家瓦格納關(guān)于圖的可平面性刻畫(huà)，數(shù)學(xué)家瓦格納(Wangner)在在1937年得到了一個(gè)定理。年得到了一個(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 定義定義3 設(shè)設(shè)uv是簡(jiǎn)單圖是簡(jiǎn)單圖G的一條邊。去掉該邊，重合其的一條邊。去掉該邊，重合其端點(diǎn)，在刪去由此產(chǎn)生的環(huán)和平行邊。這一過(guò)程稱(chēng)為圖端點(diǎn)，在刪去由此產(chǎn)生的環(huán)和平行邊。這一過(guò)程稱(chēng)為圖G的初等收縮或圖的邊收縮運(yùn)算。的初等收縮或圖的邊收縮運(yùn)算。 稱(chēng)稱(chēng)G可收縮到可收縮到H,是指對(duì)是指對(duì)G通過(guò)一系列邊收縮后可得到通過(guò)一

16、系列邊收縮后可得到圖圖H。 定理定理2 (瓦格納定理瓦格納定理)：簡(jiǎn)單圖：簡(jiǎn)單圖G是可平面圖當(dāng)且僅當(dāng)它是可平面圖當(dāng)且僅當(dāng)它不含有可收縮到不含有可收縮到K5或或K3,3的子圖。的子圖。 注：這是瓦格納注：這是瓦格納1937年在科隆大學(xué)博士畢業(yè)當(dāng)年提出年在科隆大學(xué)博士畢業(yè)當(dāng)年提出并證明過(guò)的一個(gè)定理。并證明過(guò)的一個(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 例例3 求證彼得森圖是非可平面圖。求證彼得森圖是非可平面圖。 證明：很明顯，彼得森圖通過(guò)一些列邊收縮運(yùn)算后得證明：很明顯，彼得森圖通過(guò)一些列邊收縮運(yùn)算后得到到K5。由瓦格納定

17、理得證。由瓦格納定理得證。 定理定理3 至少有至少有9個(gè)頂點(diǎn)的簡(jiǎn)單可平面圖的補(bǔ)圖是不可平個(gè)頂點(diǎn)的簡(jiǎn)單可平面圖的補(bǔ)圖是不可平面的，而面的，而9是這個(gè)數(shù)目中的最小的一個(gè)。是這個(gè)數(shù)目中的最小的一個(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 注：該定理是由數(shù)學(xué)家巴特爾、哈拉里和科達(dá)馬首先注：該定理是由數(shù)學(xué)家巴特爾、哈拉里和科達(dá)馬首先得到。然后由托特得到。然后由托特(1963)給出了一個(gè)不太笨拙的證明，他給出了一個(gè)不太笨拙的證明，他采用枚舉法進(jìn)行驗(yàn)證。還不知道有簡(jiǎn)潔證明，也沒(méi)有得采用枚舉法進(jìn)行驗(yàn)證。還不知道有簡(jiǎn)潔證明，也沒(méi)有得到推理方法

18、證明。到推理方法證明。 例例4 找出一個(gè)找出一個(gè)8個(gè)頂點(diǎn)的可平面圖，使其補(bǔ)圖也是可平個(gè)頂點(diǎn)的可平面圖，使其補(bǔ)圖也是可平面的。面的。76543218G76543218G的補(bǔ)的補(bǔ) 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 設(shè)設(shè)G是一個(gè)簡(jiǎn)單圖，若頂點(diǎn)數(shù)是一個(gè)簡(jiǎn)單圖，若頂點(diǎn)數(shù)n11,則則G與與G的補(bǔ)的補(bǔ)圖中，至少有一個(gè)是不可平面圖圖中，至少有一個(gè)是不可平面圖 (要求用推理方法要求用推理方法). 證明：設(shè)證明：設(shè)G是一個(gè)是一個(gè)n階可平面圖，那么：階可平面圖，那么：()36m Gn 所以：所以：(1)()()()(36)2nn nm

19、 Gm Km Gn 思索：思索：2(1)1()(36)2(36)(1324)22n nm Gnnnn 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 令令: 那么：那么： 所以，所以， 當(dāng)當(dāng)n6.5時(shí)，時(shí)，f(n)單調(diào)上升。而當(dāng)單調(diào)上升。而當(dāng)n=11時(shí)：時(shí)：21( )(1324)2f nnn13( )2fnn(11)0f 所以，所以， 當(dāng)當(dāng)n11時(shí)，有：時(shí)，有：()(36)m Gn 即證明了簡(jiǎn)單可平面圖即證明了簡(jiǎn)單可平面圖G的補(bǔ)圖是非可平面圖。的補(bǔ)圖是非可平面圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5

20、 2 1 0.5 0 0.5 1 n 例例6 設(shè)設(shè)Gi是一個(gè)有是一個(gè)有ni個(gè)點(diǎn)，個(gè)點(diǎn)，mi條邊的圖，條邊的圖，i=1,2。證明：。證明：若若G1與與G2同胚，那么：同胚，那么： 證明：設(shè)證明：設(shè)G1經(jīng)過(guò)經(jīng)過(guò)p1次次2度頂點(diǎn)擴(kuò)充，度頂點(diǎn)擴(kuò)充，p2次次2度頂點(diǎn)收縮度頂點(diǎn)收縮得到得到H1, G2經(jīng)過(guò)經(jīng)過(guò)q1次次2度頂點(diǎn)擴(kuò)充，度頂點(diǎn)擴(kuò)充，q2次次2度頂點(diǎn)收縮得度頂點(diǎn)收縮得到到H2, 使得：使得：1221nmnm 又設(shè)又設(shè)H1與與H2的頂點(diǎn)數(shù)分別為的頂點(diǎn)數(shù)分別為n1*和和n2*,邊數(shù)分別為邊數(shù)分別為m1*與與m2*。那么：。那么：12HH1112*nnPP1112*mmPP2212*nnqq2212*m

21、mqq 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 所以：所以： 而由而由 得：得：12HH12121212*nmnmPPqq1212*,*mmnn21211212*nmnmPPqq 所以：所以：1221nmnm(二二)、涉及平面性的不變量、涉及平面性的不變量 我們將要討論的問(wèn)題是：如何刻畫(huà)一個(gè)非可平面圖與平我們將要討論的問(wèn)題是：如何刻畫(huà)一個(gè)非可平面圖與平面圖之間的差距。只作簡(jiǎn)單介紹。面圖之間的差距。只作簡(jiǎn)單介紹。 1、圖的虧格、圖的虧格 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0

22、0.5 1 n 環(huán)柄：邊交叉處建立的環(huán)柄：邊交叉處建立的“立交橋立交橋”。通過(guò)它，讓一條。通過(guò)它，讓一條邊經(jīng)過(guò)邊經(jīng)過(guò) “橋下橋下”，而另一條邊經(jīng)過(guò)，而另一條邊經(jīng)過(guò)“橋上橋上”，從而把兩，從而把兩條邊在交叉處分開(kāi)。條邊在交叉處分開(kāi)。環(huán)柄示意圖環(huán)柄示意圖 定義定義4 若通過(guò)加上若通過(guò)加上k個(gè)環(huán)柄可將圖個(gè)環(huán)柄可將圖G嵌入到球面，則嵌入到球面，則k的最小數(shù)目，稱(chēng)為的最小數(shù)目，稱(chēng)為G的虧格，記為：的虧格，記為：(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 定理定理4 對(duì)于一個(gè)虧格為對(duì)于一個(gè)虧格為，有，有n個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，m條邊和條邊

23、和個(gè)面?zhèn)€面的多面體，有：的多面體，有： 因多面體對(duì)應(yīng)一個(gè)連通圖，所以上面恒等式稱(chēng)為一般因多面體對(duì)應(yīng)一個(gè)連通圖，所以上面恒等式稱(chēng)為一般連通圖的歐拉公式。連通圖的歐拉公式。22nm 推論：設(shè)推論：設(shè)G是一個(gè)有是一個(gè)有n個(gè)點(diǎn)個(gè)點(diǎn)m條邊，虧格為條邊，虧格為的連通圖，的連通圖，那么：那么：11(1),(2 )62mn11( 2 ),(2 )42Gmn若無(wú) 三 角 形 ， 則 ： 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): 因?yàn)橐驗(yàn)镚的每個(gè)面是三角形，所以每條邊是兩的每個(gè)面是三角形，所以每條邊是兩個(gè)面的公共邊，得：個(gè)面的公

24、共邊，得：3=2m。于是由定理。于是由定理4得：得：(3),=3(2+2 )Gmn若每個(gè)面是三角形，則：(4),=2(2+2 )Gmn若每個(gè)面是四邊形，則：=3(2+2 )mn 對(duì)于完全圖的虧格曾經(jīng)是一個(gè)長(zhǎng)期的，有趣的，困難對(duì)于完全圖的虧格曾經(jīng)是一個(gè)長(zhǎng)期的，有趣的，困難的和成功的努力。的和成功的努力。1890年希伍德提出如下猜想：年希伍德提出如下猜想：(3)(4)()(*)12nnnK 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 希伍德由推論希伍德由推論(1)證明了：證明了：(3)(4)()12nnnK 同時(shí)希伍德也證明了同時(shí)希伍

25、德也證明了(K7)=1. 1891年，赫夫曼對(duì)年，赫夫曼對(duì)n= 8-12 進(jìn)行了證明；進(jìn)行了證明； 1952年，林格爾對(duì)年，林格爾對(duì)n= 13 進(jìn)行了證明；進(jìn)行了證明； 記階數(shù)記階數(shù)n=12s+r 1954年，林格爾對(duì)年，林格爾對(duì)r= 5 進(jìn)行了證明；進(jìn)行了證明； 1961-65年，林格爾對(duì)年，林格爾對(duì)r= 7、10、3 進(jìn)行了證明；進(jì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 1961-65年，楊斯、臺(tái)里等對(duì)年，楊斯、臺(tái)里等對(duì)r= 4、0、1、9、6 進(jìn)行進(jìn)行了證明；了證明； 1967-68年，林格爾、楊斯對(duì)年，林格爾、楊斯對(duì)r= 2、8、11進(jìn)行了證明；進(jìn)行了證明； 1968年后，法國(guó)蒙特派列爾大學(xué)文學(xué)教授杰恩對(duì)年后，法國(guó)蒙特派列爾大學(xué)文學(xué)教授杰恩對(duì)n=18、20、23進(jìn)行了證明進(jìn)行了證