離散數(shù)學(xué)第八章省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

第八章一些特殊圖8.1

二部圖8.2

歐拉圖8.3

哈密爾頓圖8.4

平面圖

1/498.1二部圖(P286-287)定義8.1若能將無向圖G=<V,E>頂點(diǎn)集V劃分成兩個子集V1和V2(V1∩V2=

),使得G中任何一條邊兩個端點(diǎn)一個屬于V1,另一個屬于V2,則稱G為二部圖(也稱為偶圖).V1,V2稱為互補(bǔ)頂點(diǎn)子集,此時可將G記成G=<V1,V2,E>.

若V1中任一頂點(diǎn)與V2中每個頂點(diǎn)有且僅有一條邊相關(guān)聯(lián),則稱二部圖G為完全二部圖(或完全偶圖).若

V1

=n,V2=m,則記完全二部圖G為Kn,m.

在下列圖中,(1)所表示為K2,3,(2)所表示為K3,3.K3,3是主要完全二部圖,它與K5一起在平面圖中起著主要作用.2/498.1二部圖定理8.1一個無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇數(shù)長度回路.如圖8.2均無奇數(shù)長度回路,都是二部圖.其中圖(2)所表示為K2,3,圖(3)所表示為K3,3.624153二部圖判斷定理3/49

8.1二部圖定義8.2設(shè)G=<V,E>為無向圖,E*

E,若E*中任意兩條邊均不相鄰,則稱E*為G中匹配(或邊獨(dú)立集).①

若在E*中再加入任何1條邊就都不是匹配了,則稱E*為極大匹配.②

邊數(shù)最多極大匹配稱為最大匹配,最大匹配中元素(邊)個數(shù)稱為G匹配數(shù),記為

1(G),簡記為

1.注意:今后慣用M表示匹配.設(shè)M為G中一個匹配.v

V(G),若存在M中邊與v關(guān)聯(lián),則稱v為M飽和點(diǎn),不然稱v為M非飽和點(diǎn),若G中每個頂點(diǎn)都是M飽和點(diǎn),則稱M為G中完美匹配.匹配4/49在圖(1)中匹配有：

{e1},{e1,e7},{e5},{e4,e6}.其中，{e5},{e1,e7},{e4,e6}是極大匹配,{e1,e7},{e2,e6}是最大匹配,匹配數(shù)

1=2.圖中不存在完美匹配.在圖(2)中匹配有：全部匹配是極大匹配,{e1,e7,e4}是最大匹配,同時也是完美匹配,匹配數(shù)為3.{e2,e5},{e3,e6},{e1,e7,e4}5/498.1二部圖定義8.3設(shè)G=<V1,V2,E>為一個二部圖,M為G中一個最大匹配,若

M

=min{V1

,V2

},則稱M為G中一個完備匹配,此時若

V1

≤

V2

,則稱M為V1到V2一個完備匹配.假如

V1

=

V2

,這時M為G中完美匹配.完備匹配存在完備匹配嗎?存在完美匹配嗎?6/498.1二部圖定理8.2設(shè)二部圖G=<V1,V2,E>,V1

≤V2

,G中存在從V1到V2完備匹配當(dāng)且僅當(dāng)V1中任意k個頂點(diǎn)(k=1,2,…

V1

)最少鄰接V2中k個頂點(diǎn).定理8.3設(shè)二部圖G=<V1,V2,E>,假如

(1)V1中每個頂點(diǎn)最少關(guān)聯(lián)t(t＞0)條邊;(2)V2中每個頂點(diǎn)至多關(guān)聯(lián)t條邊,則G中存在V1到V2完備匹配.Hall定理7/49Hall定理中條件稱為“相異性條件”,定理8.3中條件稱為“t條件”,滿足t條件二部圖,一定滿足相異性條件.實際上,由條件(1)可知,V1中k個頂點(diǎn)最少關(guān)聯(lián)kt條邊.由條件(2)可知,這kt條邊最少關(guān)聯(lián)V2中k個頂點(diǎn),于是若G滿足t條件,則G一定滿足相異性條件,但反之不真.8.1二部圖Hall定理8/49例8.1某中學(xué)有3個課外小組:物理組、化學(xué)組、生物組.今有張、王、李、趙、陳5名同學(xué).若已知:(1)張、王為物理組組員,張、李、趙為化學(xué)組組員,李、趙、陳為生物組組員;(2)張為物理組組員,王、李、趙為化學(xué)組組員,王、李、趙、陳為生物組組員;(3)張為物理組和化學(xué)組組員,王、李、趙、陳為生物組組員.

問在以上3種情況下能否各選出3名不兼職組長？9/49解:設(shè)v1,v2,v3,v4,v5分別表示張,王,李,趙,陳;u1,u2,u3分別表示物理組,化學(xué)組,生物組;在3種情況下作二部圖分別記為G1,G2,G3,以下列圖所表示.10/49G1滿足t=2t條件,所以,存在從V1={u1,u2,u3}到V2={v1,v2,v3,v4,v5}完備匹配,圖中粗邊所表示匹配就是其中一個,即選張為物理組組長,李為化學(xué)組組長,趙為生物組組長.G2不滿足t條件,但滿足相異性條件,因而也存在完備匹配,圖中粗邊所表示匹配就是其中一個完備匹配.G3不滿足t條件,也不滿足相異性條件,因而不存在完備匹配,故選不出3名不兼職組長來.11/498.2歐拉圖(即一筆畫問題)18世紀(jì)在哥尼斯堡城(今俄羅斯加里寧格勒)普萊格爾河上有7座橋,將河中兩個島和河岸連結(jié),如圖所表示.城中居民經(jīng)常沿河過橋散步,于是提出了一個問題:能否一次走遍7座橋,而每座橋只許經(jīng)過一次,最終仍回到起始地點(diǎn).這就是七橋問題,一個著名圖論問題.大數(shù)學(xué)家歐拉那里證實了這么走法不存在.§哥尼斯堡七橋問題12/49無向圖歐拉圖及其判斷定義8.4經(jīng)過圖中每條邊一次且僅一次而且行遍圖中每個頂點(diǎn)通路(回路),稱為歐拉通路或歐拉跡(歐拉回路或歐拉閉跡).存在歐拉回路圖,稱為歐拉圖.只存在歐拉通路圖,稱為半歐拉圖.定理8.4無向圖G為歐拉圖當(dāng)且僅當(dāng)G是連通,且G中無奇度頂點(diǎn).

無向圖G為半歐拉圖,當(dāng)且僅當(dāng)G是連通且G中有兩個奇度頂點(diǎn).注:

若無奇度頂點(diǎn),則通路為回路;若有兩個奇度頂點(diǎn),則它們是歐拉通路端點(diǎn).8.2歐拉圖(即一筆畫問題)13/49例.8.2歐拉圖(即一筆畫問題)

圖中(1)(2)(3)不是歐拉圖,(4)是歐拉圖.14/498.2歐拉圖(即一筆畫問題)例.圖1是歐拉圖;圖2不是歐拉圖,但存在歐拉通路;圖3既不是歐拉圖,也不存在歐拉通路.15/498.2歐拉圖(即一筆畫問題)有向圖歐拉回路判定定理定理8.5一個有向圖D是歐拉圖,當(dāng)且僅當(dāng)D是強(qiáng)連通,且全部頂點(diǎn)入度等于出度.一個有向圖D是半歐拉圖,當(dāng)且僅當(dāng)D是單向連通,且恰有兩個奇度頂點(diǎn),其中一個入度比出度大1,另一個入度比出度小1.而其余頂點(diǎn)入度均等于出度.(1)既無歐拉回路,也無歐拉通路.(2)中存在歐拉通路,但無歐拉回路,即為半歐拉圖.(3)中存在歐拉回路,即為歐拉圖.16/498.3哈密爾頓圖1895年愛爾蘭數(shù)學(xué)家威廉.哈密爾頓首先提出了在正十二面體上一個數(shù)學(xué)游戲,即能否在如圖所表示圖上找到一條初級回路,使它經(jīng)過每個城市恰好一次,這個問題就是“周游世界問題”.這么通路(回路)就是哈密爾頓通路(回路).17/498.3哈密爾頓圖定義8.5經(jīng)過圖中每個頂點(diǎn)一次且僅一次通路(回路)稱為哈密爾頓通路(回路).存在哈密爾頓回路圖稱為哈密爾頓圖.只存在哈密爾頓通路圖稱為半哈密爾頓圖.例:圖中(1)是半哈密爾頓圖,(2)為哈密爾頓圖,(3)既不是半哈密爾頓圖也不是哈密爾頓圖.18/498.3哈密爾頓圖哈密爾頓圖判定定理8.6(必要條件)若無向圖G=<V,E>是哈密爾頓圖,則對V任意非空真子集V1,都有p(G-V1)≤

V1

.其中,p(G-V1)為從G中刪除V1(刪除V1中各頂點(diǎn)及關(guān)聯(lián)邊)后所得圖連通分支數(shù).推論若無向圖G=<V,E>是半哈密爾頓圖,則對V任意非空真子集V1,都有p(G-V1)≤

V1+1.注:利用該定理能夠判斷一些圖不是哈密爾頓圖.19/498.3哈密爾頓圖證實:設(shè)C為G中一條哈密爾頓回路.(1)若V1中頂點(diǎn)在C上彼此相鄰,則

p(C-V1)=1≤

V1

(2)設(shè)V1中頂點(diǎn)在C上存在r(2≤r≤V1

)個互不相鄰,則

p(C-V1)=r≤

V1

普通說來,V1中頂點(diǎn)在C上現(xiàn)有相鄰,又有不相鄰,因而總有p(C-V1)≤

V1

.又因為C是G生成子圖,故

p(G-V1)≤p(C-V1)≤V1

.20/49圖(1)刪除節(jié)點(diǎn)a.圖(2)刪除V1={a,b,c,d,e,f,g}8.3哈密爾頓圖(1)(2)abcdfega21/498.3哈密爾頓圖在圖中,即使對任意結(jié)點(diǎn)集合V1,都滿足p(G-V1)

|V1|,但它依然不是哈密爾頓圖.說明：該條件不能作為判斷哈密爾頓圖充分條件.例:22/49定理8.7(充分條件)設(shè)G＝<V,E>是n(n≥3)階無向簡單圖.假如G中任意兩個不相鄰結(jié)點(diǎn)u,v

V.都有：d(u)+d(v)n-1，則G中存在哈密爾頓通路.推論

設(shè)G＝<V,E>是n(n≥3)階無向簡單圖,假如對任意兩個不相鄰結(jié)點(diǎn)u,v

V,都有:d(u)+d(v)n

則G中存在哈密爾頓回路,即G是哈密爾頓圖.8.3哈密爾頓圖23/498.3哈密爾頓圖例:在右圖中,任意兩個結(jié)點(diǎn)度數(shù)之和為4,結(jié)點(diǎn)數(shù)為6,即有46,但它依然是哈密爾頓圖.說明:該條件是不完備.關(guān)于有向圖哈密爾頓回路與通路定理8.8

在n(n≥2)階有向圖D=<V,E>中,假如全部有向邊均用無向邊代替,所得無向圖中含生成子圖Kn,則有向圖D中存在哈密爾頓通路.推論

n(n≥3)階有向完全圖為哈密爾頓圖.注:到當(dāng)前為止,只能依據(jù)定義判斷一個圖是否為哈密爾頓圖,只有在特殊情況下才有判斷方法.24/498.4平面圖8.4.1平面圖基本概念定義8.6一個圖G若能以這么方式畫在平面上；除頂點(diǎn)處外無邊交叉出現(xiàn),則稱G為平面圖.畫出無邊交叉出現(xiàn)圖稱為G一個平面嵌入.無平面嵌入圖稱為非平面圖.

圖中,(2)是(1)(K4)平面嵌入,所以(1)是平面圖.(2)是平面圖.(3),(5)都不是平面圖,即K5和K3,3都不是平面圖.(4),(6)分別是(3),(5)交叉最少畫法.25/498.4平面圖8.4.1平面圖基本概念定義8.7設(shè)G是一個連通平面圖(指G某個平面嵌入),G邊將G所在平面劃分成若干個區(qū)域,每個區(qū)域稱為G一個面.其中面積無限區(qū)域稱為無限面或外部面,常記成R0.包圍每個面全部邊所組成回路稱為該面邊界,邊界長度稱為該面次數(shù),R次數(shù)記為deg(R).★對于非連通平面圖G有k(k≥2)個連通分支,則G無限面R0邊界由k個回路圍成.26/49圖(1)所表示為連通平面圖,共有3個面R0,R1,R2.

R1邊界為回路v1v3v4v1,deg(R1)=3.

R2邊界為回路v1v2v3v1,deg(R2)=3.

R0邊界為復(fù)雜回路v1v4v5v6v5v4v3v2v1,

deg(R0)=8.

27/498.4.1平面圖基本概念定理8.9在一個平面圖G中,全部面次數(shù)之和都等于邊數(shù)m2倍,即(r為面數(shù))8.4平面圖例:圖(2)與(3)都是(1)平面嵌入,它們都與(1)同構(gòu).圖(2)中deg(R0)=3;圖(3)中deg(R0)=4.28/498.4平面圖8.4.1平面圖基本概念極大平面圖、極小非平面圖定義8.8

設(shè)G為一個簡單平面圖,假如在G中任意不相鄰兩個頂點(diǎn)之間再加一條邊,所得圖為非平面圖,則稱G為極大平面圖.若在非平面圖G中任意刪除一條邊,所得圖為平面圖,則稱G為極小非平面圖.29/498.4平面圖K5,K3,3是極小非平面圖,K5任意刪除一條邊后所得圖是極大平面圖

例30/498.4平面圖8.4.1平面圖基本概念極大平面圖有以下性質(zhì):

(1)極大平面圖是連通;(2)任何n(n≥3)階極大平面圖中,每個面次數(shù)均為3.(3)任何n(n≥4)階極大平面圖G中,都有

(G)≥3.31/498.4平面圖8.4.2歐拉公式定理8.10

設(shè)G為任意連通平面圖,則有

n-m+r＝2成立.其中,n為G中頂點(diǎn)數(shù),m為邊數(shù),r為面數(shù).該定理中公式為歐拉公式.證實:

對邊數(shù)m作歸納法.(1)m＝0時,G為孤立點(diǎn),此時n＝1,r＝1,結(jié)論自然成立.(2)設(shè)m＝k-1(k≥1)時結(jié)論成立,要證實m＝k時結(jié)論成立.32/498.4平面圖8.4.2歐拉公式歐拉公式證實(續(xù))首先,若G為樹,任取一樹葉v并刪除它,得G'＝G-v,G'中有n'＝n-1個頂點(diǎn)m'＝m-1條邊,r'＝r,由歸納假設(shè)有下式成立;n'-m'+r'＝2,

即(n-1)-(m-1)+r＝2,

整理后得n-m+r＝2.其次,G不是樹,證實則G中必有初級回路.設(shè)C為一初級回路,e在C上.令G'＝G-e,因為e在C上,所以,G'仍連通,在G'中,n'＝n,m'＝m-1,r'＝r-1,利用歸納假設(shè)可得

n-m+r＝2.33/498.4平面圖8.4.2歐拉公式歐拉公式推廣對于任意p(p≥2)個連通分支平面圖G,有

n-m+r＝p+1

成立.34/498.4平面圖8.4.2歐拉公式定理8.11

設(shè)G是連通平面圖,且每個面次數(shù)最少為l(l≥3),則推廣設(shè)G是p(p≥2)個連通分支平面圖,每個面次數(shù)最少為l(l≥3),則35/498.4平面圖例:

利用定理8.11能夠證實K5和K3,3都不是平面圖.若K5是平面圖,則每個面次數(shù)最少為3.不過由前面定理有10≤3(5-2)＝9這是矛盾,因而K5不是平面圖.類似地,K3,3也不是平面圖.定理8.12

設(shè)G為連通簡單平面圖,則G最小度δ≤5.36/49

8.4平面圖8.4.3平面圖判斷消去插入在圖(1)中,從左到右變換稱為消去2度頂點(diǎn)w.圖(2)中從左到右變換稱為插入2度頂點(diǎn)w.37/498.4平面圖8.4.3平面圖判斷同胚定義8.9

假如兩個圖G1和G2同構(gòu),或經(jīng)過重復(fù)插入或消去2度頂點(diǎn)后同構(gòu),則稱G1與G2同胚.38/49

8.4平面圖8.4.3平面圖判斷初等收縮定義8.10

圖G中相鄰頂點(diǎn)u,v之間初等收縮由下面方法給出;刪除邊(u,v),用新頂點(diǎn)w取代u,v,使w關(guān)聯(lián)u,v關(guān)聯(lián)一切邊(除(u,v)外).v1v2v3v4v1w=v2v439/498.4平面圖8.4.3平面圖判斷庫拉圖斯基定理定理8.13

一個圖是平面圖當(dāng)且僅當(dāng)它不含與K5同胚子圖,也不含與K3,3同胚子圖.定理8.14

一個圖是平面圖當(dāng)且僅當(dāng)它既沒有能夠收縮到K5子圖,也沒有收縮到K3,3子圖.例.

彼得松(森)圖不是平面圖收縮邊(a,f),(b,g),(c,h),(d,i),(e,j)，所得圖為K5,或者令G’=G-{(j,g),(d,c)}，則G’與K3,3同胚40/498.4平面圖例令G’=G-{(d,f),(g,c)},易知G’與K5同胚.令G’’=G-{(a,e),(a,f),(b,g),(g,f)}，則G’’與K3,3同胚41/498.4平面圖8.4.4對偶圖定義8.11

設(shè)平面圖G＝<V,E>,G有r個面,n個頂點(diǎn),m條邊.用以下方法結(jié)構(gòu)G*;(1)在G面Ri中放置G*頂點(diǎn)vi*,這么G*頂點(diǎn)集V*＝{v1*,v2*,...,vr*}；(2)若面Ri和Rj邊界中有公共邊ek,連接對應(yīng)頂點(diǎn)vi*和vj*,得G*邊ek*與ek相交.當(dāng)ek為G中橋且在面Ri邊界中出現(xiàn)時,以Ri中頂點(diǎn)vi*為頂點(diǎn)做環(huán)ek*,ek*為G*中一個環(huán).設(shè)G*邊集為E*,因為G*邊數(shù)與G邊數(shù)相同,則E*＝{e1*,e2*,…,em*},稱G*＝<V*,E*>為G對偶圖.42/49例43/498.4平面圖8.4.4對偶圖注:①

對于任意連通平面圖G,有n*=r,m*=m,r*=n成立,其中n,m,r分別為G頂點(diǎn)數(shù),邊數(shù)和面數(shù).n*,m*,r*分別為G對偶圖G*頂點(diǎn)數(shù),邊數(shù)和面數(shù).②

同構(gòu)平面圖對偶圖,不一定是同構(gòu).G對偶圖G*對偶圖G**不一定與G同構(gòu).③G*是平面圖G對偶圖,若G*與G同構(gòu),則稱G為自對偶圖.④在n-1邊形Cn-1內(nèi)放置一個頂點(diǎn),使這個頂點(diǎn)與Cn-1上全部頂點(diǎn)均相鄰,所得n階簡單圖稱為n階輪圖.n為奇數(shù)輪圖稱為奇階輪圖,n為偶數(shù)輪圖稱為偶階輪圖.44/498.4平面圖8.4.5圖著色①點(diǎn)著色:一個圖用彩色將每個頂點(diǎn)著色,相鄰頂點(diǎn)染不一樣顏色.②

面著色:一個平面圖用彩色將每個面著色,相鄰面染不一樣顏色.

能夠發(fā)覺:面著色能夠轉(zhuǎn)換成其對偶圖點(diǎn)著色.定義8.12

對無環(huán)圖每個頂點(diǎn)涂一個顏色,使相鄰頂點(diǎn)有不一樣顏色,稱為對G一個著色.若能用k種顏色給G頂點(diǎn)著色,就稱對G進(jìn)行了k著色,也稱G是k-可著色.若G是k-可著色,但不是是k-1-可著色,就成G為k色圖,并稱這么k為G色數(shù),記作χ(G),簡記為χ.45/49