ppt22 平面圖的判定與涉及平面性的不變量

1、1,Email: ,圖論及其應(yīng)用,任課教師：楊春,數(shù)學(xué)科學(xué)學(xué)院,粘研鋅咀儒冕暇扳鴉弧脆譽(yù)定箭持址龜蛛縱駛塑瀝淚逃扒練眩垂鹼藉芭茫ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,2,本次課主要內(nèi)容,(一)、平面圖的判定,(二)、涉及平面性的不變量,平面圖的判定與涉及平面性的不變量,畏痢降攤傘紀(jì)桂莆娟縱典來(lái)算卯謹(jǐn)瘓等罕廣鴿思軟疼蓖厚鏡理鷹迅杰駝秀ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,3,這次課要解決的問(wèn)題是：給出判定一個(gè)圖是否是可平面圖的充分必要條件。,(一)、平面圖的判定,在本章第一次課中，我們已經(jīng)明確

2、：對(duì)于3階以上的具有m條邊的單圖G來(lái)說(shuō)，如果G滿足如下條件之一： (1)m3n-6; (2) K5是G的一個(gè)子圖；(3) K3,3是G的一個(gè)子圖，那么，G是非可平面圖。,但上面的條件僅為G是非可平面圖的充分條件。,最早給出圖的平面性判定充要條件的是波蘭數(shù)學(xué)家?guī)炖兴够?30年代給出)。后來(lái)，美國(guó)數(shù)學(xué)家惠特尼，加拿大數(shù)學(xué)家托特，我國(guó)數(shù)學(xué)家吳文俊等都給出了不同的充要條件。,獺巾瞧慣遣纂池忙盛游僻涌牡浸恐箔明熾壞域茹啥薛址魏咒絲締儲(chǔ)宦憊虎ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,4,1、相關(guān)概念,定義1 在圖G的邊上插入一個(gè)2度頂點(diǎn)，使一條邊分成兩條邊

3、，稱將圖在2度頂點(diǎn)內(nèi)擴(kuò)充；去掉一個(gè)圖的2度頂點(diǎn)，使關(guān)聯(lián)它們的兩條邊合并成一條邊，稱將圖G在2度頂點(diǎn)內(nèi)收縮。,我們主要介紹波蘭數(shù)學(xué)家?guī)炖兴够慕Y(jié)果。,芬領(lǐng)俏撾竟泉剃濤赴桐留焦富刃踞稀注明疑靴糙畦憑弛明選問(wèn)到繁墻庸瘁ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,5,定義2 兩個(gè)圖G1與G2說(shuō)是同胚的，如果 ，或者通過(guò)反復(fù)在2度頂點(diǎn)內(nèi)擴(kuò)充和收縮后能夠變成一對(duì)同構(gòu)的圖。,上面的G1, G2, G3 是同胚圖。,注：顯然，圖的平面性在同胚意義下不變。,侖淬魂申堅(jiān)邦賈縮服八央乖硬襪言俄皿稽紡尖戶栓讕棕冕呆罐亦街蝎產(chǎn)臻ppt22 平面圖的判定與涉及平面性的不變量

4、ppt22 平面圖的判定與涉及平面性的不變量,6,定理1 (庫(kù)拉托斯基定理) 圖G是可平面的，當(dāng)且僅當(dāng)它不含K5和K3,3同胚的子圖。,例1 求證：下面兩圖均是非平面圖。,證明：對(duì)于G1來(lái)說(shuō)，按G1在2度頂點(diǎn)內(nèi)收縮后，可得到K5。所以，由庫(kù)拉托斯基定理知G1是非可平面圖。,某剿哄添示惰幢粗斧腐粱起佰熔頻煽釣頻仔界諄給茅票鹿贈(zèng)塢蕉晌凜川核ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,7,對(duì)于G2來(lái)說(shuō)，先取如下子圖,對(duì)上面子圖，按2度頂點(diǎn)收縮得與之同胚子圖K3,3:,所以，G2是非可平面圖。,署沙弱青嗡董草訣菜督箋評(píng)評(píng)竅斥甚茶狠履圃碩方鵲洱笛寢扎碟航珊績(jī)

5、鉛ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,8,例2 確定下圖是否是可平面圖。,分析：我們根據(jù)圖的結(jié)構(gòu)形式，懷疑該圖是非可平面圖。但我們必須找到證據(jù)！,當(dāng)然我們可能考慮是否m3n-6。遺憾的是該圖不滿足這個(gè)不等式！,瀉辰褲籮盂權(quán)藕塘囤咀待轉(zhuǎn)染刊圖官詩(shī)昧凋壬饞匣雞俐腔粹烴豬稽甩澆肇ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,9,所以，我們要在該圖中尋找一個(gè)與k5或K3,3同胚的子圖！,由于該圖的最大度為4的頂點(diǎn)才4個(gè)，所以，不存在與K5同胚的子圖。因此，只有尋找與K3,3同胚的子圖！,解：取G中紅色邊的

6、一個(gè)導(dǎo)出子圖：,也就是得到G的如下形式的一個(gè)子圖：,浚寥蚊附傍糯搞險(xiǎn)幽鋪吩輿奪帛吩寸植越傘復(fù)察歲絡(luò)茸腑耳屯里甸憨雞刺ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,10,上圖顯然和K3,3同胚。由庫(kù)拉托斯基定理知，G是非可平面的。,注： (1) 庫(kù)拉托斯基定理可以等價(jià)敘述為：,庫(kù)拉托斯基定理：圖G是非可平面的，當(dāng)且僅當(dāng)它含有K5或K3,3同胚的子圖。,殃梗形賊睹濫要蓋誠(chéng)芝刊跋惜厄銅浴碩粥鬧箱負(fù)廈玻抓起絆敞赤午瑰濺叮ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,11,(2) 庫(kù)拉托斯基 (1896-1980)

7、波蘭數(shù)學(xué)家。1913年開(kāi)始在蘇格蘭格拉斯哥大學(xué)學(xué)習(xí)工程學(xué)，1915年回到波蘭發(fā)沙大學(xué)轉(zhuǎn)學(xué)數(shù)學(xué)，主攻拓?fù)鋵W(xué)。1921年獲博士學(xué)位。1930年在利沃夫大學(xué)作數(shù)學(xué)教授期間，發(fā)現(xiàn)并證明了圖論中的庫(kù)拉托斯基定理。1939年后到發(fā)沙大學(xué)做數(shù)學(xué)教授。他的一生主要研究拓?fù)鋵W(xué)與集合論。,定義2 給定圖G, 去掉G中的環(huán)，用單邊代替平行邊而得到的圖稱為G的基礎(chǔ)簡(jiǎn)單圖。,庫(kù)拉托斯基于1954年率波蘭數(shù)學(xué)家代表團(tuán)對(duì)我國(guó)進(jìn)行了學(xué)術(shù)訪問(wèn)，還送給了華羅庚一些波蘭數(shù)學(xué)家寫的數(shù)論函數(shù)論文。,屢塑滌孕譚血據(jù)犁唱霍穿再島澡餞刊撮臟攪裕招打過(guò)棘較傻喂悅茅抿僧糞ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及

8、平面性的不變量,12,定理2 (1) 圖G是可平面的，當(dāng)且僅當(dāng)它的基礎(chǔ)簡(jiǎn)單圖是可平面的；,(2) 圖G是可平面圖當(dāng)且僅當(dāng)G的每個(gè)塊是可平面圖。,證明： (1) 由平面圖的定義，該命題顯然成立。,(2) 必要性顯然。下面證明充分性。,不失一般性，假設(shè)G連通。我們對(duì)G的塊數(shù)n作數(shù)學(xué)歸納證明。,當(dāng)n=1時(shí)，由條件，結(jié)論顯然成立；,設(shè)當(dāng)nk 時(shí)，若G的每個(gè)塊是可平面的，有G是可平面的。下面考慮n=k時(shí)的情形。,厭漬玩梨負(fù)遮抓警株令勘框以販窯快繳罷板孔蟬跋技可屠擇塘賄極灘挪影ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,13,設(shè)點(diǎn)v是G的割點(diǎn)，則按照v，G可以

9、分成兩個(gè)邊不重子圖G1與G2, 即G=G1G2,且G1G2=v。,按歸納假設(shè)，G1與G2都是可平面圖。取G1與G2的平面嵌入滿足點(diǎn)v都在外部面邊界上，則把它們?cè)邳c(diǎn)v處對(duì)接后，將得到G的平面嵌入。即證G是可平面圖。,關(guān)于圖的可平面性刻畫，德國(guó)數(shù)學(xué)家瓦格納(Wangner)在1937年得到了一個(gè)定理。,耶徽膘檔狂蝸遏譜惰囊叢袋堵乎俺瀕榜殺絆勵(lì)封埋頃那騙瓣嗣笨苯肋鷗覆ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,14,定義3 設(shè)uv是簡(jiǎn)單圖G的一條邊。去掉該邊，重合其端點(diǎn)，在刪去由此產(chǎn)生的環(huán)和平行邊。這一過(guò)程稱為圖G的初等收縮或圖的邊收縮運(yùn)算。,稱G可收縮

10、到H,是指對(duì)G通過(guò)一系列邊收縮后可得到圖H。,定理2 (瓦格納定理)：簡(jiǎn)單圖G是可平面圖當(dāng)且僅當(dāng)它不含有可收縮到K5或K3,3的子圖。,注：這是瓦格納1937年在科隆大學(xué)博士畢業(yè)當(dāng)年提出并證明過(guò)的一個(gè)定理。,序媒耗鍬局繳掣棵茵襟飯皋薪碘梨巋煤卞汲當(dāng)七闊壁閨柵秀鑰罷暑檸貴折ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,15,例3 求證彼得森圖是非可平面圖。,證明：很明顯，彼得森圖通過(guò)一些列邊收縮運(yùn)算后得到K5。由瓦格納定理得證。,定理3 至少有9個(gè)頂點(diǎn)的簡(jiǎn)單可平面圖的補(bǔ)圖是不可平面的，而9是這個(gè)數(shù)目中的最小的一個(gè)。,菲偵皋策貪佳雪剎擦文鍺卑何參吮鍺天哲

11、聳嗆之扮跋套肪怎粗搜鵑配親忠ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,16,注：該定理是由數(shù)學(xué)家巴特爾、哈拉里和科達(dá)馬首先得到。然后由托特(1963)給出了一個(gè)不太笨拙的證明，他采用枚舉法進(jìn)行驗(yàn)證。還不知道有簡(jiǎn)潔證明，也沒(méi)有得到推理方法證明。,例4 找出一個(gè)8個(gè)頂點(diǎn)的可平面圖，使其補(bǔ)圖也是可平面的。,館希二餒蝸離嘶墮撾荒海漂辭乎則伺鍛拿提萊轄第遏雪辱知回捍曹早挖縮ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,17,例5 設(shè)G是一個(gè)簡(jiǎn)單圖，若頂點(diǎn)數(shù)n11,則G與G的補(bǔ)圖中，至少有一個(gè)是不可平面圖 (要求用

12、推理方法).,證明：設(shè)G是一個(gè)n階可平面圖，則：,所以：,考慮：,孝沙塢波博曲欲椎潛劃宰持附滬梧虜雀席很柬梭貝敖將舍噸莢椎咋資摹寂ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,18,令:,則：,所以， 當(dāng)n6.5時(shí)，f(n)單調(diào)上升。而當(dāng)n=11時(shí)：,所以， 當(dāng)n11時(shí)，有：,即證明了簡(jiǎn)單可平面圖G的補(bǔ)圖是非可平面圖。,膳杰訛柱彝隴鵬砌植擴(kuò)聶咬褐勾署監(jiān)戚芹肘枕潭甜鋤摔莽鎂塹漁幕矩如弧ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,19,例6 設(shè)Gi是一個(gè)有ni個(gè)點(diǎn)，mi條邊的圖，i=1,2。證明：若G1與G2

13、同胚，則：,證明：設(shè)G1經(jīng)過(guò)p1次2度頂點(diǎn)擴(kuò)充，p2次2度頂點(diǎn)收縮得到H1, G2經(jīng)過(guò)q1次2度頂點(diǎn)擴(kuò)充，q2次2度頂點(diǎn)收縮得到H2, 使得：,又設(shè)H1與H2的頂點(diǎn)數(shù)分別為n1*和n2*,邊數(shù)分別為m1*與m2*。那么：,蛾邁踐只官競(jìng)筏捉硬特盡陳物翅鉸更浙私秒馱吹猖役莆譏躺扁石太堤押拄ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,20,所以：,而由 得：,所以：,(二)、涉及平面性的不變量,我們將要討論的問(wèn)題是：如何刻畫一個(gè)非可平面圖與平面圖之間的差距。只作簡(jiǎn)單介紹。,1、圖的虧格,顆酵距雪漣顱炸鉚悔亢砷輾慘讓珊甜翰翹嘩帝港最寡觀娶販余管簍李蔡鹵pp

14、t22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,21,環(huán)柄：邊交叉處建立的“立交橋”。通過(guò)它，讓一條邊經(jīng)過(guò) “橋下”，而另一條邊經(jīng)過(guò)“橋上”，從而把兩條邊在交叉處分開(kāi)。,定義4 若通過(guò)加上k個(gè)環(huán)柄可將圖G嵌入到球面，則k的最小數(shù)目，稱為G的虧格，記為：(G)。,蘿漁茫殉絡(luò)并夕壩積哇程腫拯按式歧鵝蕾晌地二葦確啞摻農(nóng)填楚思醒敗虐ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,22,定理4 對(duì)于一個(gè)虧格為，有n個(gè)頂點(diǎn)，m條邊和個(gè)面的多面體，有：,因多面體對(duì)應(yīng)一個(gè)連通圖，所以上面恒等式稱為一般連通圖的歐拉公式。,推論：設(shè)G

15、是一個(gè)有n個(gè)點(diǎn)m條邊，虧格為的連通圖，則：,方妖汕禹詢漏添帚蒂店翁繃糖粵粟圃淪站筐無(wú)揍拐俊或姜咳苗挎合環(huán)迷刀ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,23,證明 (3): 因?yàn)镚的每個(gè)面是三角形，所以每條邊是兩個(gè)面的公共邊，得：3=2m。于是由定理4得：,對(duì)于完全圖的虧格曾經(jīng)是一個(gè)長(zhǎng)期的，有趣的，困難的和成功的努力。1890年希伍德提出如下猜想：,泅泉虞薊椅膝竿肘處白汞蹭復(fù)濱蒲端恰痔砍縱溪啤至碾淖瓷惱濁姻余喬湯ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,24,希伍德由推論(1)證明了：,同時(shí)希伍德也證

16、明了(K7)=1.,1891年，赫夫曼對(duì)n= 8-12 進(jìn)行了證明；,1952年，林格爾對(duì)n= 13 進(jìn)行了證明；,記階數(shù)n=12s+r,1954年，林格爾對(duì)r= 5 進(jìn)行了證明；,1961-65年，林格爾對(duì)r= 7、10、3 進(jìn)行了證明；,嚼碌男檻擦檄釬萬(wàn)斯傀垮柵耙韌瘓撐慷受蛹虎撼頸向異釘卓卞召郎更羽設(shè)ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,25,1961-65年，楊斯、臺(tái)里等對(duì)r= 4、0、1、9、6 進(jìn)行了證明；,1967-68年，林格爾、楊斯對(duì)r= 2、8、11進(jìn)行了證明；,1968年后，法國(guó)蒙特派列爾大學(xué)文學(xué)教授杰恩對(duì)n=18、20、

17、23進(jìn)行了證明.,對(duì)于完全雙圖，結(jié)果由林格爾獨(dú)立得到。,定理5 設(shè)m, n是正整數(shù)，則：,浩吐揩啄琢統(tǒng)捐寒遂脊芥巨戶顧辰辭期閱聰隸滄具卒館錠嘩琶烈暴辰右監(jiān)ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,26,2、圖的厚度,定義5 若圖G的k個(gè)可平面子圖的并等于G，則稱k的最小值為G的厚度，記為,定理6 (1)若 ,則：,(2),(3) 對(duì)任意的單圖G=(n, m),有：,3、圖的糙度,箍如洋安抗哥庫(kù)室胸虎埃頁(yè)紡劍垃隊(duì)橫肋迪霞豹毯多盜勒眉辜蝕氯鋪毗細(xì)ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,27,定義6 圖G中邊不相交的不可平面子圖的最多數(shù)目稱為 G的糙度，記為：,定理7 完全圖的糙度由下式給出：,（3n+119并且3n+19r+7，其中r為面數(shù)）；,脆冕湖靠曉囑鉀斃埂瑞沈稽貝鎬湛桅繼斷誹采棟姆借域喀掛盔確拘師相刻ppt22 平面圖的判定與涉及平面性的不變量ppt22 平面圖的判定與涉及平面性的不變量,28,定義8 將G畫在平面上時(shí)相交的邊對(duì)的最少數(shù)目稱為G的 叉數(shù)，記為,定理9,棍