《離散數(shù)學(xué)》課件：4-1-圖

第四章

圖與網(wǎng)絡(luò)

§4.1

圖

§4.2

樹

§4.3

有向圖

Euler路

§4.4

Hamilton圖

§4.5

平面圖

§4.6

匹配

二部圖

§4.7

Konig無限性引理

§4.1圖(Graphs)

LeonhardEuler(公元1707-1783年)歐拉1707年出生在瑞士的巴塞爾城，13歲就進巴塞爾大學(xué)讀書，得到當(dāng)時最有名的數(shù)學(xué)家約翰.伯努利的精心指導(dǎo)。他從19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。1733年，年僅26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長，直到1766年，重回彼得堡，沒有多久，完全失明．歐拉在數(shù)學(xué)上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。哥尼斯堡七橋問題能否從某個地方出發(fā)，穿過所有的橋各一次后再回到出發(fā)點?1736年歐拉把研究7橋問題的結(jié)果寫成論文發(fā)表標(biāo)志著圖論學(xué)科的誕生.§4.1.1圖的基本概念定義4.1.1

G＝(P,L)稱為圖。如果P是點的非空集合，L是連接某些不同點對的邊集合，并且任意一對不同點之間最多有一條邊。當(dāng)P為有限集時，G稱為有限圖。設(shè)G＝(P,L)是一個圖，今后，我們用P(G)表示G的(節(jié))點集，用L(G)表示G的邊集。設(shè)lL(G)，并假設(shè)l是連接G中點u，點v的邊，則稱u，v是l的端點，并稱u與v相鄰。若l1L(G)，l2L(G)。且l1和l2有公共的端點，則稱邊l1與l2相鄰。有時，在不致引起混亂的情況下，將l記為uv。

§4.1.1圖的基本概念沒有任何邊(L(G)=)的圖稱為零圖；只有一個點的圖稱為平凡圖；任意兩點之間都有邊的圖稱為完全圖。(a)圖(b)零圖(c)完全圖§4.1.1圖的基本概念容許有平行邊和反身邊的圖稱為無向圖

不允許有反身邊和平行邊的圖稱為簡單圖

圖的同構(gòu)(isomorphism)

稱圖G和H是同構(gòu)的。如果存在P(G)到P(H)的雙射，使對任意的u,vP(G),u與v在G中相鄰,當(dāng)且僅當(dāng)(u)與(v)在H中相鄰。我們把同構(gòu)的圖看成是一個圖

圖的同構(gòu)(isomorphism)

abcdd1a1b1c1abcdd1a1b1c1abcdd1a1b1c1圖的同構(gòu)(isomorphism)

定義4.1.2設(shè)G，H是圖，如果P(H)P(G)，L(H)L(G)。則稱H是G的子圖，G是H的母圖。如果H是G的子圖，并且P(H)＝P(G)，則稱H是G的支撐子圖。如果H是G的子圖，且L(G)中兩個端點都在P(H)中的邊都在L(H)中，則稱H為點集P(H)在G中誘導(dǎo)的子圖。

abcdd1a1b1c1母圖abcda1b1子圖abcdd1a1b1c1支撐子圖abcdd1b1誘導(dǎo)子圖定義4.1.3設(shè)G是圖，vP(G)，L(G)中以v為端點的邊的條數(shù)稱為點v的度，記為dG(v)。abcdd1a1b1c1dG(a1)=0;

dG(c)=1;

dG(a)=2;dG(c1)=3;今后，為簡便計，有時也將圖G中的點v，邊l，寫成vG，lG。圖的表示關(guān)聯(lián)矩陣相鄰矩陣(鄰接矩陣)關(guān)聯(lián)矩陣(incidencematrix)

設(shè)G＝(P，L)是有限圖，集合P的元數(shù)為m，集合L的元數(shù)為n，不妨設(shè)P(G)＝v1，…，vm，L(G)＝l1，…，ln。矩陣M(G)＝aij稱為G的關(guān)聯(lián)矩陣，其中顯然，M(G)是m×n階矩陣。

例v1v2v3v4l1l2l3l4l5相鄰矩陣(adjacencymatrix)設(shè)G＝(P，L)是有限圖，集合P的元數(shù)為m，不妨設(shè)P(G)＝v1，…，vm。矩陣A(G)＝bij稱為G的相鄰矩陣，其中顯然，A(G)是m×m階矩陣。

例v1v2v3v4定理4.1.1(握手定理)設(shè)G＝(P,L)是有限圖，不妨設(shè)L(G)含有m個元素，于是證明：設(shè)M(G)是G的關(guān)聯(lián)矩陣，因為G中某點v的度dG(v)恰是M(G)中的代表點v的那一行中1的個數(shù)，故

而M(G)中每列恰有兩個1，M(G)共m列，故M(G)中1的個數(shù)為2m。所以定理4.1.2任一有限圖中，奇數(shù)度的點的個數(shù)為偶數(shù)。是偶數(shù)。因為是偶數(shù)。所以

是偶數(shù)，故S1的元數(shù)是偶數(shù)。

證明：設(shè)S1，S2分別是圖G中有奇數(shù)度的點和有偶數(shù)度的點的集合，由定理4.1.1知定義4.1.4設(shè)G＝(P，L)是圖，v，v’是G中兩點。由G中點組成的序列(v0,v1,…,vn)稱為從v到v’的長度為n的路，如果

(1)v0=v，vn=v’；

(2)vi與vi+1相鄰，0

i＜n。

這里v，v’是圖G中未必不同的兩點，v0,v1,…,vn中也允許有重復(fù)。

定義4.1.5設(shè)G＝(P，L)是圖，(v0,v1,…,vn)是G中從v0到vn的路，稱此路為簡單路，如果

1）v0,…,vn－1互不相同；

2）v1,…,vn互不相同。

顯然，一條簡單路（v0,v1,…,vn），除v0與vn可以相同外，其它任意兩點都不相同。

定義4.1.6設(shè)G＝(P，L)是圖。G中從點v到自身的其長度不小于3的簡單路，稱為回路。

例

(a,b,c,d)是一條長度為3的路(簡單路)(a,b,c,a,d,c,b)是一條長度為6的路(不是簡單路)(a,b,c,a)、(a,c,d,a)、(a,b,c,d,a)都是回路。abcd定義

設(shè)G＝(P，L)是圖，G中兩點u,v，如果從u到v有一條路，則稱u與v是相連的。我們認為點v與自身是相連的，則顯然G中兩點之間的相連關(guān)系是一個等價關(guān)系。在此等價關(guān)系下，集合P(G)必分成一些等價類，不妨設(shè)為S1,…,Sn,…。顯然，每一個Si和G中所有以Si中的點為端點的邊一起，組成G的一個子圖Gi。每個Gi稱為G的一個連通分支。如果圖G僅有一個分支，則稱圖G是連通的。

對于圖G，我們用W(G)記其連通分支數(shù)。顯然，一個圖G是連通的，當(dāng)且僅當(dāng)G中任意兩點都是相連的。§4.1.2權(quán)圖Dijkstra算法定義4.1.7設(shè)G＝(P,L)是有限圖，如果對L(G)中任一條邊l，都規(guī)定一個實數(shù)w(l)附在其上，則稱G為有限權(quán)圖(網(wǎng)絡(luò))，稱w(l)為邊l的權(quán)。規(guī)定w(uu)=0(其中uP(G)),w(uv)＝∞(其中uvL(G))。例:權(quán)圖

w(ab)=5，w(aa)=0，w(bd)=∞，w(ad)=8abcd5124820定義在一個權(quán)圖G中，任給兩點u，v，從u到v可能有多條路，在這些路中，所帶的權(quán)和最小的那條路稱為圖中從u到v的最短路。這條最短路所帶的權(quán)和稱為u到v的距離，記為d(u,v)。

顯然兩點間的最短路一定簡單路（為什么？），所以在網(wǎng)絡(luò)中找最短路只需在簡單路中找。

例:最短路

a到c的路有：(a,b,c)長度為5+4=9;(a,c)長度為12;(a,d,c)長度為8+20=28。最短路為：(a,b,c)，因此a到c的距離為9abcd5124820Dijkstra算法定義設(shè)G是有限權(quán)圖，SP(G)，u0S，S’=P-S，定義u0到S’的距離為

實現(xiàn)上述距離的路稱為u0到S’的最短路。上述點到點集距離的定義等價于

例:

如圖所示，令S={a,b,f}，則S’={c,d,e}，求d(a,S’)？abcd125610fe1143S’S取u=b，則d(a,b)=6，w(bc)=5，w(bd)=∞，w(be)=4，取u=f，則d(a,f)=1，w(fc)=1，w(fd)=∞，w(fe)=2abcd125610fe1143設(shè)u0=a，

取u=a，則w(ac)=∞，w(ad)=10，w(ae)=∞，因而d(a,S’)=2，a到S’的最短路為（a,f,c）。Dijkstra算法指導(dǎo)思想：設(shè)u0P,v0P,要求u0到v0點的距離，我們通過求u0到圖中其它各點的距離。先把P分成兩個子集，一個設(shè)為S,S={v|vP,u0到v的距離已求出}，另一個是S’=P-S。顯然，S，因為至少u0S，算法不斷擴大S，直到S=P(或者v0S)對任意的vP-{u0}，設(shè)l(v)表示從u0僅經(jīng)過S中點到v的最短路的帶權(quán)長度。若不存在這樣的路，置l(v)=∞。Dijkstra算法(1)初始化，令S={u0}，S’=P-S，對S’中每一個定點v,令l(v)=w(u0,v)；(2)找到uiS’，滿足(3)若S=P，則終止；否則令S=S∪{ui}，S’=S’-{ui},對S’中每一個定點v，計算轉(zhuǎn)到(2)。Dijkstra算法bacd762fe81443472356321u0gDijkstra算法執(zhí)行過程l(g)l(f)l(e)l(d)l(c)l(b)l(a)S’S712∞∞48abcdefgu01724∞48abcdegu0f273∞48abcdgu0fe36948abcgu0fed4696acgu0fedb569cgu0fedba69cu0fedbag7u0fedbagc8Dijkstra算法bacd762fe81443472356321u0g定理4.1.3設(shè)G＝(P,L)是有限連通權(quán)圖，SP(G)，S={u0,u1,…,uk}，并且已經(jīng)知道了u0分別到u1,…,uk的距離與最短路l1,…,lk。又設(shè)S’＝P－S，d(u0,S’)={d(u0,u)+w(u,v)}是u0到集合S’的距離，lk+1=(u0,u1’,…,us’,uk+1)是實現(xiàn)d(u0,S’)的路，其中u0,u1’,…,us’S，uk+1S’。則u0到uk+1的距離d(u0,uk+1)=d(u0,S’)，且lk+1是u0到uk+1的最短路。證明：

我們用|l|表示路l上所帶權(quán)的和，則|lk+1|=d(u0,S’)。設(shè)l=(u0,v1,…,vr,uk+1)是u0到uk+1的任意一條路，以下證明|l||lk+1|。1)若v1S’，即l的第一步就進入S’，則|l|=w(u0,v1)+w(v1,v2)+…+w(v