matlab圖與網(wǎng)絡(luò)分析模型選講課件

第七章圖與網(wǎng)絡(luò)分析模型選講一、圖論的基本知識(shí)1.圖的概念定義圖G(V,E)是指一個(gè)二元組(V(G),E(G))，其中:

(1)V(G)={v1,2v,…,nv}是非空有限集，稱(chēng)為頂點(diǎn)集，(2)E(G)是V(G)中的元素對(duì)(vi

j,v)組成的集合稱(chēng)為邊集。圖G：V(G)={v,1v2

3,4v,v}E(G)=

{e

1,2e3,4e5

6,e

,e

,e

}e3=(v1,3v

)若圖G是的邊是有方向的，稱(chēng)G是有向圖，有向圖的邊稱(chēng)為有向邊或弧。常用術(shù)語(yǔ)

e6

v2邊和它的兩端點(diǎn)稱(chēng)為互相關(guān)聯(lián).

e3

e1e2與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱(chēng)

v4為相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn)

e4

v3點(diǎn)關(guān)聯(lián)的兩條邊稱(chēng)為相鄰的邊.

v53)端點(diǎn)重合為一點(diǎn)的邊稱(chēng)為環(huán).e5若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱(chēng)為重邊．既沒(méi)有環(huán)也沒(méi)有重邊的圖，稱(chēng)為簡(jiǎn)單圖．v16)若圖G的每一條邊e都賦以一個(gè)實(shí)數(shù)w(e)，稱(chēng)w(e)為邊e的權(quán)，G連同邊上的權(quán)稱(chēng)為賦權(quán)圖,記為：G(V,E,W)，W={w(e)|

e∈E}v27)圖G的中頂點(diǎn)的個(gè)數(shù)，352v4v1v3稱(chēng)為圖G的階；圖中與某個(gè)頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，稱(chēng)為該頂點(diǎn)的度。8）完全圖：若無(wú)向圖的任意兩個(gè)頂點(diǎn)之間都存在著一條邊，稱(chēng)此圖為完全圖。2.圖的矩陣表示鄰接矩陣:(以下均假設(shè)圖為簡(jiǎn)單圖).圖G的鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣：A=(a

i)j，或權(quán)值，若vi與vj

相鄰其中：或∞，若vi與vj不相鄰無(wú)向圖G鄰接矩陣A=(aij)v2v4v1v3v2543v4v11v3有向圖G鄰接矩陣A=(aij)v2v4v1v3v2543v4v11v3二、最大流問(wèn)題定義：設(shè)G(V,E)為有向圖，若在每條邊e上定義一個(gè)非負(fù)權(quán)c，則稱(chēng)圖G為一個(gè)網(wǎng)絡(luò)，稱(chēng)c為邊e的容量函數(shù)，記為c(e)。若在有向圖G(V,E)中有兩個(gè)不同的頂點(diǎn)vs與vt，若頂點(diǎn)vs只有出度沒(méi)有入度，稱(chēng)vs為圖G的源，若頂點(diǎn)vt只有入度沒(méi)有出度，稱(chēng)為G的匯，若頂點(diǎn)v既不是源也不是匯，稱(chēng)為v中間頂點(diǎn)。v1

v284335vtvs777v4v3設(shè)u,v網(wǎng)絡(luò)G(V,E)的相鄰頂點(diǎn)，邊(u,v)上的函數(shù)f(u,v)稱(chēng)為邊(u,v)上的實(shí)際流量；若對(duì)網(wǎng)絡(luò)G(V,E)的任意相鄰頂點(diǎn)u,v均成立：0≤

f(u,v)

≤

c(u,v)

，v3v1

v28稱(chēng)該網(wǎng)絡(luò)為相容網(wǎng)絡(luò)。若v為網(wǎng)絡(luò)G(V,E)的中間頂點(diǎn)，4vs有：335vt777v4網(wǎng)絡(luò)的總流量為從源vs流出的總流量：流入?yún)Rvt總流量：v1v284335vtvs777v4v3定義：設(shè)網(wǎng)絡(luò)G(V,E)為相容網(wǎng)絡(luò)，u,v是G的相鄰頂點(diǎn)，

G的容量函數(shù)為c(u,v)，實(shí)際流量函數(shù)為f(u,v)，s

v和t

v分別為G(V,E)的源和匯，V(f)為從源vs

流出的總流量，若：則稱(chēng)該網(wǎng)絡(luò)稱(chēng)為守恒網(wǎng)絡(luò)。守恒網(wǎng)