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

節點(Vertex)物理實體、事物、概念一般用vi

表示邊(Edge)節點間的連線，表示有關系一般用eij

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

端點，關聯邊，相鄰，次有向圖中，由節點指向外的弧的數目稱為正次數，記為d+，指向該節點的弧的數目稱為負次數，記為d–次數為0的點稱為孤立點(isolatedvertex)

，次數為1的點稱為懸掛點(pendantvertex)鏈，圈，路徑，回路相鄰節點的序列

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

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

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

G=（V，E）子圖矩陣表示含元素的個數點的次邊特殊的圖點邊關系簡單圖多重圖空圖連通圖樹部分樹23點邊關系真子圖部分圖子圖各種鏈的概念通路樹連通圖

部分樹有向、無向25兩個主要定理定理1

圖G中，所有頂點的次的和等于所有邊數的2倍。即定理2在任一圖中，奇點的個數必為偶數。證明要點：（V1、V2分別是圖G中次為奇數和偶數的頂點集合）26三、網絡的計算機表示大量的工程計算無法依靠手工完成交通工程中的網絡計算必須依靠計算機

網絡在計算機中的表示與存儲29900多節點，3000多條邊30構造VE階矩陣A={aij}V1V3V2V4e1e2e3e4e6e51、關聯矩陣法31V4V2V1V5V3563263542、鄰接矩陣法D={dij}

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

詳見單獨文件36最大流問題37AC(40)(10)(10)(20)(30)(30)(20)(20)(20)(30)(60)(40)(10)下圖為某一城市道路網絡，路段均為雙向，圖中數據（a）為道路通行能力（容量）。求：從A、C兩點到B點的最大網絡運輸能力（最大流量）。B381網絡與流網路流一般在有向圖上討論定義網路上支路的容量為其最大通過能力，記為cij，支路上的實際流量記為fij圖中規定一個發點s，一個收點t節點沒有容量限制，流在節點不會存儲容量限制條件：0fijcij平衡條件：

滿足上述條件的網路流稱為可行流，總存在最大可行流當支路上fij

=cij

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

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

當且僅當不存在增廣鏈時，可行流為最大流。

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

增廣過程：前向弧fij=fij

+q,后向弧fij=fij

q

增廣后仍是可行流

前向弧非飽和弧；后向弧非零流弧。41最大流最小截的標號法步驟第一步：標號過程，找一條增廣鏈1、給源點s標號[s+,q(s)=]，表示從s點有無限流出潛力2、找出與已標號節點i相鄰的所有未標號節點j，若(1)(i,j)是前向弧且飽和，則節點j

不標號；(2)(i,j)是前向弧且未飽和，則節點j

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

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