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

第四章圖與網(wǎng)絡(luò)分析圖是最直觀的模型圖論是交通系統(tǒng)分析中的重要工具圖論在交通系統(tǒng)規(guī)劃、管理中作用大圖論是對(duì)實(shí)際交通網(wǎng)絡(luò)進(jìn)行抽象分析的重要手段12蘇州市規(guī)劃公交線路網(wǎng)經(jīng)過(guò)抽象后的城市道路網(wǎng)絡(luò)圖3567BACD圖論GraphTheory哥尼斯堡七橋問(wèn)題(歐拉回路)/環(huán)球旅行問(wèn)題(哈密爾頓回路)/中國(guó)郵路問(wèn)題歐拉Euler(1707-1783)在1736年發(fā)表第一篇圖論方面的論文，奠基了圖論中的一些基本定理很多問(wèn)題都可以用點(diǎn)和線來(lái)表示，一般點(diǎn)表示實(shí)體，線表示實(shí)體間的關(guān)聯(lián)9一、圖與網(wǎng)絡(luò)的基本概念

節(jié)點(diǎn)(Vertex)物理實(shí)體、事物、概念一般用vi

表示邊(Edge)節(jié)點(diǎn)間的連線，表示有關(guān)系一般用eij

表示圖(Graph)節(jié)點(diǎn)和邊的集合一般用G(V,E)表示點(diǎn)集V={v1,v2,…,vn}邊集E={eij}網(wǎng)絡(luò)(Network)邊上具有表示連接強(qiáng)度的權(quán)值，如wij又稱加權(quán)圖(Weightedgraph)10無(wú)向圖與有向圖邊都沒(méi)有方向的圖稱為無(wú)向圖在無(wú)向圖中eij=eji，或(vi,vj)=(vj,vi)當(dāng)邊都有方向時(shí)，稱為有向圖，用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij表示，i,j的順序是不能顛倒的，圖中弧的方向用箭頭標(biāo)識(shí)圖中既有邊又有弧，稱為混合圖11

端點(diǎn)，關(guān)聯(lián)邊，相鄰，次有向圖中，由節(jié)點(diǎn)指向外的弧的數(shù)目稱為正次數(shù)，記為d+，指向該節(jié)點(diǎn)的弧的數(shù)目稱為負(fù)次數(shù)，記為d–次數(shù)為0的點(diǎn)稱為孤立點(diǎn)(isolatedvertex)

，次數(shù)為1的點(diǎn)稱為懸掛點(diǎn)(pendantvertex)鏈，圈，路徑，回路相鄰節(jié)點(diǎn)的序列

{v1,v2,…,vn}構(gòu)成一條鏈(link)，又稱為行走(walk)；首尾相連的鏈稱為圈(loop)，或閉行走在無(wú)向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)的鏈稱為路徑(path)；在有向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)且鏈中所有弧的方向一致，則稱為有向路徑(directedpath)首尾相連的路徑稱為回路(circuit)；13

連通圖，子圖，成分設(shè)有兩個(gè)圖G1(V1,E1),G2(V2,E2),若V2V1,E2

E1，則G2是G1的子圖若V2V1，E2E1,稱G2為G1的真子圖若V2=V1，E2E1,稱G2為G1的部分圖無(wú)向圖中，若任意兩點(diǎn)間至少存在一條路徑，則稱為連通圖(connectedgraph)，否則為非連通圖(discon-nectedgraph)；非連通圖中的每個(gè)連通子圖稱為成分(component)鏈，圈，路徑(簡(jiǎn)稱路)，回路都是原圖的子圖14V6V1V4V2V5V3V1V2V3V4V5V6V1（a）（b）V2V3V4V5（c）（d）V2V3V4V5V6b,c,d均為a的子圖，b為a的部分圖，c,d為a的真子圖15樹圖與最小部分樹一般研究無(wú)向圖樹圖：倒置的樹，根(root)在上，樹葉(leaf)在下多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)、路網(wǎng)布局等都是典型的樹圖17樹的定義及其性質(zhì)任兩點(diǎn)之間有且只有一條路徑的圖（無(wú)圈的連通圖）稱為樹(tree)，記為T樹圖G=（V,E）的點(diǎn)數(shù)記為p，邊數(shù)記為q，則q=p-1。樹的性質(zhì)：最少邊的連通子圖，樹中必不存在回路任意兩節(jié)點(diǎn)之間必有一條且僅有一條鏈任何樹必存在次數(shù)為1的點(diǎn)具有n個(gè)節(jié)點(diǎn)的樹T的邊恰好為n1條，反之，任何有n個(gè)節(jié)點(diǎn)，n1條邊的連通圖必是一棵樹18路(通路)初等路初等回路鏈、路、樹簡(jiǎn)單鏈初等鏈初等圈樹19給圖G中的每一條邊[vi，vj]一個(gè)相應(yīng)的數(shù)ij，則稱G為賦權(quán)圖。在賦權(quán)圖G的所有支撐樹中，必有某個(gè)支撐樹，其所有邊的和為最小，稱為最小樹。求賦權(quán)圖G的最小支撐樹的方法也有兩種,“破圈法”和“避圈法”。655172344v1v2v3v4v5v6破圈法：任選一個(gè)圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。最小部分樹（支撐樹）21v3v21v42v53v641v2v3v4v5v6避圈法：開始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)盡可能小，且與已選邊不構(gòu)成圈的邊。22歸納

G=（V，E）子圖矩陣表示含元素的個(gè)數(shù)點(diǎn)的次邊特殊的圖點(diǎn)邊關(guān)系簡(jiǎn)單圖多重圖空?qǐng)D連通圖樹部分樹23點(diǎn)邊關(guān)系真子圖部分圖子圖各種鏈的概念通路樹連通圖

部分樹有向、無(wú)向25兩個(gè)主要定理定理1

圖G中，所有頂點(diǎn)的次的和等于所有邊數(shù)的2倍。即定理2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。證明要點(diǎn)：（V1、V2分別是圖G中次為奇數(shù)和偶數(shù)的頂點(diǎn)集合）26三、網(wǎng)絡(luò)的計(jì)算機(jī)表示大量的工程計(jì)算無(wú)法依靠手工完成交通工程中的網(wǎng)絡(luò)計(jì)算必須依靠計(jì)算機(jī)

網(wǎng)絡(luò)在計(jì)算機(jī)中的表示與存儲(chǔ)29900多節(jié)點(diǎn)，3000多條邊30構(gòu)造VE階矩陣A={aij}V1V3V2V4e1e2e3e4e6e51、關(guān)聯(lián)矩陣法31V4V2V1V5V3563263542、鄰接矩陣法D={dij}

32V4V2V1V5V356326354權(quán)重矩陣33V4V2V1V5V33、邊目錄法e1e6e7e4e5e2e3e1=(1,2)e2=(2,5)e3=(5,4)e4=(1,4)…344、鄰接目錄法（推薦）計(jì)算機(jī)存儲(chǔ)利用率高12345635最短路問(wèn)題（SP）

詳見(jiàn)單獨(dú)文件36最大流問(wèn)題37AC(40)(10)(10)(20)(30)(30)(20)(20)(20)(30)(60)(40)(10)下圖為某一城市道路網(wǎng)絡(luò)，路段均為雙向，圖中數(shù)據(jù)（a）為道路通行能力（容量）。求：從A、C兩點(diǎn)到B點(diǎn)的最大網(wǎng)絡(luò)運(yùn)輸能力（最大流量）。B381網(wǎng)絡(luò)與流網(wǎng)路流一般在有向圖上討論定義網(wǎng)路上支路的容量為其最大通過(guò)能力，記為cij，支路上的實(shí)際流量記為fij圖中規(guī)定一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)t節(jié)點(diǎn)沒(méi)有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ)容量限制條件：0fijcij平衡條件：

滿足上述條件的網(wǎng)路流稱為可行流，總存在最大可行流當(dāng)支路上fij

=cij

，稱為飽和弧最大流問(wèn)題也是一個(gè)線性規(guī)劃問(wèn)題viA(vi)B(vi)392截集與截集容量定義：把網(wǎng)路分割為兩個(gè)成分的弧的最小集合，其中一個(gè)成分包含s點(diǎn)，另一個(gè)包含t點(diǎn)。一般包含s點(diǎn)的成分中的節(jié)點(diǎn)集合用V表示，包含t點(diǎn)的成分中的節(jié)點(diǎn)集合用V表示截集容量是指截集中正向弧的容量之和

福特-富克森定理：網(wǎng)路的最大流等于最小截集容量403確定網(wǎng)路最大流的標(biāo)號(hào)法從任一個(gè)初始可行流出發(fā)，如0流基本算法：找一條從s到t點(diǎn)的增廣鏈(augmentingpath)最大流充要條件：

當(dāng)且僅當(dāng)不存在增廣鏈時(shí)，可行流為最大流。

增廣鏈中與s到t方向一致的弧稱為前向弧，反之后向弧

增廣過(guò)程：前向弧fij=fij

+q,后向弧fij=fij

q

增廣后仍是可行流

前向弧非飽和?。缓笙蚧》橇懔骰?。41最大流最小截的標(biāo)號(hào)法步驟第一步：標(biāo)號(hào)過(guò)程，找一條增廣鏈1、給源點(diǎn)s標(biāo)號(hào)[s+,q(s)=]，表示從s點(diǎn)有無(wú)限流出潛力2、找出與已標(biāo)號(hào)節(jié)點(diǎn)i相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn)j，若(1)(i,j)是前向弧且飽和，則節(jié)點(diǎn)j

不標(biāo)號(hào)；(2)(i,j)是前向弧且未飽和，則節(jié)點(diǎn)j

標(biāo)號(hào)為[i+,q(j)]，表示從節(jié)點(diǎn)i正向流出，可增廣q(j)=min[q(i),cijfij]；(3)(j,i)是后向弧，若fji=0，則節(jié)點(diǎn)j不標(biāo)號(hào)；(4)(j,i)是后向弧，若fji>0，則節(jié)點(diǎn)j標(biāo)號(hào)為[i,q(j)]，表示從節(jié)點(diǎn)j

流向i，可增廣q(j)=min[q(i),fji]；3、重復(fù)步驟2，可能出現(xiàn)兩種情況：(1)節(jié)點(diǎn)t尚未標(biāo)號(hào)，但無(wú)法繼續(xù)標(biāo)記，說(shuō)明網(wǎng)路中已不存在增廣鏈，當(dāng)前流v(f)就是最大流；所有獲標(biāo)號(hào)的節(jié)點(diǎn)在V中，未獲標(biāo)號(hào)節(jié)點(diǎn)在V中，V與V間的弧即為最小截集；算法結(jié)束(2)節(jié)點(diǎn)t獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn)t標(biāo)號(hào)回溯可找出該增廣鏈；到第二步42最大流最小截的標(biāo)號(hào)法步驟第二步：增廣過(guò)程1、對(duì)增廣鏈中的前向弧，令f=f+q(t)，q(t)為節(jié)點(diǎn)t的標(biāo)記值2、對(duì)增廣鏈中的后向弧，令f=fq(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標(biāo)號(hào)，回到第一步以上算法是按廣探法描述的，但在實(shí)際圖上作業(yè)時(shí)，按深探法進(jìn)行更快捷一次只找一條增廣鏈，增廣一次換一張圖最后一次用廣探法，以便找出最小截集43最大流最小截集的標(biāo)號(hào)法舉例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)44最大流最小截集的標(biāo)號(hào)法舉例(s+,)(s+,3)(2,3)最小截集45多收發(fā)點(diǎn)的網(wǎng)絡(luò)最大流網(wǎng)絡(luò)中存在多個(gè)發(fā)點(diǎn)和收點(diǎn)時(shí)：虛擬發(fā)點(diǎn)和收點(diǎn)，虛擬發(fā)點(diǎn)和收點(diǎn)到各發(fā)點(diǎn)的弧的容量、各收點(diǎn)的弧的容量為無(wú)窮大（不破壞發(fā)點(diǎn)、收點(diǎn)產(chǎn)生、吸引流量能力無(wú)限的條件）46Vs3Vt3V2V3V4V6V513945655545104Vs1Vs2Vt2Vt147Vs3Vt3V2V3V4V6V5Vs1Vs2Vt2Vt1VsVt∞∞∞∞∞∞多收發(fā)點(diǎn)的最大流問(wèn)題轉(zhuǎn)化為單收發(fā)點(diǎn)的最大流問(wèn)題48最大流問(wèn)題作業(yè)VsV2V3V6V5(3,2)(5,1)(1,1)(4,2)(2,2)(1,1)(5,2)(2,1)Vt(3,0)弧旁注釋（a,b）對(duì)應(yīng)（弧容