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

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

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

2)E中每一條線ei是以V中兩個(gè)點(diǎn)Vs,Vt為端點(diǎn)

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

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

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

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

5、最小支撐樹1）賦權(quán)圖：給圖G=(V,E)，對(duì)G中的每一條邊[vi,vj]，相應(yīng)地有一個(gè)數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。2）最小支撐樹：如果T=(V,E’)是G的一個(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的最小支撐樹(簡(jiǎn)稱最小樹)w(T*)=minw(T)T第6頁(yè)，共34頁(yè)，2023年，2月20日，星期四3）求最小樹的方法：方法一(避圈法)開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。方法二(破圈法)任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊。在余下的圖中，重復(fù)這個(gè)步驟，一直到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹。

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

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

6、鏈：設(shè)(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一個(gè)點(diǎn)弧交錯(cuò)序列，如果這個(gè)序列在基礎(chǔ)圖G(D)中所對(duì)應(yīng)的點(diǎn)邊序列是一條鏈，則稱這個(gè)點(diǎn)弧交錯(cuò)序列是D的一條鏈。7、路：如果(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一條鏈，并且對(duì)t=1,2,…,k-1，均有ait=(vit,vit+1)，稱之為從vi1到vik的一條路。8、回路：若路的第一個(gè)點(diǎn)和最后一點(diǎn)相同，則稱之為回路。第10頁(yè)，共34頁(yè)，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、對(duì)于圖G=（V，E），∣V∣=n,構(gòu)造一個(gè)矩陣A=（aij）n×n,其中：

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

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

αi：表示到的最短路值

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

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

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

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）時(shí)，再多迭代一次P1j（t），若P1j（t）=P1j（t-1），則原問(wèn)題無(wú)解，存在負(fù)回路。第14頁(yè)，共34頁(yè)，2023年，2月20日，星期四例：求下圖所示有向圖中從v1到各點(diǎn)的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第15頁(yè)，共34頁(yè)，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說(shuō)明：表中空格處為+。第16頁(yè)，共34頁(yè)，2023年，2月20日，星期四例設(shè)備更新問(wèn)題制訂一設(shè)備更新問(wèn)題，使得總費(fèi)用最小

第1年第2年第3年第4年第5年購(gòu)買費(fèi)1314161924

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

維修費(fèi)810131827

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

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

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

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

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

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

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

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

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

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

fij(vi,vj)去掉所有的標(biāo)號(hào)，對(duì)新的可行流f′={fij′}，重新進(jìn)入標(biāo)號(hào)過(guò)程。第28頁(yè)，共34頁(yè)，2023年，2月20日，星期四可結(jié)合下圖理解其實(shí)際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第29頁(yè)，共34頁(yè)，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)號(hào)過(guò)程（2）檢查vs,在弧(vs,v1)上,fs1=7,cs1=9,fs1<cs1,則v1的標(biāo)號(hào)為(vs,l(v1))，其中第30頁(yè)，共34頁(yè)，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)號(hà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)號(hào)為(-v4,l(v3))，其中l(wèi)(v3)=min{l(v4)，f34}=min{2，1}=1（5）檢查v3,在弧(v3,vt)