周曉聰-zxc-g2basic基本概念_第1頁
周曉聰-zxc-g2basic基本概念_第2頁
周曉聰-zxc-g2basic基本概念_第3頁
周曉聰-zxc-g2basic基本概念_第4頁
周曉聰-zxc-g2basic基本概念_第5頁
已閱讀5頁,還剩50頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

[有向圖]

設(shè)V是一個非空有限集,A是V上的二元關(guān)系。二元組G=(V,A)稱為(有向)圖,V中元素稱為頂點,A中元素稱為?。ㄓ邢蜻叄?。關(guān)系A(chǔ)的關(guān)系圖就是圖G的圖解。[自環(huán)]

A中的自反性圖解為環(huán)形,稱為自環(huán)。[多重邊]

在表達實際問題的圖解中可能出現(xiàn)重復(fù)的關(guān)系定義,稱為多重邊。2.1圖的概念[簡單圖]不出現(xiàn)自環(huán)或多重邊圖解形狀的圖稱為簡單圖。未加特別聲明時,只討論簡單圖。[完全圖]任何兩個頂點之間都有弧相連的圖稱為完全圖。頂點集為V的完全圖GV=(V,VV)。[零圖]

A=或|A|=0時,稱G為零圖。[平凡圖]

|V|=1時,稱G為平凡圖。[圖的階]

|V|稱為圖的階。2.1圖的概念[子圖]

G=(V,A)是G=(V,A)的一個子圖當(dāng)且僅當(dāng):⑴V

V⑵A

是V

上的二元關(guān)系⑶A

A上述定義中,若對u,vV,<u,v>A必有<u,v>A,則稱G是G的一個極大子圖。G是G的子圖;若G

是G的子圖,則G

的任何子圖也是G的子圖;平凡圖是任何圖的子圖2.1圖的概念[生成子圖]

G=(V,A)是G=(V,A)的一個子圖且V=V,則稱G

是G的一個生成子圖或支撐子圖。[導(dǎo)出子圖]

G=(V,A),SV且S,則G中以S為頂點集的極大子圖稱為G中由S導(dǎo)出的子圖。

[補圖]

設(shè)圖G=(V,A),則~G=(V,VVA)稱為G=(V,A)的補圖。

2.1圖的概念[無向圖]

圖G=(V,A),當(dāng)A為對稱關(guān)系時,在圖解上用線段替換成對出現(xiàn)的弧,在集合上用E={(u,v)|u

V,vV,<u,v>A,

<v,u>

A}

替換A,得到無向圖的形式,記為G=(V,E)。無向圖的各種概念完全類似于有向圖的相關(guān)定義。n階無向完全圖記作Kn,其邊數(shù)=n(n1)/2。圖解中既有無向邊,又有有向邊的圖,稱為混合圖?;旌蠄D可以化為有向圖求解。2.1圖的概念[定義]

對G=(V,A),vi

V,分別定義其正關(guān)聯(lián)集、負(fù)關(guān)聯(lián)集、正鄰接集、負(fù)鄰接集如下:

Inc+(vi)={ak|(vj)(vjV

ak=<vi,vj>A)}

●以為vi起點的所有邊構(gòu)成的集合

Inc(vi)={ak|(vj)(vjV

ak=<vj,vi>A)}

●以為vi終點的所有邊構(gòu)成的集合

Adj+(vi)={vj|

vjV(ak)(ak=<vi,

vj>A)} Adj(vi)={vj|

vjV(ak)(ak=<vj,vi>A)}

●與vi相鄰的頂點構(gòu)成的集合2.2點和邊的關(guān)聯(lián)關(guān)系[關(guān)聯(lián)集與鄰接集]

對無向圖G=(V,E),viV,分別定義其關(guān)聯(lián)集、鄰接集如下:

Inc(vi)={ek

|(vj)(vjV

ek=(vi,vj)E)}

Adj(vi)={vj|

vjV(ek)(ek=(vi,

vj)E)}[正負(fù)度]

對G=(V,A),vi

V,分別定義其正度、負(fù)度、度如下:Deg+(vi)=|Inc+(vi)|Deg(vi)=|Inc(vi)|Deg(vi)=Deg+(vi)+Deg(vi)2.2點和邊的關(guān)聯(lián)關(guān)系[無向圖的度]

對G=(V,E),vi

V,定義其度如下:

Deg(vi)=|Inc(vi)|

對簡單圖顯然有:

Deg(vi)<|V|。[定理2-1]

對G=(V,E),有:

對G=(V,A)有同樣的結(jié)論;[推論1]

圖中度為奇數(shù)的頂點必為偶數(shù)個。2.2點和邊的關(guān)聯(lián)關(guān)系[定義]

對無向圖G=(V,E),若其任一頂點的度都為r,則稱G為一個r度正則圖。[例]

n階完全圖是n1度正則圖。[推論2]

3度正則圖中有偶數(shù)個頂點。2.2點和邊的關(guān)聯(lián)關(guān)系圖解法具有不唯一性。例:一一對應(yīng)的兩個關(guān)系,具有相同的代數(shù)性質(zhì),在一定意義上可視為同一。2.3同構(gòu)[同構(gòu)]

圖G=(V,A)和G=(V,A),若存在一一對應(yīng)映射g:VV,使得對

v1,v2

V,v1,v2

A當(dāng)且僅當(dāng)

g(v1),g(v2)

A,則稱G和G同構(gòu)。記為:GG[例]尋求判定圖同構(gòu)的一般方法是圖論的重要課題之一。2.3同構(gòu)[自補圖]

圖G=(V,A),~G是G的補圖。若G~G,則稱圖G是自補的(或自補圖)。[例]2.3同構(gòu)[有向道路]

有向圖G=(V,A)中,一條有向道路指的是一個點與弧的有限非空交替序列

=

v0

a1

v1

a2

v2

……

akvk

(k1)

其中viV(i=0..k),ajA(j=1..k)

且aj=<vj1,vj>(j=0..k)

v0

和vk分別稱為的起點和終點,k稱為的長度。在簡單圖中,也可記作=(v0v1v2……

vp

)或

v0

v1

v2

……

vp

2.4道路與回路[跡]若對任意的ij有ai

aj

,稱之為簡單有向道路/跡。[回路]若v0=vn

,稱之為封閉的。簡單封閉有向道路(閉跡)稱為有向回路。[路]若對任意的ij有vi

vj

,稱之為有向路(路徑)/初級道路/基本道路。[圈]若對任意的ij有vi

vj

而例外地v0=vn,稱之為初級回路/圈。兩個頂點之間若有道路存在則必有路存在。無向圖具有完全類似的定義。

2.4道路與回路[定理2-2]

無向圖G=(V,E),u,v

V且uv。若u,v

之間存在兩條不同的路,則G中存在一條回路。[證明]

(構(gòu)造法)[定理2-3]

無向圖G=(V,E)中每個頂點的度均為偶數(shù),且至少有一個頂點不是孤立點,則

G中存在一條回路。

[證明]

(反證法)設(shè)v不是孤立點,從v出發(fā)的最長簡單路徑經(jīng)過的頂點是v0(=v)v1…vn-1vn,則必存在0i<n使得vn=vi,否則與vn的度是偶數(shù)矛盾。2.4道路與回路[定理2-4]

G=(V,A),|V|=n,則

G中任何初級道路的長度均不大于n1;G中任何初級回路的長度均不大于n

。

[證明](反證法)設(shè)圖中有一條道路,其長度>n1,則其中至少有n+1個頂點標(biāo)號,而圖中只有n個頂點,故其中至少有兩個相同的頂點,即該道路不會是初級道路。2.4道路與回路[可達性]

G=(V,A)中,若從

vi

到vj

存在一條路,則稱從

vi

到vj

是可達的,或稱

vi

可達vj

。對無向圖G=(V,E),結(jié)點間的可達性是對稱的。若規(guī)定任何結(jié)點到其自身可達,則①可達性構(gòu)成V上的一個等價關(guān)系,其對V的每一個劃分塊可以構(gòu)成G的一個導(dǎo)出子圖。②兩個結(jié)點可達當(dāng)且僅當(dāng)它們屬于同一個導(dǎo)出子圖。③上述導(dǎo)出子圖的個數(shù)(或劃分塊個數(shù))稱為G的連通分支數(shù),記為W(G)。2.4道路與回路[連通性]

G=(V,E)中,任意兩點之間可達時,稱G為連通的(連通圖)。

G=(V,A)中,任意兩點之間相互可達時,稱G為強連通的;若去掉弧的方向后得到的無向圖G=(V,s(A))是連通的,則稱原來的G是弱連通的。G中的一個極大連通子圖稱為G的一個連通分支。2.4道路與回路[定理2-5]

G=(V,E),n=|V|,若對任意u,v

V且

uv,都有:Deg(u)+Deg(v)n1,則G連通。[證明](反證法)設(shè)G可分為不連通的兩部分G1=(V1,E1)和G2=(V2,E2),選取

uV1,vV2

則Deg(u)<|V1|,Deg(v)<|V2|,故Deg(u)+Deg(v)<|V1|+|V2|=n,與Deg(u)+Deg(v)n1矛盾。注意:未加特別聲明時,我們討論的都是簡單圖。2.4道路與回路[Euler回路]

若連通圖G=(V,E)中存在一條簡單回路(無重復(fù)邊)經(jīng)過G的所有邊,則稱該回路為G中的一條Euler回路。存在Euler回路的圖稱為Euler圖。[定理2-6-1]

設(shè)有連通圖G=(V,E),則下述命題等價:

(1)G是一個Euler圖;

(2)G的每一個頂點的度是偶數(shù);[證明](見戴一奇教材p16定理2.3.1)2.5Euler回路注意定理中對圖的連通性的假定;Euler回路經(jīng)過圖的所有邊一次且僅僅一次。定理對非簡單圖也成立;定理的證明過程給出了為一個Euler圖構(gòu)造Euler回路的構(gòu)造算法。[定理2-7]

設(shè)連通圖G=(V,E)中恰有2k個頂點度為奇數(shù),k1。則G的邊可劃分成k條簡單道路。[證明](構(gòu)造法,見戴一奇教材p17例2.3.3)2.5Euler回路[有向圖的Euler回路]

若有向連通圖G=(V,A)中存在一條簡單有向回路經(jīng)過G的所有弧,則稱該回路為G中的一條Euler回路,稱該圖為Euler有向圖。[定理2-6-2]

設(shè)連通有向圖G=(V,A),則下述命題等價:

(1)G是一個Euler有向圖;

(2)G的每一個頂點的入度等于出度;[證明](略)2.5Euler回路[旋轉(zhuǎn)鼓的設(shè)計]

見戴一奇教材p17例2.3.42.5Euler回路[Hamilton路]

若連通圖G=(V,E)中存在一條初級道路(無重復(fù)頂點)經(jīng)過G中每個頂點一次,則稱該道路為G中的一條Hamilton路。存在Hamilton回路的圖稱為Hamilton圖。Hamilton路經(jīng)過圖的所有頂點一次且僅僅一次。引入記號:G=(V,E),SV。從G中去除S中的頂點及其關(guān)聯(lián)邊得到的G的子圖記為GS。2.6Hamilton道路[定理2-8]

若G=(V,E)是一個Hamilton圖,SV且S,則G的子圖GS的連通分支數(shù)

W(GS)|S|[證明]

記G中H-回路為C,C中包含了G中所有頂點。考察CS:每從C中去除屬于S的一個頂點,連通分支數(shù)至多增加1(第一次以及當(dāng)該頂點處于邊緣時操作不會增加連通分支數(shù)),故

W(CS)|S|

而G可視為向C中添加邊構(gòu)成,故W(GS)W(CS)

所以W(GS)|S|2.6Hamilton道路定理給出了Hamilton圖的必要條件,可用于對Hamilton圖的否定性判定,但對Hamilton圖的肯定性判定無效。2.6Hamilton道路[例]

圖G12345786令S={2,6},則W(GS)=3。而|S|=2,即W(GS)>|S|故圖G不可能是Hamilton圖。134578圖G-S2.6Hamilton道路[例]

Petersen圖。|V|=10,對任何SV,都有W(GS)S,但Petersen圖不是Hamilton圖。2.6Hamilton道路[定理2-9]

簡單圖G=(V,E),n=|V|,若對任一對不相鄰頂點u,vV,uv,有Deg(u)+Deg(v)n1,則G中存在一條Hamilton路。[證明]見戴一奇教材p18定理2.4.1[推論]

上述有Deg(u)+Deg(v)n時,G為Hamilton圖。[證明]見戴一奇教材p19推論2.4.12.6Hamilton道路定理及其推論給出了Hamilton圖成立的充分條件,可用于對Hamilton圖的肯定性判定。Hamilton圖成立的充要條件尚未得到解決,是圖論求解的課題之一。2.6Hamilton道路[鄰接矩陣]

對有向圖G=(V,R),n=|V|,構(gòu)造矩陣A=(aij)nn,其中[定理2-10]

設(shè)A1、A2分別為G1、G2的鄰接矩陣,則G1G2當(dāng)且僅當(dāng)存在置換矩陣P,使得A1=PA2PT。

aij

=1<vi,vj>R0其他稱A為圖G的鄰接矩陣。2.7圖的鄰接矩陣[定理2-11]

設(shè)Ann是G的鄰接矩陣,則連接vi與vj(ij)的長度為l的路徑的條數(shù)等于Al的第i行第j列的元素的數(shù)值。[證明](數(shù)學(xué)歸納法:對l歸納)2.7圖的鄰接矩陣[道路矩陣]

對有向圖G=(V,R),n=|V|,構(gòu)造矩陣P=(pij)nn,其中

pij

=1若vi

到vj可達0其他稱P為圖G的道路矩陣(或可達矩陣)。2.8道路矩陣及Warshall算法[算法]

求給定圖G的道路矩陣P

設(shè)A為G的鄰接矩陣,B=A+A2+A3+…+An1,由[定理2-11],bij表示由vi至vj

,長度為1或2或…或n1的路徑數(shù)目,即為由vi至vj的全部路徑總和。令

pij

=1若bij

>00其他可求得G的道路矩陣P。

算法復(fù)雜度O(n4)2.8道路矩陣及Warshall算法[定義]

二值元素的邏輯運算:

00=0,01=10=1,11=100=0,01=10=0,11=1[定義]

二值矩陣的邏輯運算。設(shè)有矩陣A=(aij),B=(bij),矩陣元素值域為{0,1},定義運算:2.8道路矩陣及Warshall算法[定義]

A(k)=A(k1)

A(k2),A(1)=A注意A(k)與Ak

的區(qū)別[定理2-12]

設(shè)Ann是圖G的鄰接矩陣,若從vi

到vj存在長度為l的路,則[A(l)]ij

=1,否則[A(l)]ij

=0。[證明]對l作歸納;或直接引用[定理2-11]。2.8道路矩陣及Warshall算法[Warshall算法]

設(shè)Ann是圖G的鄰接矩陣,求G的道路矩陣P。PAi1j1pjk

pjk(pji

pik),k=1...njj+1,若jn,轉(zhuǎn)4i

i+1,若

in,轉(zhuǎn)3Stop計算復(fù)雜度O(n3)2.8道路矩陣及Warshall算法[例]

圖G的鄰接矩陣A如右,使用Warshall算法求G的道路矩陣P。[解]PA2.8道路矩陣及Warshall算法(1)i=1j

=1,2,3,4

增量方向i

=1矩陣元素處理次序:p11,

p12,

p13,

p14,

p21,

p22,……

p31,……

p41,……,p44,2.8道路矩陣及Warshall算法如:p11

=p11(p1i

pi1)=p11(p11

p11)=0p12

=p12(p2i

pi2)=p12(p21

p12)=1p13

=p13(p3i

pi3)=p13(p31

p13)=0…………結(jié)果為2.8道路矩陣及Warshall算法考察第

i次循環(huán)。第i

列的0元對應(yīng)的行,pji=0,故pjk

=pjk(pji

pik)=pjk(0

pik)=pjk;第i

列的1元對應(yīng)的行,pji=1,故pjk

=pjk(pji

pik)=pjk(1

pik)=pjkpik

,即將該行與第i行做“或”運算。(2)i=22.8道路矩陣及Warshall算法[表上作業(yè)法]第i

次循環(huán)時,將第i

行分別“疊加”到第i列的非0元對應(yīng)的那些行,“疊加”運算是一對行向量各個對應(yīng)元素的邏輯“或”運算。(i=1..n)如上例:

i=22.8道路矩陣及Warshall算法非0元

i[例]

i=12.8道路矩陣及Warshall算法

i

i=22.8道路矩陣及Warshall算法

i

i=42.8道路矩陣及Warshall算法

i

i=52.8道路矩陣及Warshall算法

i[進一步的討論]定義運算“PQ”:(PQ)ij=pijqij,P、Q為同階矩陣。2.8道路矩陣及Warshall算法則:(PPT)ij=pij

pji

對行列重新編號得:2.8道路矩陣及Warshall算法可見,{v1},{v3}以及{v2,v4,v5}的導(dǎo)出子圖分別構(gòu)成強連通分量。v1v2v3v4v52.8道路矩陣及Warshall算法[旅行商問題]已知n個城市,任兩個城市之間都有無向路相通,求一條經(jīng)過所有城市一次且僅僅一次,并且總路

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論