1、1第第1111章章 特殊圖特殊圖 偶圖偶圖3平面圖平面圖4歐拉圖歐拉圖1集合的表示方法集合的表示方法2哈密頓圖哈密頓圖2211.2 11.2 歐拉圖歐拉圖 11.2.1 11.2.1 歐拉圖的引入與定義歐拉圖的引入與定義A AB BC CD Db b5 5b b2 2b b1 1b b3 3b b4 4b b7 7b b6 6B BC CA AD Db b6 6b b2 2b b5 5b b7 7b b4 4b b1 1b b3 33定義定義11.2.111.2.1設(shè)設(shè)G G是是無孤立結(jié)點的圖無孤立結(jié)點的圖，若存在一條通路，若存在一條通路( (回路回路) )，經(jīng)過圖中經(jīng)過圖中每條邊每條邊一次且

2、僅一次一次且僅一次，則稱此通路，則稱此通路( (回路回路) )為該圖的一條為該圖的一條歐拉通路歐拉通路( (回路回路)()(EulerianEulerian Entry/Circuit)Entry/Circuit)。具有。具有歐拉回路歐拉回路的圖稱為的圖稱為歐拉圖歐拉圖( (EulerianEulerian Graph) Graph)。 規(guī)定：規(guī)定：平凡圖為歐拉圖。平凡圖為歐拉圖。 以上定義既適合無向圖，又適合有向圖。以上定義既適合無向圖，又適合有向圖。 4歐拉通路和歐拉回路的特征歐拉通路和歐拉回路的特征 歐拉通路歐拉通路是經(jīng)過是經(jīng)過圖中所有邊圖中所有邊的通路中的通路中長度長度（指（指邊的數(shù)目

3、，無權(quán)圖）邊的數(shù)目，無權(quán)圖）最短的通路最短的通路，即為，即為通過圖中所通過圖中所有邊的簡單通路有邊的簡單通路； 歐拉回路歐拉回路是經(jīng)過是經(jīng)過圖中所有邊圖中所有邊的回路中的回路中長度最短長度最短（指邊的數(shù)目，無權(quán)圖）（指邊的數(shù)目，無權(quán)圖）的回路的回路，即為，即為通過圖中所通過圖中所有邊的簡單回路有邊的簡單回路。 如果僅用邊來描述，如果僅用邊來描述，歐拉通路和歐拉回路就是歐拉通路和歐拉回路就是圖中所有邊的一種全排列圖中所有邊的一種全排列。5例例11.2.111.2.1判斷下面的判斷下面的6 6個圖中，是否是歐拉圖？是否存在歐個圖中，是否是歐拉圖？是否存在歐拉通路？拉通路？ v v3 3v v1 1

4、v v2 2v v4 4(c)(c)v v3 3v v1 1v v2 2v v4 4(a)(a)v v3 3v v1 1v v2 2v v4 4(b)(b)v v3 3v v1 1v v2 2v v4 4(f)(f)v v3 3v v1 1v v2 2v v4 4(d)(d)v v3 3v v1 1v v2 2v v4 4(e)(e)歐拉圖歐拉圖 歐歐拉拉圖圖 不是歐拉圖，但不是歐拉圖，但存在歐拉通路存在歐拉通路 不存在歐不存在歐拉通路拉通路 不不存存在在歐歐拉拉通通路路 不是歐拉圖，但存在歐拉通路不是歐拉圖，但存在歐拉通路 611.2.2 11.2.2 歐拉圖的判定歐拉圖的判定- -無向圖無

5、向圖 定理定理11.2.111.2.1 無向圖無向圖G = G = 具有一條具有一條歐拉通歐拉通路路，當且僅當，當且僅當G G是連通的，且僅有零個或兩個奇度是連通的，且僅有零個或兩個奇度數(shù)結(jié)點。數(shù)結(jié)點。推論推論11.2.111.2.1 無向圖無向圖G = G = 具有一條具有一條歐拉回路歐拉回路，當且僅當當且僅當G G是連通的，并且所有結(jié)點的度數(shù)均為偶是連通的，并且所有結(jié)點的度數(shù)均為偶數(shù)。數(shù)。對圖中各結(jié)點度數(shù)的計算，就可知它是否存在歐拉對圖中各結(jié)點度數(shù)的計算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖；通路及歐拉回路，從而知道它是否為歐拉圖；711.2.2 11.2.2 歐拉圖

6、的判定歐拉圖的判定- -有向圖有向圖定理定理11.2.211.2.2 有向圖有向圖G G具有一條具有一條歐拉通路歐拉通路，當且僅當，當且僅當G G是連通的，且除了兩個結(jié)點以外，其余結(jié)點的入是連通的，且除了兩個結(jié)點以外，其余結(jié)點的入度等于出度，而這兩個例外的結(jié)點中，一個結(jié)點的度等于出度，而這兩個例外的結(jié)點中，一個結(jié)點的入度比出度大入度比出度大1 1，另一個結(jié)點的出度比入度大，另一個結(jié)點的出度比入度大1 1。推論推論11.2.211.2.2 有向圖有向圖G G具有一條具有一條歐拉回路歐拉回路，當且僅，當且僅當當G G是連通的，且所有結(jié)點的是連通的，且所有結(jié)點的入度等于出度入度等于出度。 對圖中各結(jié)

7、點出度與入度的計算，就可知它是否存對圖中各結(jié)點出度與入度的計算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖。在歐拉通路及歐拉回路，從而知道它是否為歐拉圖。8歐拉回路的尋找歐拉回路的尋找- -橋的定義橋的定義設(shè)設(shè)G = G = ，eEeE，如果，如果p(G-ep(G-e) )p(Gp(G) )稱稱e e為為G G的的橋橋(Bridge)(Bridge)或或割邊割邊(Cut edge)(Cut edge)。 顯然，顯然，所有的懸掛邊都是橋所有的懸掛邊都是橋。 其中其中p(G-ep(G-e) )是從是從G G中刪除中刪除e e后所得到圖的連通分后所得到圖的連通分支數(shù)。支數(shù)。 9歐拉回

8、路的尋找歐拉回路的尋找- -FleuryFleury算法算法算法算法11.2.111.2.1 求歐拉圖求歐拉圖G = G = 的歐拉回路的的歐拉回路的FleuryFleury算法：算法：（1 1）任?。┤稳 v0 0VV，令，令P P0 0 = v = v0 0，i = 0i = 0；（2 2）按下面的方法從）按下面的方法從E-eE-e1 1, e, e2 2, , , , e ei i 中選取中選取e ei+1i+1：na. ea. ei+1i+1與與v vi i相關(guān)聯(lián)；相關(guān)聯(lián)；nb. b. 除非無別的邊可選取，否則除非無別的邊可選取，否則e ei+1i+1不應(yīng)該為不應(yīng)該為G = G-eG

9、 = G-e1 1, e, e2 2, , , , e ei i 中中的橋的橋；（3 3）將邊）將邊e ei+1i+1加入通路加入通路P P0 0中，令中，令P P0 0 = = v v0 0e e1 1v v1 1e e2 2e ei iv vi ie ei+1i+1v vi+1i+1，i = i+1i = i+1；（4 4）如果）如果i = |E|i = |E|，結(jié)束，否則轉(zhuǎn)，結(jié)束，否則轉(zhuǎn)(2)(2)。10例例11.2.211.2.2用用FleuryFleury算法求歐拉算法求歐拉圖的一條歐拉回路。圖的一條歐拉回路。 v v1 1v v7 7v v5 5v v3 3v v2 2v v8 8

10、v v4 4e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e1010e e7 7e e8 8e e9 9e e1111e e1212v v6 6分析分析 求從求從v v1 1出發(fā)，按照出發(fā)，按照FleuryFleury算法，每次走一條邊，算法，每次走一條邊，在可能的情況下，不走橋。在可能的情況下，不走橋。例如，在得到例如，在得到P P7 7 = v = v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e4 4v v5 5e e5 5v v6 6e e6 6v v7 7e e7 7v v8 8時，時，G = G-eG = G-e1

11、 1, e, e2 2, , , , e e7 7 中的中的e e8 8是橋，因此下一步是橋，因此下一步選擇走選擇走e e9 9，而不要走，而不要走e e8 8。 解解 從從v v1 1出發(fā)的一條歐拉回路為：出發(fā)的一條歐拉回路為：P P1212 = v = v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e4 4v v5 5e e5 5v v6 6e e6 6v v7 7e e7 7v v8 8e e9 9v v2 2e e1010v v4 4e e1111v v6 6e e1212v v8 8e e8 8v v1 1 1111.2.4 11.2.4 歐拉圖

12、的應(yīng)用歐拉圖的應(yīng)用 1 1、一筆畫問題、一筆畫問題 所謂所謂“一筆畫問題一筆畫問題”就是畫一個圖形，筆不離就是畫一個圖形，筆不離紙，每條邊只畫一次而不許重復(fù)，畫完該圖。紙，每條邊只畫一次而不許重復(fù)，畫完該圖。 “ “一筆畫問題一筆畫問題”本質(zhì)上就是一個無向圖是否存本質(zhì)上就是一個無向圖是否存在歐拉通路在歐拉通路( (回路回路) )的問題。如果該圖為歐拉圖，則的問題。如果該圖為歐拉圖，則能夠一筆畫完該圖，并且筆又回到出發(fā)點；如果該能夠一筆畫完該圖，并且筆又回到出發(fā)點；如果該圖只存在歐拉通路，則能夠一筆畫完該圖，但筆回圖只存在歐拉通路，則能夠一筆畫完該圖，但筆回不到出發(fā)點；如果該圖中不存在歐拉通路，

13、則不能不到出發(fā)點；如果該圖中不存在歐拉通路，則不能一筆畫完該圖。一筆畫完該圖。12例例11.2.311.2.3圖中的三個圖能否一筆畫？為什么？圖中的三個圖能否一筆畫？為什么？ v v1 1v v2 2v v3 3v v4 4v v5 5(b)(b)v v1 1v v2 2v v3 3v v4 4(c)(c)v v1 1v v2 2v v3 3v v4 4v v5 5(a)(a)解解 因為圖因為圖(a)(a)和和(b)(b)中分別有中分別有0 0個和個和2 2個奇度數(shù)結(jié)點，個奇度數(shù)結(jié)點，所以它們分別是歐拉圖和存在歐拉通路，因此能夠所以它們分別是歐拉圖和存在歐拉通路，因此能夠一筆畫，并且在一筆畫，

14、并且在(a)(a)中筆能回到出發(fā)點，而中筆能回到出發(fā)點，而(b)(b)中筆中筆不能回到出發(fā)點。圖不能回到出發(fā)點。圖c c中有中有4 4個度數(shù)為個度數(shù)為3 3的結(jié)點，所的結(jié)點，所以不存在歐拉通路，因此不能一筆畫。以不存在歐拉通路，因此不能一筆畫。 1311.2.3 11.2.3 歐拉圖小節(jié)歐拉圖小節(jié) 1.1. 僅有歐拉通路而無歐拉回路的圖不是歐拉圖；僅有歐拉通路而無歐拉回路的圖不是歐拉圖；2.2. 圖中是否存在歐拉通路、歐拉回路圖的判定非圖中是否存在歐拉通路、歐拉回路圖的判定非常簡單，只需要數(shù)一下圖中結(jié)點的度數(shù)即可；常簡單，只需要數(shù)一下圖中結(jié)點的度數(shù)即可；3.3. 使用使用FleuryFleur

15、y算法求歐拉通路算法求歐拉通路( (回路回路) )時，每次走時，每次走一條邊，在可能的情況下，不走橋。一條邊，在可能的情況下，不走橋。 1411.3 11.3 哈密頓圖哈密頓圖 11.2.1 11.2.1 哈密頓的引入與定義哈密頓的引入與定義 1 12 23 34 45 56 67 720208 89 9101011111212131314141515161617171818191915哈密頓圖哈密頓圖定義定義11.3.111.3.1 經(jīng)過圖中經(jīng)過圖中每個每個結(jié)點結(jié)點一次且僅一次一次且僅一次的通的通路路( (回路回路) )稱為稱為哈密頓通路哈密頓通路( (回路回路)(Hamiltonian )

16、(Hamiltonian Entry/circuit)Entry/circuit)。存在。存在哈密頓回路哈密頓回路的圖稱為的圖稱為哈密頓哈密頓圖圖(Hamiltonian Graph)(Hamiltonian Graph)。 規(guī)定：規(guī)定：平凡圖為哈密頓圖平凡圖為哈密頓圖。 以上定義既適合無向圖，又適合有向圖。以上定義既適合無向圖，又適合有向圖。 16哈密頓通路和哈密頓回路的特征哈密頓通路和哈密頓回路的特征n哈密頓通路是經(jīng)過圖中所有結(jié)點的通路中哈密頓通路是經(jīng)過圖中所有結(jié)點的通路中長度（指邊的長度（指邊的數(shù)目，無權(quán)圖）數(shù)目，無權(quán)圖）最短的通路，即為通過圖中所有結(jié)點的最短的通路，即為通過圖中所有結(jié)點

17、的基本通路；基本通路；n哈密頓回路是經(jīng)過圖中所有結(jié)點的回路中長度最短哈密頓回路是經(jīng)過圖中所有結(jié)點的回路中長度最短（指（指邊的數(shù)目，無權(quán)圖）邊的數(shù)目，無權(quán)圖）的回路，即為通過圖中所有結(jié)點的的回路，即為通過圖中所有結(jié)點的基本回路?；净芈?。n如果我們僅用結(jié)點來描述的話哈密頓通路就是圖中所有如果我們僅用結(jié)點來描述的話哈密頓通路就是圖中所有結(jié)點的一種全排列結(jié)點的一種全排列n哈密頓回路就是圖中所有結(jié)點的一種全排列再加上該排哈密頓回路就是圖中所有結(jié)點的一種全排列再加上該排列中第一個結(jié)點的一種排列。列中第一個結(jié)點的一種排列。17例例11.3.111.3.1判斷下面的判斷下面的6 6個圖中，是否是哈密頓圖？是

18、否存在個圖中，是否是哈密頓圖？是否存在哈密頓通路？哈密頓通路？v v3 3v v1 1v v2 2v v4 4(a)(a)v v3 3v v1 1v v2 2v v4 4(d)(d)v v3 3v v1 1v v2 2v v4 4(b)(b)v v5 5v v6 6v v7 7v v2 2v v4 4v v1 1v v5 5(c)(c)v v3 3v v3 3v v1 1v v2 2v v4 4(e)(e)v v3 3v v1 1v v2 2v v4 4(f)(f)哈密哈密頓圖頓圖 不存不存在哈在哈密頓密頓通路通路 不是哈密不是哈密頓圖，但頓圖，但存在哈密存在哈密頓通路頓通路 哈密哈密頓圖頓圖

19、 不是哈密不是哈密頓圖，但頓圖，但存在哈密存在哈密頓通路頓通路 不存不存在哈在哈密頓密頓通路通路 1811.3.2 11.3.2 哈密頓圖的必要條件哈密頓圖的必要條件 定理定理11.3.111.3.1 設(shè)設(shè)無向圖無向圖G = G = 是是哈密頓圖哈密頓圖（存在哈密爾頓回路）（存在哈密爾頓回路），V V1 1是是V V的任意非空子集，的任意非空子集，則則p(G-Vp(G-V1 1) |V) |V1 1| |推論推論11.3.111.3.1設(shè)設(shè)無向圖無向圖G = G = 中存在中存在哈密頓通路哈密頓通路，則對則對V V的任意非空子集的任意非空子集V V1 1，都有，都有p(G-Vp(G-V1 1)

20、 |V) |V1 1| + 1 | + 1 定理定理11.3.111.3.1給出的是哈密頓圖的必要條件，而不給出的是哈密頓圖的必要條件，而不是充分條件。是充分條件。 其它的逆否命題非常有用：若存在其它的逆否命題非常有用：若存在V V的某個非空子的某個非空子集集V V1 1使得使得p(G-Vp(G-V1 1) )|V|V1 1| |，則，則G G不是哈密頓圖。不是哈密頓圖。 19例例11.3.211.3.2證明圖中不存在哈密頓回路。證明圖中不存在哈密頓回路。a ab bc cg gi ih h分析分析 利用定理利用定理11.3.111.3.1的逆否命題，尋找的逆否命題，尋找V V的某的某個非空子

21、集個非空子集V V1 1使得使得p(G-Vp(G-V1 1) )|V|V1 1| |，則，則G G不是哈密頓不是哈密頓圖。找到圖。找到V V1 1 = = d, e, fd, e, f滿足要求。滿足要求。證明證明 在圖中，刪除結(jié)在圖中，刪除結(jié)點子集點子集d, e, fd, e, f，得，得新圖，它的連通分支為新圖，它的連通分支為4 4個，由定理個，由定理11.3.111.3.1知，知，該圖不是哈密頓圖，因該圖不是哈密頓圖，因而不會存在哈密頓回路。而不會存在哈密頓回路。d df fe ea ab bc cg gi ih h20哈密頓圖的充分條件哈密頓圖的充分條件定理定理11.3.211.3.2

22、設(shè)設(shè)G = G = 是具有是具有n n個結(jié)點的簡單個結(jié)點的簡單無向圖無向圖。如。如果對任意兩個不相鄰的結(jié)點果對任意兩個不相鄰的結(jié)點u, u, vVvV，均有，均有deg(u)+deg(v)n-1deg(u)+deg(v)n-1則則G G中存在哈密頓通路。中存在哈密頓通路。推論推論11.3.211.3.2 設(shè)設(shè)G = G = 是具有是具有n n個結(jié)點的簡單無向圖。如個結(jié)點的簡單無向圖。如果對任意兩個不相鄰的結(jié)點果對任意兩個不相鄰的結(jié)點u, u, vVvV，均有，均有deg(u)+deg(v)ndeg(u)+deg(v)n則則G G中存在哈密頓回路。中存在哈密頓回路。推論推論11.3.311.3.

23、3 設(shè)設(shè)G = G = 是具有是具有n n個結(jié)點的簡單無向圖，個結(jié)點的簡單無向圖，n3n3。如果對任意。如果對任意vVvV，均有，均有deg(vdeg(v) n/2) n/2，則，則G G是哈密頓圖。是哈密頓圖。需要注意，定理需要注意，定理11.3.211.3.2給出的是哈密頓圖的充分給出的是哈密頓圖的充分條件，而不是必要條件。在六邊形中，任兩個不條件，而不是必要條件。在六邊形中，任兩個不相鄰的結(jié)點的度數(shù)之和都是相鄰的結(jié)點的度數(shù)之和都是4 46 6，但六邊形是哈，但六邊形是哈密頓圖。密頓圖。21例例11.3.311.3.3某地有某地有5 5個風景點，若每個風景點均有個風景點，若每個風景點均有2

24、 2條道路與其條道路與其他點相通。問游人可否經(jīng)過每個風景點恰好一次而他點相通。問游人可否經(jīng)過每個風景點恰好一次而游完這游完這5 5處？處？解解 將將5 5個風景點看成是有個風景點看成是有5 5個結(jié)點的無向圖，兩風個結(jié)點的無向圖，兩風景點間的道路看成是無向圖的邊，因為每處均有兩景點間的道路看成是無向圖的邊，因為每處均有兩條道路與其他結(jié)點相通，故每個結(jié)點的度數(shù)均為條道路與其他結(jié)點相通，故每個結(jié)點的度數(shù)均為2 2，從而任意兩個不相鄰的結(jié)點的度數(shù)之和等于從而任意兩個不相鄰的結(jié)點的度數(shù)之和等于4 4，正，正好為總結(jié)點數(shù)減好為總結(jié)點數(shù)減1 1。故此圖中存在一條哈密頓通路，。故此圖中存在一條哈密頓通路，因此

25、游人可以經(jīng)過每個風景點恰好一次而游完這因此游人可以經(jīng)過每個風景點恰好一次而游完這5 5處。處。22有向圖上的哈密爾頓通路有向圖上的哈密爾頓通路設(shè)設(shè)G = G = 是有是有n(n2)n(n2)個結(jié)點的一些簡單有向個結(jié)點的一些簡單有向圖。如果忽略圖。如果忽略G G中邊的方向所得的無向圖中含生成中邊的方向所得的無向圖中含生成子圖完全圖子圖完全圖KnKn，則有向圖，則有向圖G G中存在中存在哈密頓通路哈密頓通路。v v2 2v v3 3v v1 1v v4 4v v5 5 在右圖中，它所對應(yīng)在右圖中，它所對應(yīng)的無向圖中含完全圖的無向圖中含完全圖K K5 5，由定理由定理11.3.311.3.3知，圖中

26、含知，圖中含有哈密頓通路。事實上，有哈密頓通路。事實上，通路通路v v3 3v v5 5v v4 4v v2 2v v1 1為一條哈密為一條哈密頓通路。頓通路。 2311.3.3 11.3.3 哈密頓圖小節(jié)哈密頓圖小節(jié) 1.1. 僅有哈密頓通路而無哈密頓回路的圖不是哈密僅有哈密頓通路而無哈密頓回路的圖不是哈密頓圖；頓圖；2.2. 還沒有判斷圖中是否存在歐拉通路、歐拉回路還沒有判斷圖中是否存在歐拉通路、歐拉回路圖的簡單判定定理，我們只能對結(jié)點較少的圖圖的簡單判定定理，我們只能對結(jié)點較少的圖憑經(jīng)驗去判定；憑經(jīng)驗去判定；3.3. 在哈密頓圖中有定理僅是必要條件，此必要條在哈密頓圖中有定理僅是必要條件

27、，此必要條件正方面的敘述無法用來判斷一個圖是否是哈件正方面的敘述無法用來判斷一個圖是否是哈密頓圖，此時該定理是毫無用處的，但必要條密頓圖，此時該定理是毫無用處的，但必要條件的等價逆敘述卻非常的重要，用此逆敘述可件的等價逆敘述卻非常的重要，用此逆敘述可以判斷一個圖不是哈密爾圖。以判斷一個圖不是哈密爾圖。2411.3.4 11.3.4 哈密頓圖的應(yīng)用哈密頓圖的應(yīng)用 1 1、巡回售貨員問題、巡回售貨員問題 G = G = 是是n n個結(jié)點的賦權(quán)完全圖，這個結(jié)點的賦權(quán)完全圖，這里里V = vV = v1 1, v, v2 2, , , , v vn n 是城市的集合，是城市的集合，E E是連接城是連接

28、城市的道路的集合，市的道路的集合，W W是從是從E E到正實數(shù)集合的一個函數(shù)到正實數(shù)集合的一個函數(shù)( (即即W(vW(vi i, , v vj j) )是城市是城市v vi i與與v vj j之間的距離之間的距離) )，試求出該，試求出該賦權(quán)圖上的最小權(quán)（距離）哈密頓回路。賦權(quán)圖上的最小權(quán)（距離）哈密頓回路。2511.4 11.4 偶圖偶圖 11.4.1 11.4.1 偶圖的定義偶圖的定義定義定義11.4.111.4.1 若無向圖若無向圖G = G = 的結(jié)點集的結(jié)點集V V能夠能夠劃分劃分為為兩個子集兩個子集V V1 1, V, V2 2，滿足，滿足V V1 1VV2 2 = = ，且，且V

29、 V1 1VV2 2 = V = V，使得，使得G G中中任意一條邊的兩個端點任意一條邊的兩個端點，一一個屬于個屬于V V1 1，另一個屬于，另一個屬于V V2 2，則稱，則稱G G為為偶圖偶圖(Bipartite Graph)(Bipartite Graph)或或二分圖二分圖( (BigraphBigraph) )。V V1 1和和V V2 2稱稱為為互補結(jié)點子集互補結(jié)點子集，偶圖通常記為，偶圖通常記為G=VG= 。 偶圖沒有自回路。偶圖沒有自回路。 平凡圖和零圖可看成特殊的偶圖平凡圖和零圖可看成特殊的偶圖。 26定義定義11.4.211.4.2在偶圖在偶圖G = VG = 中，若中，若V

30、V1 1中的每個結(jié)點與中的每個結(jié)點與V V2 2中的每個結(jié)點中的每個結(jié)點都都有且僅有一條邊相關(guān)聯(lián)有且僅有一條邊相關(guān)聯(lián)，則稱偶圖，則稱偶圖G G為為完全偶圖完全偶圖(Complete Bipartite Graph)(Complete Bipartite Graph)或或完全完全二分圖二分圖(Complete (Complete BigraphBigraph) )，記為，記為K Ki,ji,j，其中，其中，i = i = |V|V1 1| |，j = |Vj = |V2 2| |。27例例11.4.111.4.1判斷圖中的幾個圖，那些是偶圖？那些是完全偶圖？判斷圖中的幾個圖，那些是偶圖？那些是完

31、全偶圖？ v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7(a)(a)v v6 6v v1 1v v4 4v v3 3v v5 5v v2 2(d)(d)(b)(b)v v1 1v v2 2v v3 3v v4 4v v5 5(c)(c)v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v1 1v v4 4v v2 2v v3 3(e)(e)偶圖偶圖 偶圖偶圖 偶圖偶圖 偶圖偶圖 不是不是偶圖偶圖 完全完全偶圖偶圖K K2,32,3 完全完全偶圖偶圖K K3,33,3 完全完全偶圖偶圖K K3,33,3 2811.4.2 11.4.

32、2 偶圖的判定偶圖的判定定理定理11.4.111.4.1 無向圖無向圖G = G = 為偶圖的充分必為偶圖的充分必要條件是要條件是G G的所有回路的長度均為偶數(shù)。的所有回路的長度均為偶數(shù)。直觀理解：有來有往直觀理解：有來有往 無向圖無向圖G G 不是偶圖的充分必要條件是不是偶圖的充分必要條件是G G中存在長中存在長度為奇數(shù)的回路。度為奇數(shù)的回路。v v1 1v v4 4v v2 2v v3 32911.4.3 11.4.3 匹配匹配 定義定義11.4.211.4.2 在偶圖在偶圖G = VG = 中，中，V V1 1 = v = v1 1, , v v2 2, , , , v vq q ，若存

33、在，若存在E E的子集的子集E = (vE = (v1 1, v, v1 1)，(v(v2 2, v, v2 2)，( (v vq q, , v vq q)，其中，其中v v1 1, v, v2 2, , , , v vq q 是是V V2 2中的中的q q個個不同的結(jié)點不同的結(jié)點 ，則稱，則稱G G的子圖的子圖G = G = V 為從為從V V1 1到到V V2 2的一個的一個完全匹配完全匹配(Complete Matching)(Complete Matching)，簡稱，簡稱匹配匹配。30必要條件必要條件 在偶圖在偶圖G = VG = 中，若存在中，若存在V V1 1到到V V2 2的單

34、的單射射f f，使得對任意，使得對任意vVvV1 1，都有，都有(v, (v, f(v)Ef(v)E，則存，則存在在V V1 1到到V V2 2的匹配。的匹配。 由單射的性質(zhì)知，不是所有的偶圖都有匹配，由單射的性質(zhì)知，不是所有的偶圖都有匹配，存在匹配的必要條件是存在匹配的必要條件是|V|V1 1| |V| |V2 2| |。 然而，這個條件并不是充分條件。然而，這個條件并不是充分條件。 31例例11.4.211.4.2下面的下面的3 3個偶圖哪些存在個偶圖哪些存在V V1 1到到V V2 2匹配？對存在匹配匹配？對存在匹配的偶圖給出一個匹配。的偶圖給出一個匹配。 (b)(b)v v1 1v v

35、2 2v v3 3v v4 4v v5 5v v6 6V V1 1V V2 2v v1 1v v2 2v v3 3v v5 5v v6 6v v7 7v v8 8(c)(c)v v4 4v v9 9V V1 1V V2 2v v1 1v v2 2v v3 3v v6 6v v7 7v v8 8(a)(a)v v4 4V V1 1V V2 2v v1 1v v2 2v v3 3v v5 5v v6 6v v7 7v v8 8v v4 4v v9 9V V1 1V V2 2不存在不存在匹配匹配 不存在不存在匹配匹配 存在存在匹配匹配 32霍爾定理霍爾定理定理定理11.4.211.4.2 ( (霍爾

36、定理霍爾定理) ) 偶圖偶圖G = VG = 中中存在從存在從V V1 1到到V V2 2的匹配的充分必要條件是的匹配的充分必要條件是V V1 1中任意中任意k k個個結(jié)點至少與結(jié)點至少與V V2 2中的中的k k個結(jié)點相鄰個結(jié)點相鄰，k = 1, 2, k = 1, 2, , , |V|V1 1| |。 定理定理11.4.211.4.2中的條件通常稱為中的條件通常稱為相異性條件相異性條件(Diversity Condition)(Diversity Condition)。33例例不滿足相異性條件，不滿足相異性條件，故沒有匹配。故沒有匹配。(b)(b)v v1 1v v2 2v v3 3v v

37、4 4v v5 5v v6 6V V1 1V V2 2v v1 1v v2 2v v3 3v v5 5v v6 6v v7 7v v8 8(c)(c)v v4 4v v9 9V V1 1V V2 2滿足相異性條件，滿足相異性條件，故存在匹配故存在匹配34定理定理11.4.311.4.3設(shè)設(shè)G = VG = 是一個偶圖。如果滿足條件是一個偶圖。如果滿足條件（1 1）V V1 1中每個結(jié)點至少關(guān)聯(lián)中每個結(jié)點至少關(guān)聯(lián)t t條邊；條邊；（2 2）V V2 2中每個結(jié)點至多關(guān)聯(lián)中每個結(jié)點至多關(guān)聯(lián)t t條邊；條邊；則則G G中存在從中存在從V V1 1到到V V2 2的匹配。其中的匹配。其中t t為正整數(shù)

38、。為正整數(shù)。定理定理11.4.311.4.3中的條件通常稱為中的條件通常稱為t t條件條件(t-(t-Condition)Condition)。判斷判斷t t條件非常簡單，只需要條件非常簡單，只需要計算計算V V1 1中結(jié)點的最小中結(jié)點的最小度數(shù)度數(shù)和和V V2 2中結(jié)點的最大度數(shù)中結(jié)點的最大度數(shù)即可。即可。 3511.5 11.5 平面圖平面圖 11.5.1 11.5.1 平面圖的定義平面圖的定義 在電路板布線時會發(fā)現(xiàn)，不僅需要允許各邊在結(jié)點在電路板布線時會發(fā)現(xiàn)，不僅需要允許各邊在結(jié)點處相交，而且還應(yīng)該允許各邊在某些非結(jié)點處相交，處相交，而且還應(yīng)該允許各邊在某些非結(jié)點處相交，這樣的點稱為這樣

39、的點稱為交叉點交叉點(Cross Point)(Cross Point)；而相交的邊，；而相交的邊，稱為稱為交叉邊交叉邊(Cross Edge)(Cross Edge)。v v1 1v v2 2v v3 3v v4 4v v5 536定義定義11.5.111.5.1如果如果把一個無向圖把一個無向圖G G的所有結(jié)點和邊的所有結(jié)點和邊畫在平面上畫在平面上，使得使得任何兩邊除公共結(jié)點外沒有其他交叉點任何兩邊除公共結(jié)點外沒有其他交叉點，則稱，則稱G G為為平面圖平面圖(Plane Graph)(Plane Graph)，否則稱，否則稱G G為為非平面圖非平面圖( (NonplanarNonplanar

40、 Graph) Graph)。 當且僅當一個圖的每個連通分支都是平面圖時，當且僅當一個圖的每個連通分支都是平面圖時，這個圖是平面圖。這個圖是平面圖。應(yīng)當注意，應(yīng)當注意，有些圖從表面上看它的某些邊是相交叉有些圖從表面上看它的某些邊是相交叉的，但是不能就此肯定它不是平面圖。的，但是不能就此肯定它不是平面圖。v v1 1v v2 2v v3 3v v4 4v v5 5v v1 1v v2 2v v3 3v v4 4v v5 5平面圖的平面表示平面圖的平面表示 37非平面圖非平面圖 有些圖形不論如何改畫，除去結(jié)點外，總有邊有些圖形不論如何改畫，除去結(jié)點外，總有邊相交叉。相交叉。 即不管怎樣改畫，至少有

41、一條邊與其他邊相交即不管怎樣改畫，至少有一條邊與其他邊相交叉，故它是非平面圖。叉，故它是非平面圖。v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v1 1v v2 2v v3 3v v4 4v v5 5v v6 63811.5.2 11.5.2 觀察法觀察法 設(shè)設(shè)G G是畫于平面上的圖，并設(shè)是畫于平面上的圖，并設(shè)C = vC = v1 1v v2 2v v3 3v v4 4v v1 1是是G G中的任何基本回路。此外，設(shè)中的任何基本回路。此外，設(shè)P P1 1 = v = v1 1v v3 3和和P P2 2 = v= v2 2v v4 4是是G G中的任意兩條無公共

42、結(jié)點的基本通路。中的任意兩條無公共結(jié)點的基本通路。v v1 1v v3 3v v4 4v v2 2P P2 2P P1 1P P2 2P P1 1觀察法觀察法 39例例11.5.111.5.1用觀察法來判定圖用觀察法來判定圖K K3,33,3為非平面圖。為非平面圖。 v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v1 1v v5 5v v4 4v v2 2v v3 3v v6 64011.5.3 11.5.3 歐拉公式歐拉公式 定義定義11.5.211.5.2 在平面圖在平面圖G G的一個平面表示中，的一個平面表示中，u 由由邊所包圍的邊所包圍的其其內(nèi)部不包含圖的

43、結(jié)點和邊內(nèi)部不包含圖的結(jié)點和邊的的區(qū)區(qū)域域，稱為，稱為G G的一個的一個面面(Surface)(Surface)，u 包圍該面包圍該面的諸的諸邊所構(gòu)成的回路邊所構(gòu)成的回路稱為這個面的稱為這個面的邊邊界界(Bound)(Bound)，u 面面r r的的邊界的長度邊界的長度稱為該面的稱為該面的次數(shù)次數(shù)(Degree)(Degree)，記，記為為D(rD(r) )。u 區(qū)域區(qū)域面積有限面積有限的面稱為的面稱為有限面有限面(Finite (Finite Surface)Surface)，區(qū)域，區(qū)域面積無限面積無限的面稱為的面稱為無限面無限面(Infinite Surface)(Infinite Sur

44、face)。u 平面圖有且僅有一個無限面平面圖有且僅有一個無限面。41面的形象描述：面的形象描述： 假設(shè)我們把一個平面圖的平面表示畫在平面上，假設(shè)我們把一個平面圖的平面表示畫在平面上，然后用一把然后用一把小刀小刀，沿著圖的，沿著圖的邊邊切開，那么平面就被切開，那么平面就被切成許多切成許多塊塊，每一塊就是圖的一個面。，每一塊就是圖的一個面。 更確切地說，平面圖的一個面就是平面的一塊，更確切地說，平面圖的一個面就是平面的一塊，它用它用邊作邊界線邊作邊界線，且，且不能再分成子塊不能再分成子塊。 42例例11.5.211.5.2考察下圖所示平面圖的面、邊界和次數(shù)。考察下圖所示平面圖的面、邊界和次數(shù)。

45、a ab bd de ec ch hi ij jk kr r0 0r r1 1r r2 2r r3 3解解 平面圖把平面分成平面圖把平面分成4 4個面：個面：r r0 0，邊界為，邊界為abdehecaabdeheca，D(rD(r0 0)=7)=7r r1 1，邊界為，邊界為abcaabca，D(rD(r1 1)=3)=3r r2 2，邊界為，邊界為beckijicbbeckijicb，D(rD(r2 2)=9)=9r r3 3，邊界為，邊界為bdebbdeb，D(rD(r3 3)=3)=3r r1 1、r r2 2和和r r3 3是有限面，是有限面，r r0 0是無限是無限面。面。 注意：

46、注意：對于平面圖的不同平面表示，雖然面的數(shù)目對于平面圖的不同平面表示，雖然面的數(shù)目相同，但各面的邊界和次數(shù)會不同。相同，但各面的邊界和次數(shù)會不同。 i ij ja ab bd de ec ch hk kr r0 0r r1 1r r2 2r r3 343定理定理11.5.111.5.1平面圖中所有面的次數(shù)之和等于邊數(shù)的二倍。平面圖中所有面的次數(shù)之和等于邊數(shù)的二倍。17501750年，年，歐拉歐拉發(fā)現(xiàn)，任何一個發(fā)現(xiàn)，任何一個凸多面體凸多面體，若有，若有n n個個頂點頂點、m m條棱條棱和和r r個面?zhèn)€面，則有，則有n-m+rn-m+r = 2 = 2。這個公式。這個公式可以推廣到平面圖上來，稱之

47、為可以推廣到平面圖上來，稱之為歐拉公式歐拉公式。 44歐拉公式歐拉公式定理定理11.5.211.5.2 設(shè)設(shè)G = G = 是連通平面圖，是連通平面圖，若它有若它有n n個結(jié)點、個結(jié)點、m m條邊和條邊和r r個面，則有個面，則有n-m+rn-m+r = 2 = 2推論推論11.5.111.5.1 設(shè)設(shè)G G是一個是一個( (n,mn,m) )簡單連通平面簡單連通平面圖，若圖，若m m1 1，則有，則有m3n-6m3n-6 一個簡單連通圖，若不滿足一個簡單連通圖，若不滿足m3n-6m3n-6，則一定是非，則一定是非平面圖。平面圖。45例例11.5.311.5.3證明證明5 5個結(jié)點的完全圖個結(jié)

48、點的完全圖K K5 5是非平面圖。是非平面圖。分析分析 因為因為K K5 5是簡單連通圖，我們可以驗證是簡單連通圖，我們可以驗證m m 3n-63n-6不成立，因此它不是平面圖。不成立，因此它不是平面圖。證明證明 因為因為K K5 5是簡單連通圖，是簡單連通圖，n=5n=5，m=10m=10，因此，因此m m3n-6=33n-6=35-6=95-6=9，故不滿足，故不滿足m3n-6m3n-6，因此它不是平，因此它不是平面圖。面圖。 再看圖再看圖K K3,33,3，n=6n=6，m=9m=9，滿足不等式，滿足不等式m3n-6m3n-6，但是我們已用觀察法證明了它是一個非平面圖。但是我們已用觀察法

49、證明了它是一個非平面圖。46推論推論11.5.211.5.2設(shè)設(shè)G G是一個是一個(n, m)(n, m)簡單連通平面圖，若每個面的次簡單連通平面圖，若每個面的次數(shù)至少為數(shù)至少為k(k3)k(k3)，則有，則有 k km m( (n n - -2 2) )k k - -2 2可以用來判定某些圖是非平面圖。可以用來判定某些圖是非平面圖。 一個簡單連通圖，若每個面的次數(shù)至少一個簡單連通圖，若每個面的次數(shù)至少為為k(k3)k(k3)，若不滿足，若不滿足 ，則，則一定是非平面圖。一定是非平面圖。 k km(n -2)m(n -2)k -2k -247例例11.5.411.5.4不使用觀察法證明圖不使用

50、觀察法證明圖K K3,33,3是一個非平面圖。是一個非平面圖。證明證明 利用推論利用推論11.5.211.5.2可以判斷。事實上，假設(shè)可以判斷。事實上，假設(shè)K K3,33,3是一個平面圖，那么它的每個面的次數(shù)均不能是一個平面圖，那么它的每個面的次數(shù)均不能小于等于小于等于3 3，即每個面的次數(shù)均大于等于，即每個面的次數(shù)均大于等于k(k4)k(k4)，由推論由推論11.5.211.5.2，有，有注意到注意到 在在k=4k=4時取最大值時取最大值2 2，因而，因而9898，這是，這是矛盾的。矛盾的。 k k9 9( (6 6 - -2 2) )k k - -2 2k kk k - -2 24811.5.4 11.5.4 庫拉托夫斯基定理庫拉托夫斯基定理 定理定理11.5.3(11.5.3(庫拉托夫斯基定理庫拉托夫斯基定理) ) 一個圖是平面圖一個圖是平面圖的充分必要條件是它的任何子圖都不可能收縮為的充分必要條件是它的任何子圖都不可能收縮為K K5 5或或K K3,33,