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

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 圖論-平面圖的判定與涉及平面性的不變量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 圖論-平面圖的判定與涉及平面性的不變量2本次課主要內容本次課主要內容(一一)、平面圖的判定、平面圖的判定(二二)、涉及平面性的不變量、涉及平面性的不變量平面圖的判定與涉及平面性的不變量平面圖的判定與涉及平面性的不變量 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5

2、2 1 0.5 0 0.5 1 n 圖論-平面圖的判定與涉及平面性的不變量3 這次課要解決的問題是：給出判定一個圖是否是可這次課要解決的問題是：給出判定一個圖是否是可平面圖的充分必要條件。平面圖的充分必要條件。(一一)、平面圖的判定、平面圖的判定 在本章第一次課中，我們已經(jīng)明確：對于在本章第一次課中，我們已經(jīng)明確：對于3階以上的階以上的具有具有m條邊的圖條邊的圖G來說，如果來說，如果G滿足如下條件之一：滿足如下條件之一： (1)m3n-6; (2) K5是是G的一個子圖；的一個子圖；(3) K3,3是是G的一個的一個子圖，那么，子圖，那么，G是非可平面圖。是非可平面圖。 但上面的條件僅為但上面

3、的條件僅為G是非可平面圖的充分條件。是非可平面圖的充分條件。 最早給出圖的平面性判定充要條件的是波蘭數(shù)學家最早給出圖的平面性判定充要條件的是波蘭數(shù)學家?guī)炖兴够鶐炖兴够?30年代給出年代給出)。后來，美國數(shù)學家惠特尼，。后來，美國數(shù)學家惠特尼，加拿大數(shù)學家托特，我國數(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 圖論-平面圖的判定與涉及平面性的不變量4 所以，我們稱所以，我們稱K5與與K3,3為庫拉托斯基圖。為庫拉托斯基圖。 我們主要

4、介紹波蘭數(shù)學家?guī)炖兴够慕Y果。我們主要介紹波蘭數(shù)學家?guī)炖兴够慕Y果。 庫拉托斯基定理主要基于庫拉托斯基定理主要基于K5和和K3,3是非可平面圖這一是非可平面圖這一事實而提出的平面性判定方法。事實而提出的平面性判定方法。 一個自然的猜測是：一個自然的猜測是：G是可平面圖的充分必要條件是是可平面圖的充分必要條件是G不含子圖不含子圖K5和和K3,3。 上面命題必要性顯然成立！但充分性能成立嗎？上面命題必要性顯然成立！但充分性能成立嗎？ 十分遺憾！下面例子給出了回答：十分遺憾！下面例子給出了回答：NO! 下面的圖下面的圖G是一個點數(shù)為是一個點數(shù)為5，邊數(shù)為，邊數(shù)為9的極大平面圖。的極大平面圖?？紤]

5、考慮 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 圖論-平面圖的判定與涉及平面性的不變量5 注：注：F由由G的的3個拷貝組成，分別是個拷貝組成，分別是G1,G2,G3。三個拷。三個拷貝中的邊沒有畫出。圖中虛線不是對應的貝中的邊沒有畫出。圖中虛線不是對應的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 圖論-平面圖的判定與涉及平面性的不變量6 可以證明：可以證明：

6、F中不含中不含K5和和K3,3，且，且F是非可平面圖。是非可平面圖。 盡管我們的直覺猜測錯了，但庫拉托斯基還是基于盡管我們的直覺猜測錯了，但庫拉托斯基還是基于K5與與K3,3得到了圖的平面性判據(jù)。得到了圖的平面性判據(jù)。 1、相關概念、相關概念 定義定義1 在圖在圖G的邊上插入一個的邊上插入一個2度頂點，使一條邊分度頂點，使一條邊分成兩條邊，稱將圖在成兩條邊，稱將圖在2度頂點內擴充；去掉一個圖的度頂點內擴充；去掉一個圖的2度度頂點，使關聯(lián)它們的兩條邊合并成一條邊，稱將圖頂點，使關聯(lián)它們的兩條邊合并成一條邊，稱將圖G在在2度頂點內收縮。度頂點內收縮。 在在2度頂點內收縮度頂點內收縮在在2度頂點內擴

7、充度頂點內擴充 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 定義定義2 兩個圖兩個圖G1與與G2說是同胚的，如果說是同胚的，如果 ，或，或者通過反復在者通過反復在2度頂點內擴充和收縮后能夠變成一對同度頂點內擴充和收縮后能夠變成一對同構的圖。構的圖。 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

8、1 n 圖論-平面圖的判定與涉及平面性的不變量8 定理定理1 (庫拉托斯基定理庫拉托斯基定理) 圖圖G是可平面的，當且僅當是可平面的，當且僅當它不含它不含K5或或K3,3同胚的子圖。同胚的子圖。 例例1 求證：下面兩圖均是非平面圖。求證：下面兩圖均是非平面圖。圖圖 G G1 1圖圖 G G2 2 證明：對于證明：對于G1來說，按來說，按G1在在2度頂點內收縮后，可得度頂點內收縮后，可得到到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 圖論-平面

9、圖的判定與涉及平面性的不變量9 對于對于G2來說，先取如下子圖來說，先取如下子圖 G G2 2的一個子圖的一個子圖 對上面子圖，按對上面子圖，按2度頂點收縮得與之同胚子圖度頂點收縮得與之同胚子圖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 圖論-平面圖的判定與涉及平面性的不變量10 例例2 確定下圖是否是可平面圖。確定下圖是否是可平面圖。u1u2v1v2y1y2x1x2w1w2 分析：我們根據(jù)圖的結構形式，懷疑該圖是非可平分析：我們根據(jù)圖的結構形式，懷疑該圖是非可平面

10、圖。但我們必須找到證據(jù)！面圖。但我們必須找到證據(jù)！ 當然我們可能考慮是否當然我們可能考慮是否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 圖論-平面圖的判定與涉及平面性的不變量11 u1u2v1v2y1y2x1x2w1w2 所以，我們要在該圖中尋找一個與所以，我們要在該圖中尋找一個與k5或或K3,3同胚的子同胚的子圖！圖！ 由于該圖的最大度為由于該圖的最大度為4的頂點才的頂點才4個，所以，不存在與個，所以，不存在與K5同胚的子圖。因此，只有尋找與同胚的子圖。

11、因此，只有尋找與K3,3同胚的子圖！同胚的子圖！ 解：取解：取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 圖論-平面圖的判定與涉及平面性的不變量12 上圖顯然和上圖顯然和K3,3同胚。由庫拉托斯基定理知，同胚。由庫拉托斯基定理知，G是非可是非可平面的。平面的。u1u2v1v2y1y2x1x2w1w2 注：注： (1) 庫拉托斯基定理可以等價敘述為：庫拉托斯基定理可以等價敘述為： 庫拉托斯基定理：圖庫拉托斯基定理：

12、圖G是非可平面的，當且僅當它含有是非可平面的，當且僅當它含有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 圖論-平面圖的判定與涉及平面性的不變量13 (2) 庫拉托斯基庫拉托斯基 (1896-1980) 波蘭數(shù)學家。波蘭數(shù)學家。1913年開始年開始在蘇格蘭格拉斯哥大學學習工程學，在蘇格蘭格拉斯哥大學學習工程學，1915年回到波蘭發(fā)沙年回到波蘭發(fā)沙大學轉學數(shù)學，主攻拓撲學。大學轉學數(shù)學，主攻拓撲學。1921年獲博士學位。年獲博士學位。1930年年在利沃夫大學作數(shù)學教授期間，發(fā)現(xiàn)并證明了圖論中的

13、庫在利沃夫大學作數(shù)學教授期間，發(fā)現(xiàn)并證明了圖論中的庫拉托斯基定理。拉托斯基定理。1939年后到發(fā)沙大學做數(shù)學教授。他的一年后到發(fā)沙大學做數(shù)學教授。他的一生主要研究拓撲學與集合論。生主要研究拓撲學與集合論。 庫拉托斯基定理：圖庫拉托斯基定理：圖G是非可平面的，當且僅當它含是非可平面的，當且僅當它含有有K5或或K3,3同胚的子圖。同胚的子圖。 定義定義2 給定圖給定圖G, 去掉去掉G中的環(huán)，用單邊代替平行邊而中的環(huán)，用單邊代替平行邊而得到的圖稱為得到的圖稱為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 圖

14、論-平面圖的判定與涉及平面性的不變量14 定理定理2 (1) 圖圖G是可平面的，當且僅當它的基礎簡單圖是可平面的，當且僅當它的基礎簡單圖是可平面的；是可平面的； (2) 圖圖G是可平面圖當且僅當是可平面圖當且僅當G的每個塊是可平面圖。的每個塊是可平面圖。 證明：證明： (1) 由平面圖的定義，該命題顯然成立。由平面圖的定義，該命題顯然成立。 (2) 必要性顯然。下面證明充分性。必要性顯然。下面證明充分性。 不失一般性，假設不失一般性，假設G連通。我們對連通。我們對G的塊數(shù)的塊數(shù)n作數(shù)學歸作數(shù)學歸納證明。納證明。 當當n=1時，由條件，結論顯然成立；時，由條件，結論顯然成立； 設當設當nk 時，

15、若時，若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 n 圖論-平面圖的判定與涉及平面性的不變量15 設點設點v是是G的割點，則按照的割點，則按照v，G可以分成兩個邊不重可以分成兩個邊不重子圖子圖G1與與G2, 即即G=G1GG2 2, ,且且G1G2=v。vG2G1 按歸納假設，按歸納假設，G1與與G2都是可平面圖。取都是可平面圖。取G1與與G2的平的平面嵌入滿足點面嵌入滿足點v都在外部面邊界上，則把它們在點都在外部面邊

16、界上，則把它們在點v處對處對接后，將得到接后，將得到G的平面嵌入。即證的平面嵌入。即證G是可平面圖。是可平面圖。 關于圖的可平面性刻畫，數(shù)學家瓦格納關于圖的可平面性刻畫，數(shù)學家瓦格納(Wangner)在在1937年得到了一個定理。年得到了一個定理。 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 定義定義3 設設uv是簡單圖是簡單圖G的一條邊。去掉該邊，重合其的一條邊。去掉該邊，重合其端點，在刪去由此產生的環(huán)和平行邊。這一過程稱為圖端點，在刪去由此產生的環(huán)和平行邊。這一過程稱為圖G的初等收縮

17、或圖的邊收縮運算。的初等收縮或圖的邊收縮運算。 稱稱G可收縮到可收縮到H,是指對是指對G通過一系列邊收縮后可得到通過一系列邊收縮后可得到圖圖H。 定理定理2 (瓦格納定理瓦格納定理)：簡單圖：簡單圖G是可平面圖當且僅當它是可平面圖當且僅當它不含有可收縮到不含有可收縮到K5或或K3,3的子圖。的子圖。 注：這是瓦格納注：這是瓦格納1937年在科隆大學博士畢業(yè)當年提出年在科隆大學博士畢業(yè)當年提出并證明過的一個定理。并證明過的一個定理。 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 例例3 求證

18、彼得森圖是非可平面圖。求證彼得森圖是非可平面圖。 證明：很明顯，彼得森圖通過一些列邊收縮運算后得證明：很明顯，彼得森圖通過一些列邊收縮運算后得到到K5。由瓦格納定理得證。由瓦格納定理得證。 定理定理3 至少有至少有9個頂點的簡單可平面圖的補圖是不可平個頂點的簡單可平面圖的補圖是不可平面的，而面的，而9是這個數(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 圖論-平面圖的判定與涉及平面性的不變量18 注：該定理是由數(shù)學家巴特爾、哈拉里和科達馬首先注：該定理是由數(shù)學家巴特爾、哈拉里和科達馬首先

19、得到。然后由托特得到。然后由托特(1963)給出了一個不太笨拙的證明，他給出了一個不太笨拙的證明，他采用枚舉法進行驗證。還不知道有簡潔證明，也沒有得采用枚舉法進行驗證。還不知道有簡潔證明，也沒有得到推理方法證明。到推理方法證明。 例例4 找出一個找出一個8個頂點的可平面圖，使其補圖也是可平個頂點的可平面圖，使其補圖也是可平面的。面的。76543218G76543218G的補的補 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 例例5 設設G是一個簡單圖，若頂點數(shù)是一個簡單圖，若頂點數(shù)n11,

20、則則G與與G的補的補圖中，至少有一個是不可平面圖圖中，至少有一個是不可平面圖 (要求用推理方法要求用推理方法). 證明：設證明：設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 1.5 2 1 0.5 0 0.5 1 n 圖論-平面圖的判定與涉及平面性的不變量20 令令: 則：則： 所以，所以， 當當n6.5時，時，f(n)單調上升。而當單調上升。而當n=11時：

21、時：21( )(1324)2f nnn13( )2fnn(11)0f 所以，所以， 當當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 圖論-平面圖的判定與涉及平面性的不變量21 例例6 設設Gi是一個有是一個有ni個點，個點，mi條邊的圖，條邊的圖，i=1,2。證明：。證明：若若G1與與G2同胚，則：同胚，則： 證明：設證明：設G1經(jīng)過經(jīng)過p1次次2度頂點擴充，度頂點擴充，p2次次2度頂點收縮度頂點收縮得到

22、得到H1, G2經(jīng)過經(jīng)過q1次次2度頂點擴充，度頂點擴充，q2次次2度頂點收縮得到度頂點收縮得到H2, 使得：使得：1221nmnm 又設又設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 圖論-平面圖的判定與涉及平面性的不變量22 所以：所以： 而由而由 得：得：12HH12121212*nmnmPPqq1212*,*mmnn21211212*

23、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 圖論-平面圖的判定與涉及平面性的不變量23 環(huán)柄：邊交叉處建立的環(huán)柄：邊交叉處建立的“立交橋立交橋”。通過它，讓一條。通過它，讓一條邊經(jīng)過邊經(jīng)過 “橋下橋下”，而另一條邊經(jīng)過，而另一條邊經(jīng)過“橋上橋上”，從而把兩，

24、從而把兩條邊在交叉處分開。條邊在交叉處分開。環(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 圖論-平面圖的判定與涉及平面性的不變量24 定理定理4 對于一個虧格為對于一個虧格為，有有n個頂點，個頂點，m條邊和條邊和個面?zhèn)€面的多面體，有：的多面體，有： 因多面體對應一個連通圖，所以上面恒等式稱為一般因多面體對應一個連通圖，所以上面恒等式稱為一般連通圖

25、的歐拉公式。連通圖的歐拉公式。22nm 推論：設推論：設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 圖論-平面圖的判定與涉及平面性的不變量25 證明證明 (3): 因為因為G的每個面是三角形，所以每條邊是兩的每個面是三角形，所以每條邊是兩個面的公共邊，得：個面的公共邊，得：3=2m=2m。于是由定理。于是由定理4 4得：得：(3),=3(2+2 )Gmn若每個

26、面是三角形，則：(4),=2(2+2 )Gmn若每個面是四邊形，則：=3(2+2 )mn 對于完全圖的虧格曾經(jīng)是一個長期的，有趣的，困難對于完全圖的虧格曾經(jī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 圖論-平面圖的判定與涉及平面性的不變量26 希伍德由推論希伍德由推論(1)證明了：證明了：(3)(4)()12nnnK 同時希伍德也證明了同時希伍德也證明了(K(K7 7)=1.)=1. 1

27、891年，赫夫曼對年，赫夫曼對n= 8-12 進行了證明；進行了證明； 1952年，林格爾對年，林格爾對n= 13 進行了證明；進行了證明； 記階數(shù)記階數(shù)n=12s+r 1954年，林格爾對年，林格爾對r= 5 進行了證明；進行了證明； 1961-65年，林格爾對年，林格爾對r= 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 圖論-平面圖的判定與涉及平面性的不變量27 1961-65年，楊斯、臺里等對年，楊斯、臺里等對r= 4、0、1、9、6 進行進行了證明；了證明； 1967-68年，林格爾、楊斯對年，林格爾、楊斯對r= 2、8、11進行了證明；進行了證明； 1968年后，法國蒙特派列爾大學文學教授杰恩對年后，法國蒙特派列爾大學文學教授杰恩對n=18、20、23進行了證明進行了證明. 對于完全雙圖，結果由林格爾獨立得到。對于完全雙圖，結果由林格爾獨立得到。 定理定理5 設設m, n是正整