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

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

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

3、n個(gè)點(diǎn)vi (i=1，2，…，n)所組成的集合，即V={v1，v2，…，vn}；E是一個(gè)由m條線ei（i=1，2，…，m）所組成的集合，即E={e1，e2，…，em}；而且集合E中任意一條線，都是以集合V中的點(diǎn)為端點(diǎn)；而且任意兩條線除了端點(diǎn)外沒有其他的公共點(diǎn)或交叉點(diǎn)。 那么，把V與E結(jié)合在一起就構(gòu)成了一個(gè)圖G，記作G＝(V, E),圖G由點(diǎn)集合V與線集合E構(gòu)成,,,V不允許是空集,E可以是空集,（一）圖的定義,頂點(diǎn)：點(diǎn)集合

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

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

6、橋一次而返回原處？圖論研究結(jié)果告訴我們，其答案是否定的。,,,,,（一）圖的定義,需要說明的是：圖的定義只關(guān)注點(diǎn)之間是否連通，而不關(guān)注點(diǎn)之間的連結(jié)方式。對(duì)于任何一個(gè)圖，它的畫法并不唯一。,圖僅定義了節(jié)點(diǎn)之間是否存在連接的邏輯關(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)圖： 圖的定義中并沒涉及點(diǎn)和線的差異性，即所有的點(diǎn)和

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

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

10、)。(另可描述為度數(shù)Degree),Q: 次數(shù)反映了頂點(diǎn)的什么特征？,次數(shù)的取值范圍？次數(shù)越小表明？次數(shù)越大表明？,（二）圖的一些相關(guān)概念,（9）路徑（鏈）： 若圖G＝(V,E)中，若頂點(diǎn)與邊交替出現(xiàn)的序列（對(duì)于有向圖來說，要求排在每一條邊之前和之后的頂點(diǎn)分別是這條邊的起點(diǎn)和終點(diǎ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},實(shí)質(zhì)是頂點(diǎn)與邊的交替序列集合,,該連接邊的起點(diǎn)和終點(diǎn)必須是它在路徑集合中的相

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

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

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

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

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

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

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

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

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

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

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