計量地理學-10.1-地理數(shù)據(jù)圖論描述

1、,,地理網(wǎng)絡的圖論描述,地理網(wǎng)絡的測度,,,,,,,網(wǎng)絡分析,是運籌學的一個重要分支，它主要運用圖論方法研究各類網(wǎng)絡的結(jié)構(gòu)及其優(yōu)化問題，是計量地理學必不可少的重要方法之一。,對于許多現(xiàn)實的地理問題，譬如城鎮(zhèn)體系問題、城市地域結(jié)構(gòu)問題、交通問題、商業(yè)網(wǎng)點布局問題、物流問題、管道運輸問題、供電與通訊線路問題等等，都可以運用網(wǎng)絡分析方法進行研究。,最短路徑與選址問題,最大流與最小費用流,地理網(wǎng)絡的圖論描述,“圖”,(Map/Picture/G

2、raphic/Image/Chart/Drawing/Painting),通俗意義上，主要是指各種各樣的地圖、遙感影像圖，或者是由各種符號、文字代表的示意圖，或者是由各種數(shù)據(jù)繪制而成的曲線圖、直方圖等等。,圖論中的“圖” (Graph),是一個純粹的數(shù)學概念，能從數(shù)學本質(zhì)上揭示地理實體與地理事物空間分布格局，地理要素之間的相互聯(lián)系以及它們在地域空間上的運動形式、地理事件發(fā)生的先后順序等。,（一）圖的定義,圖： 設V是一個由

3、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結(jié)合在一起就構(gòu)成了一個圖G，記作G＝(V, E),圖G由點集合V與線集合E構(gòu)成,,,V不允許是空集,E可以是空集,（一）圖的定義,頂點：點集合

4、V中的每一個點vi（i=1，2，…，n）稱為圖G的頂點。邊：線集合E中每一條線稱為圖G的邊（或弧）；若一條邊e連接u，v兩個頂點，則記為e＝(u, v)。,,例：在如下圖所示的圖中，頂點集合為 V＝｛v1，v2，v3，v4，v5，v6，v7，v8｝，邊集合為E＝{e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11 }。,（一）圖的定義,在現(xiàn)實地理系統(tǒng)中，對于地理位置、地理實體、地理區(qū)域以及它們之間的相互聯(lián)系，可以經(jīng)過

5、一定的簡化與抽象，將它們描述為圖論意義下的地理網(wǎng)絡，即圖。,一個由基本流域單元組成的復雜的流域地貌系統(tǒng)，如果舍棄各種復雜的地貌形態(tài)：,各條河流——線,河流分岔或匯聚處——點,河流水系網(wǎng)絡,（一）圖的定義,列昂納德·歐拉——哥尼斯堡七橋問題,東普魯士的哥尼斯堡城（現(xiàn)在的加里寧格勒）是建在兩條河流的匯合處以及河中的兩個小島上的，共有7座小橋?qū)蓚€小島及小島與城市的其他部分連接起來，那么，哥尼斯堡人從其住所出發(fā)，能否恰好只經(jīng)過每座小

6、橋一次而返回原處？圖論研究結(jié)果告訴我們，其答案是否定的。,,,,,（一）圖的定義,需要說明的是：圖的定義只關(guān)注點之間是否連通，而不關(guān)注點之間的連結(jié)方式。對于任何一個圖，它的畫法并不唯一。,圖僅定義了節(jié)點之間是否存在連接的邏輯關(guān)系，而不涉及具體的連接方式,（二）圖的一些相關(guān)概念,（1）無向圖與有向圖： 無向圖——圖的每條邊都沒有給定方向，

7、 即（u，v）＝（v，u）； 有向圖——圖的每條邊都給定了方向， 即（u，v）≠（v，u）。,有向圖,一般將有向圖的邊集記為A，無向圖的邊集記為E。這樣，G=（V，A）就表示有向圖，而G=（V，E）則表示無向圖。,（二）圖的一些相關(guān)概念,（2）賦權(quán)圖： 圖的定義中并沒涉及點和線的差異性，即所有的點和

8、所有的線認為是無差異的，為體現(xiàn)點和線的實際區(qū)別，可以分別為點和線賦予權(quán)值來實現(xiàn)， 這樣的圖G稱為賦權(quán)圖。,為圖G＝(V, E)中的每一條邊(vi, vj)都相應地賦一個數(shù)值wij，其中wij稱為邊(vi, vj)的權(quán)值。,為線賦權(quán),為點賦權(quán),對于圖G中的每一頂點vj，也可以賦予一個載荷a(vj)，其中a(vj)稱為點vj的權(quán)值。,在同一個圖G中，可以同時為頂點和連接邊都賦權(quán)值，并且，可以為頂點和連接邊賦予超過一個以上的的不同權(quán)重值。,（

9、二）圖的一些相關(guān)概念,（3）關(guān)聯(lián)邊：若e＝(u,v)，則稱u和v是邊e的端點，e是u和v的關(guān)聯(lián)邊。,（4）環(huán)：若連接邊e的兩個端點相同，即u＝v，則稱e為環(huán)。,（5）多重邊：若連接相同兩個端點的邊多于一條以上，則稱為多重邊。,（6）多重圖：含有多重邊的圖，稱為多重圖。,（7）簡單圖：無環(huán)、無多重邊的圖，稱為簡單圖。,圖的兩個特殊結(jié)構(gòu),（二）圖的一些相關(guān)概念,（8）頂點的次數(shù)： 以點v為端點的邊的個數(shù)稱為點v的次，記為d(v

10、)。(另可描述為度數(shù)Degree),Q: 次數(shù)反映了頂點的什么特征？,次數(shù)的取值范圍？次數(shù)越小表明？次數(shù)越大表明？,（二）圖的一些相關(guān)概念,（9）路徑（鏈）： 若圖G＝(V,E)中，若頂點與邊交替出現(xiàn)的序列（對于有向圖來說，要求排在每一條邊之前和之后的頂點分別是這條邊的起點和終點） P＝{vi1，ei1，vi2，ei2，…，eik-1，vik} 滿足

11、 eit = (vit，vi,t+1) (t=1,2,…,k-1) 則稱P為一條從vi1到vik的路（或鏈），簡記為 P＝{vi1，vi2，…，vik},P＝{vi1，ei1，vi2，ei2，…，eik-1，vik},實質(zhì)是頂點與邊的交替序列集合,,該連接邊的起點和終點必須是它在路徑集合中的相

12、鄰前一個點和后一個點,P＝{vi1，vi2，…，vik},正因為路徑滿足這個特征，故可將其簡化為頂點的序列集合,（二）圖的一些相關(guān)概念,（10）連通圖： 在圖G中，若任何兩點之間至少存在一條路徑（對于有向圖，則不考慮邊的方向），則稱G為連通圖，否則稱為不連通圖。,（11）回路： 若一條路的起點與終點相同，即vi1=vik，則稱它為回路（閉合的回路）。,（12）樹：（Tree）

13、不含回路的連通的無向圖稱為樹。,作為一種特殊類型的網(wǎng)絡圖，樹(Tree)的基本特點：,,1、任意兩個根、枝、葉節(jié)點均有連通的路徑；2、不存在任何閉合路徑即回路；3、連接邊沒有方向（養(yǎng)分可從樹根傳遍所有枝葉，光合作用也可從樹葉傳回樹根）。,注：Tree的兩種最基本算法即“生成”與“遍歷”,（二）圖的一些相關(guān)概念,（13）基礎圖： 從一個有向圖D＝（V，A）中去掉所有邊上的箭頭所得到的無向圖，就稱為D的基礎圖，記

14、之為G（D）。,（15）截：如果從圖中移去邊的一個集合將增加子圖/亞圖的數(shù)目時，被移去的邊的集合就稱為截。,什么是“截” ？ “截”是一些特殊連接邊的集合；特殊性體現(xiàn)于連接邊的移除將解除了有些節(jié)點的約束力，使得在子圖選擇時有了更多的可選空間，從而增加了子圖數(shù)量。,（14）子圖/亞圖：設G＝（V， E）是一個無向圖，V1與E1分別是V與E的子集，即V1 V， E1 E。如果對于任意ei∈E1，其兩

15、個端點都屬于V1，則稱G1＝（V1，E1）是圖G的一個子圖。（一般性地， E1不允許為空集）,（二）圖的一些相關(guān)概念,（16）支撐子圖：設G1＝（V1，E1）是圖G＝（V，E）的一個子圖，如果V1 ＝ V，則稱G1是G 的支撐子圖。,即：節(jié)點數(shù)量滿額的子圖為支撐子圖；或者說，支撐子圖是從原網(wǎng)絡圖中僅僅刪除若干連接邊所得；原網(wǎng)絡圖為它自身的一個支撐子圖。,（17）支撐樹：設G＝（V，E）是一個無向圖，如果T＝（V1，E1）是G的支撐子圖，

16、并且T是樹，則稱T是G 的一個支撐樹。,Q：一個無向圖一定會有支撐樹嗎？或者說，將一個無向圖刪除若干連接邊，必定能得到一個樹結(jié)構(gòu)嗎？,（二）圖的一些相關(guān)概念,（18）樹的重量：一個樹的所有邊的權(quán)值之和稱為該樹的重量。,注：既然連接邊的權(quán)值可以由多個，即數(shù)的重量可以是由多種權(quán)重總和構(gòu)成；同時，節(jié)點也可有權(quán)重，可考慮引入以定義特殊的樹的重量。,注：無權(quán)圖的最小支撐樹即為所有支撐樹中的邊數(shù)最小者。,（19）最小支撐樹：在一個圖的所有支撐樹中，

17、重量最小的那個叫做該圖的最小支撐樹。,地理網(wǎng)絡的測度,許多現(xiàn)實的地理問題，只要經(jīng)過一定的簡化和抽象，就可以將它們描述為圖論意義下的地理網(wǎng)絡，點和線的排布格局，并可以進一步定量化地測度它們的拓撲結(jié)構(gòu)，以及連通性和復雜性。,圖 地理網(wǎng)絡的拓撲分類,目前關(guān)于地理網(wǎng)絡的拓撲研究，最多、最常見的是基于平面圖描述的二維平面網(wǎng)絡。,各連線之間不能交叉，而且每一條連線除頂點以外，不能再有其他的公共點。,（一）關(guān)聯(lián)矩陣與鄰接矩陣,,關(guān)聯(lián)矩陣,關(guān)聯(lián)矩陣用

18、于測度網(wǎng)絡圖中頂點與邊的關(guān)聯(lián)關(guān)系。 假設網(wǎng)絡圖G＝(V, E)的頂點集為V={v1，v2，…，vn}，邊集為E={e1，e2，…，em}，則該網(wǎng)絡圖的關(guān)聯(lián)矩陣就是一個n×m矩陣，可表示為,式中：gij為頂點vi與邊ej相關(guān)聯(lián)的次數(shù)。,gij,（簡單圖）頂點vi和連接邊ej是否關(guān)聯(lián)？如果是，則gij =1；如果否，則gij =0。,對于存在多重邊的多重圖， gij可能大于1。,,鄰接矩陣,（一）關(guān)聯(lián)矩陣與鄰接矩陣,鄰

19、接矩陣用于測度網(wǎng)絡圖中各頂點之間的連通性程度。 假設圖G＝(V, E)的頂點集為V={v1，v2，…，vn}，則鄰接矩陣是一個n階方陣，可表示為,式中：aij表示連接頂點vi與vj的邊的數(shù)目。,aij,（簡單圖）頂點vi和頂點vj是否存在連接邊？如果是，則aij =1；如果否，則aij =0。,對于存在多重邊的多重圖， aij可能大于1。,例：,該圖的關(guān)聯(lián)矩陣為：,該圖的鄰接矩陣為：,鄰接矩陣和關(guān)聯(lián)矩陣如何互相轉(zhuǎn)換？？,,,（

20、二）網(wǎng)絡結(jié)構(gòu)測度指標,對于任何一個網(wǎng)絡圖，都存在著3種共同的基礎指標： ① 連線（邊或?。?shù)目m； ② 結(jié)點（頂點）數(shù)目n； ③ 網(wǎng)絡中互不連接的亞圖數(shù)目p。,注：統(tǒng)計p值時有連接的或同級的亞圖僅計算一次。,,由m、n、p可以產(chǎn)生如下幾個更為一般性的網(wǎng)絡結(jié)構(gòu)測度指標： β指數(shù)、 回路數(shù)k、 α指數(shù)、γ指數(shù)。,,β指數(shù),β指數(shù)也稱為線點率，是網(wǎng)絡內(nèi)每一個結(jié)點的平均連線數(shù)目：,β=0，表示

21、無網(wǎng)絡存在；網(wǎng)絡的復雜性增加，則β值也增大。,沒有孤立點存在的網(wǎng)絡，連線數(shù)目為n-p,則β指數(shù)為：,如果地理網(wǎng)絡不包含次級亞圖，即p＝1，則其最低限度連接的β指數(shù)值為 。,,回路數(shù)k,回路是一種閉合路徑,它的始點同時也是終點。 若網(wǎng)絡內(nèi)存在回路，則連線的數(shù)目就必須超過n-p（最低限度連接網(wǎng)絡的連接數(shù)目）。,回路數(shù)k為實際連線數(shù)目減去最低限度連接的連線數(shù)目，即,,α指數(shù),網(wǎng)絡內(nèi)可能存在的最大回路數(shù)目為連

22、線的最大可能數(shù)目減去最低限度連接的連線數(shù)目，即：,所以， α指數(shù)為：,α指數(shù)也可以用百分率表示：,α指數(shù)的變化范圍，一般介于[0，1]區(qū)間；α＝0，意味著網(wǎng)絡中不存在回路；α＝1，說明網(wǎng)絡中已達到最大限度的回路數(shù)目。,α指數(shù)是指實際回路數(shù)與網(wǎng)絡內(nèi)可能存在的最大回路數(shù)之間的比率。,,γ指數(shù),γ指數(shù)指網(wǎng)絡內(nèi)連線的實際數(shù)目與連線可能存在的最大數(shù)目之間的比率，對于平面網(wǎng)絡，其計算公式為：,γ指數(shù)也可以用百分比表示：,γ指數(shù)是測度網(wǎng)絡連通性的