圖論ppt22電子科大楊春

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)容(一一)、平面圖的判定、平面圖的判定(二二)、涉及平面性的不變量、涉及平面性的不變量平面圖的判定與涉及平面性的不變量平面圖的判定與涉及平面性的不變量 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、3要解決的問題是：給出判定一個圖是否是可平面圖的充要解決的問題是：給出判定一個圖是否是可平面圖的充分必要條件。分必要條件。(一一)、平面圖的判定、平面圖的判定 最早給出圖的平面性判定充要條件的是波蘭數(shù)學(xué)家最早給出圖的平面性判定充要條件的是波蘭數(shù)學(xué)家?guī)炖兴够鶐炖兴够?30年代給出年代給出)。后來，美國數(shù)學(xué)家惠特尼，。后來，美國數(shù)學(xué)家惠特尼，加拿大數(shù)學(xué)家托特，我國數(shù)學(xué)家吳文俊等都給出了不同加拿大數(shù)學(xué)家托特，我國數(shù)學(xué)家吳文俊等都給出了不同的充要條件。的充要條件。 我們主要介紹波蘭數(shù)學(xué)家?guī)炖兴够慕Y(jié)果。我們主要介紹波蘭數(shù)學(xué)家?guī)炖兴够慕Y(jié)果。 0.8 1 0.6 0.4 0.2 0 x t 0

3、0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 1、相關(guān)概念、相關(guān)概念 定義定義1 在圖在圖G的邊上插入一個的邊上插入一個2度頂點，使一條邊分度頂點，使一條邊分成兩條邊，稱將圖在成兩條邊，稱將圖在2度頂點內(nèi)擴充；去掉一個圖的度頂點內(nèi)擴充；去掉一個圖的2度度頂點，使關(guān)聯(lián)它們的兩條邊合并成一條邊，稱將圖頂點，使關(guān)聯(lián)它們的兩條邊合并成一條邊，稱將圖G在在2度頂點內(nèi)收縮。度頂點內(nèi)收縮。 在在2度頂點內(nèi)收縮度頂點內(nèi)收縮在在2度頂點內(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 5 定義定義2 兩個圖兩個圖G1與與

4、G2說是同胚的，如果說是同胚的，如果 ，或，或者通過反復(fù)在者通過反復(fù)在2度頂點內(nèi)擴充和收縮后能夠變成一對同度頂點內(nèi)擴充和收縮后能夠變成一對同構(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 6 定理定理1 (庫拉托斯基定理庫拉托斯基定理) 圖圖G是可平面的，當(dāng)且僅當(dāng)是可平面的，當(dāng)且僅當(dāng)它不含它不含K5或或K3,3同胚的子圖。同胚的子圖。 例例1 求證：下面兩圖均是非

5、平面圖。求證：下面兩圖均是非平面圖。圖圖 G G1 1圖圖 G G2 2 證明：對于證明：對于G1來說，按來說，按G1在在2度頂點內(nèi)收縮后，可得度頂點內(nèi)收縮后，可得到到K5。所以，由庫拉托斯基定理知。所以，由庫拉托斯基定理知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 7 對于對于G2來說，先取如下子圖來說，先取如下子圖 G G2 2的一個子圖的一個子圖 對上面子圖，按對上面子圖，按2度頂點收縮得與之同胚子圖度頂點收縮得與之同胚子圖K3,3:K3,3 所以，所以，G2是非可平面圖。是非可平面圖。圖圖

6、 G G2 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 8 例例2 確定下圖是否是可平面圖。確定下圖是否是可平面圖。u1u2v1v2y1y2x1x2w1w2 分析：我們根據(jù)圖的結(jié)構(gòu)形式，懷疑該圖是非可平分析：我們根據(jù)圖的結(jié)構(gòu)形式，懷疑該圖是非可平面圖。但我們必須找到證據(jù)！面圖。但我們必須找到證據(jù)！ 當(dāng)然我們可能考慮是否當(dāng)然我們可能考慮是否m3n-6。遺憾的是該圖不滿。遺憾的是該圖不滿足這個不等式！足這個不等式！ 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 9 u1

7、u2v1v2y1y2x1x2w1w2 所以，我們要在該圖中尋找一個與所以，我們要在該圖中尋找一個與k5或或K3,3同胚的子同胚的子圖！圖！ 由于該圖的最大度為由于該圖的最大度為4的頂點才的頂點才4個，所以，不存在與個，所以，不存在與K5同胚的子圖。因此，只有尋找與同胚的子圖。因此，只有尋找與K3,3同胚的子圖！同胚的子圖！ 解：取解：取G中紅色邊的一個導(dǎo)出子圖：中紅色邊的一個導(dǎo)出子圖： 也就是得到也就是得到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 上圖顯然和上圖顯然和K3,3

8、同胚。由庫拉托斯基定理知，同胚。由庫拉托斯基定理知，G是非可是非可平面的。平面的。u1u2v1v2y1y2x1x2w1w2 注：注： (1) 庫拉托斯基定理可以等價敘述為：庫拉托斯基定理可以等價敘述為： 庫拉托斯基定理：圖庫拉托斯基定理：圖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 11 (2) 庫拉托斯基庫拉托斯基 (1896-1980) 波蘭數(shù)學(xué)家。波蘭數(shù)學(xué)家。1913年開始年開始在蘇格蘭格拉斯哥大學(xué)學(xué)習(xí)工程學(xué)，在蘇格蘭格拉斯哥

9、大學(xué)學(xué)習(xí)工程學(xué)，1915年回到波蘭發(fā)沙年回到波蘭發(fā)沙大學(xué)轉(zhuǎn)學(xué)數(shù)學(xué)，主攻拓撲學(xué)。大學(xué)轉(zhuǎn)學(xué)數(shù)學(xué)，主攻拓撲學(xué)。1921年獲博士學(xué)位。年獲博士學(xué)位。1930年年在利沃夫大學(xué)作數(shù)學(xué)教授期間，發(fā)現(xiàn)并證明了圖論中的庫在利沃夫大學(xué)作數(shù)學(xué)教授期間，發(fā)現(xiàn)并證明了圖論中的庫拉托斯基定理。拉托斯基定理。1939年后到發(fā)沙大學(xué)做數(shù)學(xué)教授。他的一年后到發(fā)沙大學(xué)做數(shù)學(xué)教授。他的一生主要研究拓撲學(xué)與集合論。生主要研究拓撲學(xué)與集合論。 庫拉托斯基定理：圖庫拉托斯基定理：圖G是非可平面的，當(dāng)且僅當(dāng)它含是非可平面的，當(dāng)且僅當(dāng)它含有有K5或或K3,3同胚的子圖。同胚的子圖。 定義定義2 給定圖給定圖G, 去掉去掉G中的環(huán)，用單邊代替

10、平行邊而中的環(huán)，用單邊代替平行邊而得到的圖稱為得到的圖稱為G的基礎(chǔ)簡單圖。的基礎(chǔ)簡單圖。 庫拉托斯基于庫拉托斯基于1954年率波蘭數(shù)學(xué)家代表團對我國進行年率波蘭數(shù)學(xué)家代表團對我國進行了學(xué)術(shù)訪問，還送給了華羅庚一些波蘭數(shù)學(xué)家寫的數(shù)論函了學(xué)術(shù)訪問，還送給了華羅庚一些波蘭數(shù)學(xué)家寫的數(shù)論函數(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 12 定理定理2 (1) 圖圖G是可平面的，當(dāng)且僅當(dāng)它的基礎(chǔ)簡單圖是可平面的，當(dāng)且僅當(dāng)它的基礎(chǔ)簡單圖是可平面的；是可平面的； (2) 圖圖G是可平面圖當(dāng)且僅當(dāng)是可平面圖當(dāng)且僅當(dāng)G的每個塊是可平

11、面圖。的每個塊是可平面圖。 證明：證明： (1) 由平面圖的定義，該命題顯然成立。由平面圖的定義，該命題顯然成立。 (2) 必要性顯然。下面證明充分性。必要性顯然。下面證明充分性。 不失一般性，假設(shè)不失一般性，假設(shè)G連通。我們對連通。我們對G的塊數(shù)的塊數(shù)n作數(shù)學(xué)歸作數(shù)學(xué)歸納證明。納證明。 當(dāng)當(dāng)n=1時，由條件，結(jié)論顯然成立；時，由條件，結(jié)論顯然成立； 設(shè)當(dāng)設(shè)當(dāng)nk 時，若時，若G的每個塊是可平面的，有的每個塊是可平面的，有G是可平是可平面的。下面考慮面的。下面考慮n=k時的情形。時的情形。 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

12、n 13 設(shè)點設(shè)點v是是G的割點，則按照的割點，則按照v，G可以分成兩個邊不重可以分成兩個邊不重子圖子圖G1與與G2, 即即G=G1GG2 2, ,且且G1G2=v。vG2G1 按歸納假設(shè)，按歸納假設(shè)，G1與與G2都是可平面圖。取都是可平面圖。取G1與與G2的平的平面嵌入滿足點面嵌入滿足點v都在外部面邊界上，則把它們在點都在外部面邊界上，則把它們在點v處對處對接后，將得到接后，將得到G的平面嵌入。即證的平面嵌入。即證G是可平面圖。是可平面圖。 關(guān)于圖的可平面性刻畫，德國數(shù)學(xué)家瓦格納關(guān)于圖的可平面性刻畫，德國數(shù)學(xué)家瓦格納(Wangner)在在1937年得到了一個定理。年得到了一個定理。 0.8

13、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 定義定義3 設(shè)設(shè)uv是簡單圖是簡單圖G的一條邊。去掉該邊，重合其的一條邊。去掉該邊，重合其端點，在刪去由此產(chǎn)生的環(huán)和平行邊。這一過程稱為圖端點，在刪去由此產(chǎn)生的環(huán)和平行邊。這一過程稱為圖G的初等收縮或圖的邊收縮運算。的初等收縮或圖的邊收縮運算。 稱稱G可收縮到可收縮到H,是指對是指對G通過一系列邊收縮后可得到通過一系列邊收縮后可得到圖圖H。 定理定理2 (瓦格納定理瓦格納定理)：簡單圖：簡單圖G是可平面圖當(dāng)且僅當(dāng)它是可平面圖當(dāng)且僅當(dāng)它不含有可收縮到不含有可收縮到K5或或K3,3的子圖。的子

14、圖。 注：這是瓦格納注：這是瓦格納1937年在科隆大學(xué)博士畢業(yè)當(dāng)年提出年在科隆大學(xué)博士畢業(yè)當(dā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 15 例例3 求證彼得森圖是非可平面圖。求證彼得森圖是非可平面圖。 證明：很明顯，彼得森圖通過一些列邊收縮運算后得證明：很明顯，彼得森圖通過一些列邊收縮運算后得到到K5。由瓦格納定理得證。由瓦格納定理得證。 定理定理3 至少有至少有9個頂點的簡單可平面圖的補圖是不可平個頂點的簡單可平面圖的補圖是不可平面的，而面的，而9是這個數(shù)目中的最小的一個。是這個

15、數(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 16 注：該定理是由數(shù)學(xué)家巴特爾、哈拉里和科達馬首先注：該定理是由數(shù)學(xué)家巴特爾、哈拉里和科達馬首先得到。然后由托特得到。然后由托特(1963)給出了一個不太笨拙的證明，他給出了一個不太笨拙的證明，他采用枚舉法進行驗證。還不知道有簡潔證明，也沒有得采用枚舉法進行驗證。還不知道有簡潔證明，也沒有得到推理方法證明。到推理方法證明。 例例4 找出一個找出一個8個頂點的可平面圖，使其補圖也是可平個頂點的可平面圖，使其補圖也是可平面的。面的。76543218G76543218G

16、的補的補 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 例例5 設(shè)設(shè)G是一個簡單圖，若頂點數(shù)是一個簡單圖，若頂點數(shù)n11,則則G與與G的補的補圖中，至少有一個是不可平面圖圖中，至少有一個是不可平面圖 (要求用推理方法要求用推理方法). 證明：設(shè)證明：設(shè)G是一個是一個n階可平面圖，則：階可平面圖，則：()36m Gn 所以：所以：(1)()()()(36)2nn nm 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

17、 1.5 2 1 0.5 0 0.5 1 n 18 令令: 則：則： 所以，所以， 當(dāng)當(dāng)n6.5時，時，f(n)單調(diào)上升。而當(dāng)單調(diào)上升。而當(dāng)n=11時：時：21( )(1324)2f nnn13( )2fnn(11)0f 所以，所以， 當(dāng)當(dāng)n11時，有：時，有：()(36)m Gn 即證明了簡單可平面圖即證明了簡單可平面圖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 19 例例6 設(shè)設(shè)Gi是一個有是一個有ni個點，個點，mi條邊的圖，條邊的圖，i=1,2。證明：。證明：若若G1與與G2同胚

18、，則：同胚，則： 證明：設(shè)證明：設(shè)G1經(jīng)過經(jīng)過p1次次2度頂點擴充，度頂點擴充，p2次次2度頂點收縮度頂點收縮得到得到H1, G2經(jīng)過經(jīng)過q1次次2度頂點擴充，度頂點擴充，q2次次2度頂點收縮得到度頂點收縮得到H2, 使得：使得：1221nmnm 又設(shè)又設(shè)H1與與H2的頂點數(shù)分別為的頂點數(shù)分別為n1*和和n2*,邊數(shù)分別為邊數(shù)分別為m1*與與m2*。那么：。那么：12HH1112*nnPP1112*mmPP2212*nnqq2212*mmqq 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 所以：所以： 而由而由 得：得：12H

19、H12121212*nmnmPPqq1212*,*mmnn21211212*nmnmPPqq 所以：所以：1221nmnm(二二)、涉及平面性的不變量、涉及平面性的不變量 我們將要討論的問題是：如何刻畫一個非可平面圖與平我們將要討論的問題是：如何刻畫一個非可平面圖與平面圖之間的差距。只作簡單介紹。面圖之間的差距。只作簡單介紹。 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 21 環(huán)柄：邊交叉處建立的環(huán)柄：邊交叉處建立的“立交橋立交橋”。通過它，讓一條。通過它，讓一條邊經(jīng)過邊經(jīng)過 “橋下橋下”，而另一條邊經(jīng)過，

20、而另一條邊經(jīng)過“橋上橋上”，從而把兩，從而把兩條邊在交叉處分開。條邊在交叉處分開。環(huán)柄示意圖環(huán)柄示意圖 定義定義4 若通過加上若通過加上k個環(huán)柄可將圖個環(huán)柄可將圖G嵌入到球面，則嵌入到球面，則k的最小數(shù)目，稱為的最小數(shù)目，稱為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 22 定理定理4 對于一個虧格為對于一個虧格為，有有n個頂點，個頂點，m條邊和條邊和個面?zhèn)€面的多面體，有：的多面體，有： 因多面體對應(yīng)一個連通圖，所以上面恒等式稱為一般因多面體對應(yīng)一個連通圖，所以上面恒等式稱為一般連通圖

21、的歐拉公式。連通圖的歐拉公式。22nm 推論：設(shè)推論：設(shè)G是一個有是一個有n個點個點m條邊，虧格為條邊，虧格為的連通圖，的連通圖，則：則：11(1),(2 )62mn11( 2 ),(2 )42Gmn若無 三 角 形 ， 則 ： 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 (3),=3(2+2 )Gmn若每個面是三角形，則：(4),=2(2+2 )Gmn若每個面是四邊形，則： 對于完全圖的虧格曾經(jīng)是一個長期的，有趣的，困難對于完全圖的虧格曾經(jīng)是一個長期的，有趣的，困難的和成功的努力。的和成功的努力。1890年希伍德提出如下猜

22、想：年希伍德提出如下猜想：(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 24 希伍德由推論希伍德由推論(1)證明了：證明了：(3)(4)()12nnnK 同時希伍德也證明了同時希伍德也證明了(K(K7 7)=1.)=1. 1891年，赫夫曼對年，赫夫曼對n= 8-12 進行了證明；進行了證明； 1952年，林格爾對年，林格爾對n= 13 進行了證明；進行了證明； 記階數(shù)記階數(shù)n=12s+r 1954年，林格爾對年，林格爾對r= 5 進行了證明；進行了證明； 1961-65年，林格爾對年，林格爾對r

23、= 7、10、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 25 1961-65年，楊斯、臺里等對年，楊斯、臺里等對r= 4、0、1、9、6 進行進行了證明；了證明； 1967-68年，林格爾、楊斯對年，林格爾、楊斯對r= 2、8、11進行了證明；進行了證明； 1968年后，法國蒙特派列爾大學(xué)文學(xué)教授杰恩對年后，法國蒙特派列爾大學(xué)文學(xué)教授杰恩對n=18、20、23進行了證明進行了證明. 對于完全雙圖，結(jié)果由林格爾獨立得到。對于完全雙圖，結(jié)果由林格爾獨立得到。 定理定理5 設(shè)設(shè)m, n是正整數(shù)，則：是正整數(shù)，則：(3)(4)()12nnnK,(3)(2)()4m nmnK 0.8 1 0.