圖論平面圖的判定與涉及平面性的不變量PPT教案

1、圖論平面圖的判定與涉及平面性的不變圖論平面圖的判定與涉及平面性的不變量量本次課主要內容(一)、平面圖的判定(二)、涉及平面性的不變量平面圖的判定與涉及平面性的不變量第1頁/共32頁 這次課要解決的問題是：給出判定一個圖是否是可平面圖的充分必要條件。(一)、平面圖的判定 在本章第一次課中，我們已經明確：對于3階以上的具有m條邊的圖G來說，如果G滿足如下條件之一： (1)m3n-6; (2) K5是G的一個子圖；(3) K3,3是G的一個子圖，那么，G是非可平面圖。 但上面的條件僅為G是非可平面圖的充分條件。 最早給出圖的平面性判定充要條件的是波蘭數(shù)學家?guī)炖兴够?30年代給出)。后來，美國數(shù)學家

2、惠特尼，加拿大數(shù)學家托特，我國數(shù)學家吳文俊等都給出了不同的充要條件。第2頁/共32頁 所以，我們稱K5與K3,3為庫拉托斯基圖。 我們主要介紹波蘭數(shù)學家?guī)炖兴够慕Y果。 庫拉托斯基定理主要基于K5和K3,3是非可平面圖這一事實而提出的平面性判定方法。 一個自然的猜測是：G是可平面圖的充分必要條件是G不含子圖K5和K3,3。 上面命題必要性顯然成立！但充分性能成立嗎？ 十分遺憾！下面例子給出了回答：NO! 下面的圖G是一個點數(shù)為5，邊數(shù)為9的極大平面圖?？紤] F=GK3第3頁/共32頁 注：F由G的3個拷貝組成，分別是G1,G2,G3。三個拷貝中的邊沒有畫出。圖中虛線不是對應的Gi中邊。Gu5

3、u4u3u2u1v5v4v3v2v1w5w4w3w2w13FGKG3G2G1第4頁/共32頁 可以證明：F中不含K5和K3,3，且F是非可平面圖。 盡管我們的直覺猜測錯了，但庫拉托斯基還是基于K5與K3,3得到了圖的平面性判據(jù)。 1、相關概念 定義1 在圖G的邊上插入一個2度頂點，使一條邊分成兩條邊，稱將圖在2度頂點內擴充；去掉一個圖的2度頂點，使關聯(lián)它們的兩條邊合并成一條邊，稱將圖G在2度頂點內收縮。 在2度頂點內收縮在2度頂點內擴充第5頁/共32頁 定義2 兩個圖G1與G2說是同胚的，如果 ，或者通過反復在2度頂點內擴充和收縮后能夠變成一對同構的圖。 12GGG3G2G1 上面的G1, G

4、2, G3 是同胚的。 注：圖的平面性在同胚意義下不變。第6頁/共32頁 定理1 (庫拉托斯基定理) 圖G是可平面的，當且僅當它不含K5或K3,3同胚的子圖。 例1 求證：下面兩圖均是非平面圖。圖 G1圖 G2 證明：對于G1來說，按G1在2度頂點內收縮后，可得到K5。所以，由庫拉托斯基定理知G1是非可平面圖。第7頁/共32頁 對于G2來說，先取如下子圖 G2的一個子圖 對上面子圖，按2度頂點收縮得與之同胚子圖K3,3:K3,3 所以，G2是非可平面圖。第8頁/共32頁 例2 確定下圖是否是可平面圖。u1u2v1v2y1y2x1x2w1w2 分析：我們根據(jù)圖的結構形式，懷疑該圖是非可平面圖。但

5、我們必須找到證據(jù)！ 當然我們可能考慮是否m3n-6。遺憾的是該圖不滿足這個不等式！第9頁/共32頁 u1u2v1v2y1y2x1x2w1w2 所以，我們要在該圖中尋找一個與k5或K3,3同胚的子圖！ 由于該圖的最大度為4的頂點才4個，所以，不存在與K5同胚的子圖。因此，只有尋找與K3,3同胚的子圖！ 解：取G中紅色邊的一個導出子圖： 也就是得到G的如下形式的一個子圖：第10頁/共32頁 上圖顯然和K3,3同胚。由庫拉托斯基定理知，G是非可平面的。u1u2v1v2y1y2x1x2w1w2 注： (1) 庫拉托斯基定理可以等價敘述為： 庫拉托斯基定理：圖G是非可平面的，當且僅當它含有K5或K3,3

6、同胚的子圖。第11頁/共32頁 (2) 庫拉托斯基 (1896-1980) 波蘭數(shù)學家。1913年開始在蘇格蘭格拉斯哥大學學習工程學，1915年回到波蘭發(fā)沙大學轉學數(shù)學，主攻拓撲學。1921年獲博士學位。1930年在利沃夫大學作數(shù)學教授期間，發(fā)現(xiàn)并證明了圖論中的庫拉托斯基定理。1939年后到發(fā)沙大學做數(shù)學教授。他的一生主要研究拓撲學與集合論。 庫拉托斯基定理：圖G是非可平面的，當且僅當它含有K5或K3,3同胚的子圖。 定義2 給定圖G, 去掉G中的環(huán)，用單邊代替平行邊而得到的圖稱為G的基礎簡單圖。第12頁/共32頁 定理2 (1) 圖G是可平面的，當且僅當它的基礎簡單圖是可平面的； (2) 圖

7、G是可平面圖當且僅當G的每個塊是可平面圖。 證明： (1) 由平面圖的定義，該命題顯然成立。 (2) 必要性顯然。下面證明充分性。 不失一般性，假設G連通。我們對G的塊數(shù)n作數(shù)學歸納證明。 當n=1時，由條件，結論顯然成立； 設當nk 時，若G的每個塊是可平面的，有G是可平面的。下面考慮n=k時的情形。第13頁/共32頁 設點v是G的割點，則按照v，G可以分成兩個邊不重子圖G1與G2, 即G=G1G2,且G1G2=v。vG2G1 按歸納假設，G1與G2都是可平面圖。取G1與G2的平面嵌入滿足點v都在外部面邊界上，則把它們在點v處對接后，將得到G的平面嵌入。即證G是可平面圖。 關于圖的可平面性刻

8、畫，數(shù)學家瓦格納(Wangner)在1937年得到了一個定理。第14頁/共32頁 定義3 設uv是簡單圖G的一條邊。去掉該邊，重合其端點，在刪去由此產生的環(huán)和平行邊。這一過程稱為圖G的初等收縮或圖的邊收縮運算。 稱G可收縮到H,是指對G通過一系列邊收縮后可得到圖H。 定理2 (瓦格納定理)：簡單圖G是可平面圖當且僅當它不含有可收縮到K5或K3,3的子圖。 注：這是瓦格納1937年在科隆大學博士畢業(yè)當年提出并證明過的一個定理。第15頁/共32頁 例3 求證彼得森圖是非可平面圖。 證明：很明顯，彼得森圖通過一些列邊收縮運算后得到K5。由瓦格納定理得證。 定理3 至少有9個頂點的簡單可平面圖的補圖是

9、不可平面的，而9是這個數(shù)目中的最小的一個。第16頁/共32頁 注：該定理是由數(shù)學家巴特爾、哈拉里和科達馬首先得到。然后由托特(1963)給出了一個不太笨拙的證明，他采用枚舉法進行驗證。還不知道有簡潔證明，也沒有得到推理方法證明。 例4 找出一個8個頂點的可平面圖，使其補圖也是可平面的。76543218G76543218G的補第17頁/共32頁 例5 設G是一個簡單圖，若頂點數(shù)n11,則G與G的補圖中，至少有一個是不可平面圖 (要求用推理方法). 證明：設G是一個n階可平面圖，則：()36m Gn 所以：(1)()()()(36)2nn nm Gm Km Gn 考慮：2(1)1()(36)2(3

10、6)(1324)22n nm Gnnnn第18頁/共32頁 令: 則： 所以， 當n6.5時，f(n)單調上升。而當n=11時：21( )(1324)2f nnn13( )2fnn(11)0f 所以， 當n11時，有：()(36)m Gn 即證明了簡單可平面圖G的補圖是非可平面圖。第19頁/共32頁 例6 設Gi是一個有ni個點，mi條邊的圖，i=1,2。證明：若G1與G2同胚，則： 證明：設G1經過p1次2度頂點擴充，p2次2度頂點收縮得到H1, G2經過q1次2度頂點擴充，q2次2度頂點收縮得到H2, 使得：1221nmnm 又設H1與H2的頂點數(shù)分別為n1*和n2*,邊數(shù)分別為m1*與m

11、2*。那么：12HH1112*nnPP1112*mmPP2212*nnqq2212*mmqq第20頁/共32頁 所以： 而由 得：12HH12121212*nmnmPPqq1212*,*mmnn21211212*nmnmPPqq 所以：1221nmnm(二)、涉及平面性的不變量 我們將要討論的問題是：如何刻畫一個非可平面圖與平面圖之間的差距。只作簡單介紹。 1、圖的虧格第21頁/共32頁 環(huán)柄：邊交叉處建立的“立交橋”。通過它，讓一條邊經過 “橋下”，而另一條邊經過“橋上”，從而把兩條邊在交叉處分開。環(huán)柄示意圖 定義4 若通過加上k個環(huán)柄可將圖G嵌入到球面，則k的最小數(shù)目，稱為G的虧格，記為：

12、(G)。第22頁/共32頁 定理4 對于一個虧格為，有n個頂點，m條邊和個面的多面體，有： 因多面體對應一個連通圖，所以上面恒等式稱為一般連通圖的歐拉公式。22nm 推論：設G是一個有n個點m條邊，虧格為的連通圖，則：11(1),(2 )62mn11( 2 ),(2 )42Gmn若無 三 角 形 ， 則 ：第23頁/共32頁 證明 (3): 因為G的每個面是三角形，所以每條邊是兩個面的公共邊，得：3=2m。于是由定理4得：(3),=3(2+2 )Gmn若每個面是三角形，則：(4),=2(2+2 )Gmn若每個面是四邊形，則：=3(2+2 )mn 對于完全圖的虧格曾經是一個長期的，有趣的，困難的

13、和成功的努力。1890年希伍德提出如下猜想：(3)(4)()(*)12nnnK第24頁/共32頁 希伍德由推論(1)證明了：(3)(4)()12nnnK 同時希伍德也證明了(K7)=1. 1891年，赫夫曼對n= 8-12 進行了證明； 1952年，林格爾對n= 13 進行了證明； 記階數(shù)n=12s+r 1954年，林格爾對r= 5 進行了證明； 1961-65年，林格爾對r= 7、10、3 進行了證明；第25頁/共32頁 1961-65年，楊斯、臺里等對r= 4、0、1、9、6 進行了證明； 1967-68年，林格爾、楊斯對r= 2、8、11進行了證明； 1968年后，法國蒙特派列爾大學文學教授杰恩對n=18、20、23進行了證明. 對于完全雙圖，結果由林格爾獨立得到。 定理5 設m, n是正整數(shù)，則：(3)(4)()12nnnK,(3)(2)()4m nmnK第26頁/共32頁 2、圖的厚度 定義5 若圖G的k個可平面子圖的并等于G，則稱k的最小值為G的厚度，記為 ( )G定理6 (1)若 ,則： 4(mod6)9nn或7()6nnK(2),()2(2)m nmnKmn(3) 對任意的單圖G=(n, m),有：36mn 3、圖的糙度第27頁/共32頁 定義6 圖G中邊不相交的不可平面子圖的最多數(shù)目稱為G的糙度，記為： ( )G 定理7 完全圖