網絡分析,是運籌學的壹個重要分支,它主要運用圖論方法研究各類網絡的結構及其優化問題.
網絡分析方法是計量地理學必不可少的重要方法之壹.
本章主要內容:
地理網絡的圖論描述
最短路徑與選址問題
最大流與最小費用流
第壹節 地理網絡的圖論描述
通俗意義上的"圖",主要是指各種各樣的地圖,遙感影像圖,或者是由各種符號,文字代表的示意圖,或者是由各種地理數據繪制而成的曲線圖,直方圖,等等.
圖論中的"圖",是壹個數學概念,這種"圖"能從數學本質上揭示地理實體與地理事物空間分布格局,地理要素之間的相互聯系以及它們在地域空間上的運動形式,地理事件發生的先後順序,…,等等.
壹,地理網絡的圖論描述
(1)圖: 設V是壹個由n個點vi (i=1,2,…,n)所組成的集合,即V={v1,v2,…,vn},E是壹個由m條線ei(i=1,2,…,m)所組成的集合,即E={e1,e2,…,em},而且E中任意壹條線,都是以V中的點為端點;任意兩條線除了端點外沒有其它的公***點.
(壹)圖的定義
那麽,把V與E結合在壹起就構成了壹個圖G,記作G=(V,E).
(3)邊:E中每壹條線稱為圖G 的邊(或弧);若壹條邊e連接u,v兩個頂點,則記為e=(u,v).
(2)頂點: V中的每壹個點vi(i=1,2,…,n)稱為圖G的頂點.
(4)在圖G=(V,E)中,V不允許是空集,但E可以是空集.
(5)從以上定義可以看出,圖包含兩個方面的基本要素:
① 點集(或稱頂點集);②邊集(或稱弧集).
例:在如圖10.1.1所示的圖中,
頂點集為V={v1,v2,v3,v4,v5,v6,v7,v8},
邊集為E={e1,e2,e3,e4,e5,e6,e7,e8,e9,
e10,e11 }.
圖10.1.1
(6)在現實地理系統中,對於地理位置,地理實體,地理區域以及它們之間的相互聯系,可以經過壹定的簡化與抽象,將它們描述為圖論意義下的地理網絡,即圖.
地理位置,地理實體,地理區域,譬如,山頂,河流匯聚點,車站,碼頭,村莊,城鎮等——點
它們之間的相互聯系,譬如,構造線,河流,交通線,供電與通訊線路,人口流,物質流,資金流,信息流,技術流等——點與點的連線.
壹個由基本流域單元組成的復雜的流域地貌系統,如果舍棄各種復雜的地貌形態,各條河流——線,河流分岔或匯聚處——點,流域地貌系統——水系的基本結局(樹).
列昂納德·歐拉——七橋問題
東普魯士的哥尼斯堡城(現在的加裏寧格勒)是建在兩條河流的匯合處以及河中的兩個小島上的,***有七座小橋將兩個小島及小島與城市的其它部分連接起來,那麽,哥尼斯堡人從其住所出發,能否恰好只經過每座小橋壹次而返回原處 圖論研究結果告訴我們,其答案是否定的.
(7)需要說明的是——圖的定義只關註點之間是否連通,而不關註點之間的連結方式.對於任何壹個圖,他的畫法並不唯壹.
(二)圖的壹些相關概念
(1)無向圖與有向圖
無向圖——圖的每條邊都沒有給定方向,
即(u,v)=(v,u);
有向圖——圖的每條邊都給定了方向,
即(u,v)≠(v,u).
壹般將有向圖的邊集記為A,無向圖的邊集記為E.這樣,G=(V,A)就表示有向圖,而G=(V,E)則表示無向圖.
有向圖
(2)賦權圖.
如果圖G=(V,E)中的每壹條邊(vi,vj)都相應地賦有壹個數值wij,則稱G為賦權圖,其中wij稱為邊(vi,vj)的權值.
除了可以給圖的邊賦權外,也可以給圖的頂點賦權.這就是說,對於圖G中的每壹頂點vj,也可以賦予壹個載荷a(vj).
(3)關聯邊.
若e=(u,v),則稱u和v是邊e的端點,e是u和v的關聯邊.
(4)環.
若e的兩個端點相同,即u=v,則稱為環.
(5)多重邊.
若連接兩個端點的邊多於壹條以上,則稱為多重邊.
(6)多重圖.
含有多重邊的圖,稱為多重圖.
(7)簡單圖.
無環,無多重邊的圖,稱為簡單圖.
(8)點與次.
以點v為端點的邊的個數稱為點v的次,記為d(v).
次等於1的點稱為懸掛點;與懸掛點關聯的邊稱為懸掛邊;
次為零的點稱為孤立點.次為奇數的點稱為奇點;次為偶數的點稱為偶點.
(9)連通圖.在圖G中,若任何兩點之間至少存在壹條路(對於有向圖,則不考慮邊的方向),則稱G為連通圖,否則稱為不連通圖.
(10)路(鏈).
若圖G=(V,E)中,若頂點與邊交替出現的序列(對於有向圖來說,要求排在每壹條邊之前和之後的頂點分別是這條邊的起點和終點):
P={vi1,ei1,vi2,ei2,…,eik-1,vik}
滿足
eit = (vit,vi,t+1) (t=1,2,…,k-1)
則稱P為壹條從vi1到vik的路(或鏈),簡記為
P={vi1,vi2,…,vik}.
(11)回路.
若壹條路的起點與終點相同,即vi1=vik,則稱它為回路.
(12)樹.
不含回路的連通的無向圖稱為樹.
(13)基礎圖.
從壹個有向圖D=(V,A)中去掉所有邊上的箭頭所得到的無向圖,就稱為D的基礎圖,記之為G(D).
(14)截.
如果從圖中移去邊的壹個集合將增加亞圖的數目時,被移去的邊的集合就稱為截.
(15)子圖.
設G=(V, E)是壹個無向圖,V1與E1分別是V與E的子集,即V1 V,E1 E.如果對於任意ei∈E1,其兩個端點都屬於V1,則稱G1=(V1,E1)是圖G的壹個子圖.
(16)支撐子圖.
設G1=(V1,E1)是圖G=(V,E)的壹個子圖,如果V1 = V,則稱G1是G 的支撐子圖.
(17)支撐樹.
設G=(V,E)是壹個無向圖,如果T=(V1,E1)是G的支撐子圖,並且T是樹,則稱T是G 的壹個支撐樹.
(18)樹的重量.
壹個樹的所有邊的權值之和稱為該樹的重量.
(19)最小支撐樹.
在壹個圖的所有支撐樹中,重量最小的那個叫做該圖的最小支撐樹.
二,地理網絡的測度
許多現實的地理問題,只要經過壹定的簡化和抽象,就可以將它們描述為圖論意義下的地理網絡,點和線的排布格局,並可以進壹步定量化地測度它們的拓撲結構,以及連通性和復雜性.
樹狀型
地理網絡
平面網絡(二維的)
非平面網絡(非二維的)
道路型
環狀型
細胞型
圖10.1.5 地理網絡的拓撲分類
目前關於地理網絡的拓撲研究,最多,最常見的是基於平面圖描述的二維平面網絡.
所謂平面圖,被規定為:各連線之間不能交叉,而且每壹條連線除頂點以外,不能再有其它的公***點(牛文元,1987).
以下的討論,除非特別申明外,都限於二維平面網絡.
(壹)關聯矩陣與鄰接矩陣
關聯矩陣——測度網絡圖中頂點與邊的關聯關系.
假設網絡圖G=(V,E)的頂點集為V={v1,v2,…,vn},邊集為E={e1,e2,…,em},則該網絡圖的關聯矩陣就是壹個n×m矩陣,可表示為:
gij為頂點vi與邊ej相關聯的次數.
v3
v1
v2
v4
v5
e1
e2
e3
e4
e5
e6
e7
該圖的關聯矩陣為:
例:
鄰接矩陣——測度網絡圖中各頂點之間的連通性程度.
假設圖G=(V,E)的頂點集為V={v1,v2,…,vn},則鄰接矩陣是壹個n階方陣,可表示為:
aij表示連接頂點vi與vj的邊的數目.
該圖的鄰接矩陣為:
v3
v1
v2
v4
v5
e1
e2
e3
e4
e5
e6
e7
例:
(二)有關測度指標
β指數
回路數k
α指數
γ指數
對於任何壹個網絡圖,都存在著三種***同的基礎指標:
① 連線(邊或弧)數目m;
② 結點(頂點)數目n;
③ 網絡中亞圖的數目p.
由它們可以產生如下幾個更為壹般性的測度指標:
(1)β指數
◣β指數——線點率,是網絡內每壹個節點的平均連線數目.
◣β=0,表示無網絡存在;網絡的復雜性增加,則β值也增大.
◣沒有孤立點存在的網絡,連線數目為n- p,則β指數為
如果地理網絡不包含次級亞圖,即P=1,則其最低限度連接的 指數值為 .
(2) 回路數k
◣回路是壹種閉合路徑,它的始點同時也是終點.
◣若網絡內存在回路,則連線的數目就必須超過n-p(最低限度連接網絡的連接數目).
◣回路數k——實際連線數目減去最低限度連接的連線數目,即
(3) 指數
◣ 指數——實際回路數與網絡內可能存在的最大回路數之間的比率.
◣網絡內可能存在的最大回路數目為連線的最大可能數目減去最低限度連接的連線數目,即
所以, 指數為
指數也可以用百分率表示
對於非平面網絡,其 指數為
指數的變化範圍,壹般介於[0,1]區間, =0意味著網絡中不存在回路; =1,說明網絡中已達到最大限度的回路數目.
◣
◣
(4) γ指數
◣γ指數——網絡內連線的實際數目與連線可能存在的最大數目之間的比率,對於平面網絡,其計算公式為:
γ指數也可以用百分比表示
◣γ指數是測度網絡連通性的壹種指標,其數值變化範圍為[0,1].
◣γ=0,表示網絡內無連線,只有孤立點存在;
γ=1,則表示網絡內每壹個節點都存在與其它所有節點相連的連線.