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

圖與網(wǎng)絡(luò)分析第1頁，共34頁，2023年，2月20日，星期四§1.圖的基本知識一、圖1、圖：由一些點及一些點的連線所組成的圖形。若V={V1,V2,…,Vn}是空間n個點的集合

E={e1,e2,…,em}是空間m個點的集合滿足1)V非空

2)E中每一條線ei是以V中兩個點Vs,Vt為端點

3)E中任意兩條線之間除端點之外無公共點.則由V、E構(gòu)成的二元組合G=(V，E)就是圖。2、子圖：已知圖G1（V1，E1）若V1V，E1E

則稱圖G1（V1，E1）是圖G=(V，E)的子圖3、若在圖G中，某個邊的兩個端點相同，則稱e是環(huán)。4、多重邊：圖中某兩點之間有多余一條的邊，稱之為多重邊。多重圖：含有多重邊的圖。5、簡單圖：無環(huán)、無多重邊的圖。第2頁，共34頁，2023年，2月20日，星期四

二、連通圖1、鏈：給定一個圖G=(V,E)，一個點邊的交錯序列(vi1,ei1,vi2,ei2,…,vik-1,eik-1,vik)，如果滿足eit=[vit,vit+1](t=1,2,…,k-1)，則稱為一條聯(lián)結(jié)vi1和vik的鏈，稱點vi2,vi3,…,vik-1為鏈的中間點。2、圈：鏈(vi1,vi2,…,vik)中，若vi1=vik,，則稱之為一個圈。3、簡單鏈：若鏈(vi1,vi2,…,vik)中，點vi1,vi2,…,vik都是不同的，則稱之為簡單鏈。4、連通圖：圖G中，若任何兩個點之間，至少有一條鏈。

第3頁，共34頁，2023年，2月20日，星期四三、樹1、定義：一個無圈的連通圖稱為樹。2、樹的性質(zhì)：1）圖G是樹的充分必要條件是任意兩個頂點之間恰有一條鏈。2）在樹中去掉任意一條邊則構(gòu)成一個不連通圖，不再是樹；在樹中不相鄰的兩點之間添加一條邊，恰好形成了一個圈，也就不再是樹。3）樹中頂點的個數(shù)為P，則其邊數(shù)必為P-1。第4頁，共34頁，2023年，2月20日，星期四3、支撐樹：設(shè)圖T=(V,E’)是圖G（V，E）的支撐子圖，如果圖T=(V,E’)是一個樹，則稱T是G的一個支撐樹。4、尋找支撐樹的方法1）破圈法：在圖中任取一個圈，從圈中去掉任一邊，對余下的圖重復(fù)上述操作，即可得到一個支撐樹。2）避圈法：每一步選取與已選的邊構(gòu)不成圈的邊，直到不能繼續(xù)為止。第5頁，共34頁，2023年，2月20日，星期四

5、最小支撐樹1）賦權(quán)圖：給圖G=(V,E)，對G中的每一條邊[vi,vj]，相應(yīng)地有一個數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。2）最小支撐樹：如果T=(V,E’)是G的一個支撐樹，稱E’中所有邊的權(quán)之和為支撐樹T的權(quán)，記為w(T)，即

w(T)=Σwij(vi,vj)∈T如果支撐樹T*的權(quán)w(T*)是G的所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹(簡稱最小樹)w(T*)=minw(T)T第6頁，共34頁，2023年，2月20日，星期四3）求最小樹的方法：方法一(避圈法)開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。方法二(破圈法)任取一個圈，從圈中去掉一條權(quán)最大的邊。在余下的圖中，重復(fù)這個步驟，一直到一個不含圈的圖為止，這時的圖便是最小樹。

例用破圈法求下圖的最小樹12222312222333445第7頁，共34頁，2023年，2月20日，星期四

四、一筆劃問題1、次：圖中的點V，以V為端點的邊的個數(shù)，稱為V的次，記為d(V)。2、定理1：圖G=(V,E)中，所有點的次之和是邊數(shù)的兩倍，即設(shè)q邊數(shù)，則Σd(vi)=2q，其中viV3、奇點：次為奇數(shù)的點。否則稱為偶點。4、任一圖中，奇點的個數(shù)為偶數(shù)。5、一筆劃：可以一筆劃：沒有或僅有兩個奇次點的圖形如沒有奇次點：任取一點，它既是起點又是終點。兩個奇次點：分別選為起點和終點。第8頁，共34頁，2023年，2月20日，星期四五、有向圖1、無向圖：G（V，E）點集+邊集2、弧：點與點之間有方向的邊，叫做弧?；〖篈={a1,a1,…,am}3、有向圖：由點及弧所構(gòu)成的圖，記為D=(V,A)，V,A分別是D的點集合和弧集合。4、環(huán)：某一條孤起點=終點，稱為環(huán)。5、基礎(chǔ)圖：給定一個有向圖D=(V,A)，從D中去掉所有弧上的箭頭，所得到的無向圖。記之為G(D)。第9頁，共34頁，2023年，2月20日，星期四

6、鏈：設(shè)(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一個點弧交錯序列，如果這個序列在基礎(chǔ)圖G(D)中所對應(yīng)的點邊序列是一條鏈，則稱這個點弧交錯序列是D的一條鏈。7、路：如果(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一條鏈，并且對t=1,2,…,k-1，均有ait=(vit,vit+1)，稱之為從vi1到vik的一條路。8、回路：若路的第一個點和最后一點相同，則稱之為回路。第10頁，共34頁，2023年，2月20日，星期四六、圖的矩陣表示1、網(wǎng)絡(luò)（賦權(quán)圖）G=（V，E），其邊（vi,vj）有權(quán)wij,構(gòu)造矩陣A=（aij）n×n,其中：

wij（vi,vj）∈E0其他稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。2、對于圖G=（V，E），∣V∣=n,構(gòu)造一個矩陣A=（aij）n×n,其中：

wij（vi,vj）∈E0其他稱矩陣A為網(wǎng)絡(luò)G的權(quán)。第11頁，共34頁，2023年，2月20日，星期四第二節(jié)最短路問題一、引例：如下圖中V1：油田，V9：原油加工廠求使從V1到V9總鋪路設(shè)管道最短方案。

V1V4V2V3V6V9V8V7V542466234442第12頁，共34頁，2023年，2月20日，星期四二、最短路算法1、情況一：wij≥0(E.W.Eijkstra算法)原理：Bellman最優(yōu)性定理方法：圖上作業(yè)法（標(biāo)號法）標(biāo)號：對于點,若已求出到Vi的最短值，標(biāo)號（αi,βi)

αi：表示到的最短路值

βi:表示最短路中最后經(jīng)過的點標(biāo)號法步驟：1）給V1標(biāo)號(0,Vs)2）把所有頂點分成兩部分,X：已標(biāo)號的點；X’未標(biāo)號的點考慮與已標(biāo)號點相鄰的弧是存在這樣的弧（Vi，Vj）,Vi∈X,Vj∈X’若不存在，此問題無解，否則轉(zhuǎn)3）3）選取未標(biāo)號中所有入線的起點與未標(biāo)號的點Vj進(jìn)行計算:min{αi+wij}=αj并對其進(jìn)行標(biāo)號(αj,Vi)，重復(fù)2）第13頁，共34頁，2023年，2月20日，星期四2、情況二：wij≤0設(shè)從V1到Vj(j=1,2,…,t)的最短路長為P1jV1到Vj無任何中間點P1j（1）=wijV1到Vj中間最多經(jīng)過一個點

P1j（2）=min{P1j（1）+wij}V1到Vj中間最多經(jīng)過兩個點

P1j（3）=min{P1j（2）+wij}…….V1到Vj中間最多經(jīng)過t-2個點

P1j（t-1）=min{P1j（t-2）+wij}終止原則：1）當(dāng)P1j（k）=P1j（k+1）可停止，最短路P1j*=P1j（k）2）當(dāng)P1j（t-1）=P1j（t-2）時，再多迭代一次P1j（t），若P1j（t）=P1j（t-1），則原問題無解，存在負(fù)回路。第14頁，共34頁，2023年，2月20日，星期四例：求下圖所示有向圖中從v1到各點的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第15頁，共34頁，2023年，2月20日，星期四

wijd(t)(v1,vj)v1v2v3v4v5v6v7v8v1v2

v3

v4v5v6v7v8025-30-2406400-30720320t=1t=2t=3t=4t=5t=6025-3020-3611020-36615020-3361410020-336910020-336910說明：表中空格處為+。第16頁，共34頁，2023年，2月20日，星期四例設(shè)備更新問題制訂一設(shè)備更新問題，使得總費用最小

第1年第2年第3年第4年第5年購買費1314161924

使用年數(shù)0-11-22-33-44-5

維修費810131827

[解]設(shè)以vi(i=1,2,3,4,5)表示“第i年初購進(jìn)一臺新設(shè)備”這種狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi,

vj)表示“第i年初購置的一臺設(shè)備一直使用到第j年初”這一方案，以wij表示這一方案所需購置費和維護費之和。第17頁，共34頁，2023年，2月20日，星期四這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就可歸結(jié)為從圖中找出一條從v1到v6的最短路問題。用Dijkstra標(biāo)號法，求得最短路為v1v3v6

即第一年初購置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費用最少，為78。第18頁，共34頁，2023年，2月20日，星期四v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31,V1)(44,V1)(62,V1)(78,V3)第19頁，共34頁，2023年，2月20日，星期四第三節(jié)最大流問題

如下是一運輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234第20頁，共34頁，2023年，2月20日，星期四一、基本概念和基本定理1、網(wǎng)絡(luò)與流定義1：給定一個有向圖D=(V,A),在V中有一個發(fā)點vs和一收點vt，其余的點為中間點。對于每一條弧(vi,vj),對應(yīng)有一個c(vi,vj)0,(cij)稱為弧的容量。這樣的有向圖稱為網(wǎng)絡(luò)。記為D=(V,A,C)。網(wǎng)絡(luò)的流：定義在弧集合A上的一個函數(shù)f={f(vi,vj)}，稱f(vi,vj)為弧(vi,vj)上的流量，簡記fij。第21頁，共34頁，2023年，2月20日，星期四2、可行流與最大流定義2滿足下列條件的流稱為可行流：1)0fijcij2)平衡條件：中間點fij=fji(vi,vj)A(vj,vi)A發(fā)點vsfsj–fjs=v(f)(vs,vj)A(vj,vs)Aftj–fjt=–v(f)(vt,vj)A收點vt，(vj,vt)A式中v(f)稱為這個可行流的流量，即發(fā)點的凈輸出量（或收點的凈輸入量）。第22頁，共34頁，2023年，2月20日，星期四最大流問題：求一流{fij}滿足0fijcij

v(f)i=sfij–fji=0is，t–v(f)i=t且使v(f)達(dá)到最大。第23頁，共34頁，2023年，2月20日，星期四3、增廣鏈給定可行流f={fij}，使fij=cij的弧稱為飽和弧，使fij<cij的弧稱為非飽和弧，把fij=0的弧稱為零流弧，fij>0的弧稱為非零流弧。若是網(wǎng)絡(luò)中連接發(fā)點vs和收點vt的一條鏈，定義鏈的方向是從vs到vt，則鏈上的弧被分成兩類：前向?。夯〉姆较蚺c鏈的方向一致全體+后向弧：弧的方向與鏈的方向相反全體—定義3設(shè)f是一可行流，是從vs到vt的一條鏈，若滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)+上，0fij<cij

在弧(vi,vj)—上，0<fijcij第24頁，共34頁，2023年，2月20日，星期四

4、截集與截量定義4給定網(wǎng)絡(luò)D=(V,A,C)，若點集V被剖分為兩個非空集合V1和V1，使vsV1，vtV1，則把弧集(V1,V1)稱為是（分離vs和vt的）截集。截集是從vs到vt的必經(jīng)之路。定義5給定一截集(V1,V1)，把截集(V1,V1)中所有弧的容量之和稱為這個截集的容量(截量),記為C(V1,V1)。v(f)C(V1,V1)第25頁，共34頁，2023年，2月20日，星期四若對于一可行流f*，網(wǎng)絡(luò)中有一截集(V1*,V1*)，使得v(f*)=C(V1*,V1*)，則f必是最大流，而(V1*,V1*)，必定是容量最小的截集，即最小截集。定理1可行流f*是最大流的充要條件是不存在關(guān)于f*的最大流。若f*是最大流，則網(wǎng)絡(luò)中必存在一個截集(V1*,V1*)，使得

v(f*)=C(V1*,V1*)定理2任一網(wǎng)絡(luò)D中，從vs到vt的最大流的流量等于分離vs，vt的最小截集的截量。第26頁，共34頁，2023年，2月20日，星期四步驟：2、標(biāo)號過程1、選取一個可行流（可選擇零流弧）從Vs出發(fā)，在前向弧上(vi,vj)，若fij<cij，則給vj標(biāo)號(vi,l(vj))，其中l(wèi)(vj)=min[l(vi)，cij–fij]。在后向弧(vj,vi)上，若fji>0，則給vj標(biāo)號(–Vi,l(vj))，其中l(wèi)(vj)=min[l(vi)，fji]。二、尋找最大流的標(biāo)號法(FordFulkerson)思想：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增大流量，使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。第27頁，共34頁，2023年，2月20日，星期四

3、若標(biāo)號延續(xù)到vt，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整階段4，否則當(dāng)前流即為最大流。4、調(diào)整過程令調(diào)整量為=l(vt)令fij+

(vi,vj)+fij′=fij–(vi,vj)—

fij(vi,vj)去掉所有的標(biāo)號，對新的可行流f′={fij′}，重新進(jìn)入標(biāo)號過程。第28頁，共34頁，2023年，2月20日，星期四可結(jié)合下圖理解其實際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第29頁，共34頁，2023年，2月20日，星期四vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例求下列網(wǎng)絡(luò)的最大流與最小截集。[解]一、標(biāo)號過程（2）檢查vs,在弧(vs,v1)上,fs1=7,cs1=9,fs1<cs1,則v1的標(biāo)號為(vs,l(v1))，其中第30頁，共34頁，2023年，2月20日，星期四l(v1)=min{l(vs)，cs1–fs1}=min{+，9–2}=2（3）檢查v1,在弧(v1,v4)上,f14=7,c14=9,f14<c14,則v4的標(biāo)號為(v1,l(v4))，其中l(wèi)(v4)=min{l(v1)，c14–f14}=min{2，3-1}=2（4）檢查v4,在弧(v3,v4)上,f14=1>0，則v3的標(biāo)號為(-v4,l(v3))，其中l(wèi)(v3)=min{l(v4)，f34}=min{2，1}=1（5）檢查v3,在弧(v3,vt)