離散數學：6-2 特殊的圖

請交作業(yè)五P116:21,22,23,24P137:1,4,5,8P138:12,13,14,15,18,19,20P154:4,5,8P155:16,18

作業(yè)講評四P115:13P116:14,15P115:13x1x2z3z2z1y1y2FGF

°GP116:14abcdeP116:15對任意非空集合S，P(S)-{}是S的非空子集族，那么P(S)-{}能否構成S的劃分？例：設S={1,2}P(S)={,{1},{2},{1,2}}P(S)-{}={{1},{2},{1,2}}——不是劃分例：設S={1}P(S)={,{1}}P(S)-{}={{1}}——是劃分所以若|S|>1時，P(S)-{}不構成S的劃分補充題設R、S是對稱的，試給出R°S不是對稱的例子；

R={<1,2>,<2,1>},S={<1,1>}R°

S={<1,2>}設

R、S是反對稱的，試給出R°S不是反對稱的例子。R={<2,1>,<2,2>},S={<1,2>,<2,2>}

R°S={<1,1>,<1,2>,<2,1>,<2,2>}第6章特殊的圖

6.1二部圖6.2歐拉圖6.3哈密頓圖6.4平面圖

哈密頓周游世界問題1859年，數學家哈密頓發(fā)明了一個周游世界的游戲：在一個實心的正十二面體，每面是一個正五邊形。共計20個頂點標上世界著名大城市的名字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。周游世界問題——即找一條經過所有頂點(城市)的回路。6.3哈密頓圖哈密頓回路:經過圖中所有頂點一次且僅一次的回路.哈密頓圖:具有哈密頓回路的圖.哈密頓通路:經過圖中所有頂點一次且僅一次的通路.半哈密頓圖:具有哈密頓通路而無哈密頓回路的圖.

幾點說明：平凡圖是哈密頓圖.哈密頓回路是初級回路.哈密頓通路是初級通路，環(huán)與平行邊不影響圖的哈密頓性.下列圖中哪些是哈密頓圖？半哈密頓圖?(1)是哈密頓圖;(2)是哈密頓圖;(3)是半哈密頓圖.(4)既不是哈密頓圖,也不是半哈密頓圖.

無向哈密頓圖的一個必要條件

定理：設無向圖G=<V,E>是哈密頓圖,則對V1V且V1,均有p(GV1)|V1|.

證：設C為G中任一條哈密頓回路,(1)當

V1中頂點在C上均不相鄰時，

p(CV1)=|V1|(2)當

V1中頂點在C中有彼此相鄰時，p(CV1)<|V1|所以，有p(CV1)|V1|.

又因為CG,故p(GV1)

p(CV1)

|V1|.

無向哈密頓圖的一個必要條件

由定理知,

Kr,s當sr+1時不是哈密頓圖.而Kr,r+1是半哈密頓圖.當r2時,Kr,r是哈密頓圖,哈密頓圖的必要條件：p(GV1)|V1|實例1設G為n階無向連通簡單圖,若G中有割點或橋,則G不是哈密頓圖.證:

設v為割點,刪除結點v，圖成為不連通的，且至少有兩個連通分支。則p(Gv)2>|{v}|=1.

根據定理,G不是哈密頓圖.

(2)如果G中有橋，則該橋的一個端點是割點?？梢詺w結為G中有割點的情況。所以G也不是哈密爾頓圖。

哈密頓圖的必要條件：p(GV1)|V1|vv實例2

下圖為彼得森圖。它滿足定理的條件，在刪除任意一個或兩個頂點，仍是連通的；刪除3個頂點，最多只能得到有兩個連通分支的子圖；刪除4個頂點，最多只能得到有3個連通分支的子圖；刪除≥5個頂點，余下子圖的頂點數都不大于5，故必不能有5個以上的連通分支數，所以，滿足p(G-S)|S|。但此圖是典型的非哈密爾頓圖!哈密頓圖的必要條件：p(GV1)|V1|無向哈密頓圖的一個必要條件

定理：設無向圖G=<V,E>是哈密頓圖,則對V1V且V1,均有p(GV1)|V1|.幾點說明即滿足此定理條件的圖不一定是哈密頓圖，而不滿足此定理條件的圖一定不是哈密頓圖。無向哈密頓圖的一個充分條件

定理

設G是n階無向簡單圖,若任意兩個不相鄰的頂點的度數之和大于等于n1,則G中存在哈密頓通路.

d(u)+d(v)≥n-1(u,v

不相鄰)推論當n3時,若任意兩個不相鄰的頂點的度數之和大于等于n,則G中存在哈密頓回路.

d(u)+d(v)≥n(u,v不相鄰)說明：

定理中的條件是存在哈密頓通路(回路)的充分條件,但不是必要條件.哈密頓通路(回路)的存在性下圖有6個結點，任意兩個結點度數的和小于5，但圖中存在一條哈密頓通路。下圖也有6個結點，任意兩個結點度數的和小于6，但圖中存在一條哈密頓回路。判斷某圖是否為哈密頓圖至今還是一個難題!

判斷是否是哈密頓圖的可行方法觀察出一條哈密頓回路例如：右圖(周游世界問題)中紅邊給出一條哈密頓回路,故它是哈密頓圖。滿足充分條件如當n3時,Kn中任意兩個不相鄰頂點u,v,均有d(u)+d(v)=2(n1)

n,所以Kn為哈密頓圖.不滿足必要條件

如Kr,r+1不滿足p(GV1)|V1|.所以,不是哈密頓圖哈密頓通路(回路)的存在性判斷無向哈密頓圖的必要條件無向哈密頓圖的充分條件必定是哈密頓圖必定不是哈密頓圖不能確定是否是哈密頓圖

應用實例——圓桌排座問題某次國際會議8人參加，已知每人至少與其余7人中的4人有共同語言，問服務員能否將他們安排在同一張圓桌就座，使得每個人都能與兩邊的人交談？解：作無向圖G=<V,E>,其中

V={v|v為與會者}，

E={(u,v)|u,vV,u與v有共同語言,且uv}.G為簡單圖.根據條件,vV,d(v)4.于是，u,vV,有d(u)+d(v)8.由定理可知G為哈密頓圖.服務員可在G中找一條哈密頓回路，按它的相鄰關系安排座位即可.哈密頓圖的實質是能將圖中所有的頂點排在同一個圈中哈密頓回路的應用——格雷碼000100101111110010011001n=5時,需要計算12個權值.n=25時,需要計算24!/23.11023個權值.如果計算每個哈密頓回路權值需要1ns,共需1千萬年才能全部算完,找到權值最小的哈密頓回路.貨郎擔問題（旅行商問題）TravelingSalesmanProblem——TSP

一個貨郎需要經過n個城鎮(zhèn),然后回到出發(fā)點.已知每兩個城鎮(zhèn)之間的距離,這個貨郎應如何選擇路線,經過每個城鎮(zhèn)一次且僅一次,并且總的行程最短?算法:求每一條哈密頓回路的總權值,然后從中找出最小值.對于n個頂點的完全圖有

(n-1)!條不同的哈回路.同構意義下,需要計算(n-1)!/2個權值.貨郎擔問題（旅行商問題）TravelingSalesmanProblem——TSP

以往世界解決TSP問題的情況6.4平面圖——引例1考慮把三座房屋與三種設施(水、電、煤氣)每種都連接起來的問題：能否使得連接線路不交叉?經簡化變?yōu)?能否畫出K3,3使得沒有兩條邊發(fā)生交叉？

平面圖——引例2在許多實際問題中，往往會涉及圖的可平面化問題，如：電路設計經常要考慮布線是否可以避免交叉以減少元件間的互感影響----單層印刷電路板布線問題;為安全起見，建筑物的地下水管、煤氣管、電纜線等不能交叉。平面圖和平面嵌入

定義

如果能將圖G除頂點外邊不相交地畫在平面上,則稱G是平面圖.這個畫出的無邊相交的圖稱作G的平面嵌入.沒有平面嵌入的圖稱作非平面圖.

完全圖K3是平面圖完全圖K4是平面圖K2,3是平面圖平面圖和平面嵌入設GG,若G為平面圖,則G也是平面圖;設GG,若G為非平面圖,則G也是非平面圖.K5和K3,3是非平面圖Kn(n5),K3,n(n3)都是非平面圖.平行邊與環(huán)不影響圖的平面性.

K5K3,3平面圖的面與次數設G是一個平面嵌入，G的面:由G的邊將平面劃分成的每一個區(qū)域。無限面(外部面):面積無限的面,用R0表示。有限面(內部面):面積有限的面,用R1,R2,…,Rk表示。面Ri的邊界:包圍Ri的所有邊構成的回路組。面Ri的次數:Ri邊界的長度，用deg(Ri)表示。說明:構成一個面的邊界的回路組可能是初級

回路、簡單回路,也可能是復雜回路,

甚至還可能是非連通的回路之并.R0R3R2R1上圖共有4個面：deg(R1)=1deg(R2)=3deg(R3)=2deg(R0)=8右圖和左圖是同構的。

R0:外部面(左圖),內部面(右圖)R1:內部面(左圖),外部面(右圖)其實，在平面嵌入中可把任何面作為外部面.平面圖的面與次數R0R1R2R1R2R0平面圖的面與次數定理

在一個平面圖G中，所有面的次數之和等于邊數m的2倍.其中，r為面數。說明G中每條邊無論作為兩個面的公共邊界，還是作為一個面的邊界，在算總次數時都計算兩次。極大平面圖

定義若G是簡單平面圖,并且在任意兩個不相鄰的頂點之間加一條新邊所得圖為非平面圖,則稱G為極大平面圖.若簡單平面圖中已無不相鄰頂點，則是極大平面圖。3個圖都是平面圖,但只有右邊的圖為極大平面圖.

極大平面圖的性質

K3是極大平面圖K4是極大平面圖n(n3)階極大平面圖Ri=3若簡單平面圖中已不相鄰頂點，則是極大平面圖。如K1、K2、K3、K4都是極大平面圖。極大平面圖必連通。任何n(n3)階極大平面圖不可能有割點和橋。若G為n(n3)階極大平面圖，則G每個面的次數均為3.任何n(n4)階極大平面圖G均有(G)3。極小非平面圖

定義

若G是非平面圖,并且任意刪除一條邊所得圖都是平面圖,則稱G為極小非平面圖.說明:

K5

是極小非平面圖

K3,3是極小非平面圖極小非平面圖必為簡單圖K3,3K5歐拉公式證：對邊數m做歸納證明.

m=0,G為平凡圖,n=1,r=1.1-0+1=2，結論為真.

設m