1、1第第5章章 高級網頁制作高級網頁制作網頁設計與制作網頁設計與制作 南海學院計算機系制作Win8論壇 wk11第十章 網絡分析方法 對于許多現實的地理問題，譬如，城鎮體系問題，城市地域結構問題，交通問題，商業網點布局問題，物流問題，管道運輸問題，供電與通訊線路問題，等等，都可以運用網絡分析方法進行研究。 網絡分析，是運籌學的一個重要分支，它主要運用圖論方法研究各類網絡的結構及其優化問題。 網絡分析方法是計量地理學必不可少的重要方法之一。 本章主要內容：n地理網絡的圖論描述 n最短路徑與選址問題 n最大流與最小費用流10.1 地理網絡的圖論描述地理網絡的圖論描述n通俗意義上的通俗意義上的“圖圖”

2、，主要是指各種各樣的地圖、遙感影像圖，或者是由各種符號、文字代表的示意圖，或者是由各種地理數據繪制而成的曲線圖、直方圖，等等。 n圖論中的圖論中的“圖圖”，是一個數學概念，這種“圖”能從數學本質上揭示地理實體與地理事物空間分布格局，地理要素之間的相互聯系以及它們在地域空間上的運動形式，地理事件發生的先后順序，等等。 （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中的點為端點；任意兩條線除了端點外沒有其它的公共點。 一、地理網絡的圖論描述一、

3、地理網絡的圖論描述（一）圖的定義（一）圖的定義 那么，把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所示的圖中， 頂點集為Vv1，v2，v3，v4，v5，v6，v7，v8， 邊集為Ee1，e2，e3，e4，e5，e6，e7，

4、e8，e9，e10，e11 。圖10.1.1（6 6）在現實地理系統中，對于地理位置、地理實體、地理區域以及它們之間的相互聯系，可以經過一定的簡化與抽象，將它們描述為圖論意義下的地理網絡，即圖。 n地理位置、地理實體、地理區域，譬如，山頂、河流匯聚點、車站、碼頭、村莊、城鎮等點點 n它們之間的相互聯系，譬如，構造線、河流、交通線、供電與通訊線路、人口流、物質流、資金流、信息流、技術流等點與點的連線點與點的連線。 n一個由基本流域單元組成的復雜的流域地貌系統，如果舍棄各種復雜的地貌形態，各條河流線線，河流分岔或匯聚處點點，流域地貌系統水系的基本結局（樹樹）。 列昂納德歐拉七橋問題 東普魯士的哥尼

5、斯堡城（現在的加里寧格勒）是建在兩條河流的匯合處以及河中的兩個小島上的，共有七座小橋將兩個小島及小島與城市的其它部分連接起來，那么，哥尼斯堡人從其住所出發，能否恰好只經過每座小橋一次而返回原處？圖論研究結果告訴我們，其答案是否定的。（7 7）需要說明的是）需要說明的是圖的定義只關注點之間是否連通，而不關注點之間的連結方式。對于任何一個圖，他的畫法并不唯一。 （二）圖的（二）圖的一些一些相關概念相關概念 （1）無向圖與有向圖）無向圖與有向圖 無向圖圖的每條邊都沒有給定方向， 即（u，v）（v，u）；有向圖圖的每條邊都給定了方向， 即（u，v）（v，u）。一般將有向圖的邊集記為A，無向圖的邊集記為

6、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的兩個端點相同，即uv，則稱為環。 （5）多重邊）多重邊。 若連接兩個端點的邊多于一條以上，則稱為多重邊。 （6）多重圖。）多重圖。 含有多重邊的圖，稱為

7、多重圖。 （7）簡單圖。）簡單圖。 無環、無多重邊的圖，稱為簡單圖。 （8）點與次。）點與次。 以點v為端點的邊的個數稱為點v的次次，記為d(v)。 次等于1的點稱為懸掛點懸掛點；與懸掛點關聯的邊稱為懸掛邊懸掛邊； 次為零的點稱為孤立點孤立點。次為奇數的點稱為奇點奇點；次為偶 數的點稱為偶點偶點。（9）連通圖。）連通圖。在圖G中，若任何兩點之間至少存在一條路（對 于有向圖，則不考慮邊的方向），則稱G為連通圖，否則稱 為不連通圖。（10）路（鏈）。）路（鏈）。 若圖G（V，E）中，若頂點與邊交替出現的序列（對于有向圖來說，要求排在每一條邊之前和之后的頂點分別是這條邊的起點和終點）： Pvi1，e

8、i1，vi2，ei2，eik-1，vik 滿足 eit = (vit，vi，t+1) (t=1,2,k-1) 則稱P為一條從vi1到vik的路（或鏈），簡記為 Pvi1，vi2，vik。 （11）回路。）回路。 若一條路的起點與終點相同，即vi1=vik，則稱它為回路。（12）樹。）樹。 不含回路的連通的無向圖稱為樹。 （13）基礎圖。）基礎圖。 從一個有向圖D（V，A）中去掉所有邊上的箭頭所得到的無向圖，就稱為D的基礎圖，記之為G（D）。 （14）截。）截。 如果從圖中移去邊的一個集合將增加亞圖的數目時，被移去的邊的集合就稱為截。 （15）子圖。）子圖。 設G（V， E）是一個無向圖，V1與

9、E1分別是V與E的子集，即V1 V，E1 E。如果對于任意eiE1，其兩個端點都屬于V1，則稱G1（V1，E1）是圖G的一個子圖。 （1616）支撐子圖。）支撐子圖。 設G1（V1，E1）是圖G（V，E）的一個子圖，如果V1 V，則稱G1是G 的支撐子圖。 （1717）支撐樹。）支撐樹。 設G（V，E）是一個無向圖，如果T（V1，E1）是G的支撐子圖，并且T是樹，則稱T是G的一個支撐樹。 （1818）樹的重量。）樹的重量。 一個樹的所有邊的權值之和稱為該樹的重量。 （1919）最小支撐樹。）最小支撐樹。 在一個圖的所有支撐樹中，重量最小的那個叫做該圖的最小支撐樹。 二、地理網絡的測度二、地理網

10、絡的測度 許多現實的地理問題，只要經過一定的簡化和抽象，就可以將它們描述為圖論意義下的地理網絡，點和線的排布格局，并可以進一步定量化地測度它們的拓撲結構，以及連通性和復雜性。 樹狀型地理網絡平面網絡（二維的）非平面網絡（非二維的）道路型環狀型細胞型圖圖10.1.5 10.1.5 地理網絡的拓撲分類地理網絡的拓撲分類 目前關于地理網絡的拓撲研究，最多、最常見的是基于平面圖描述的二維平面網絡。 所謂平面圖，被規定為：各連線之間不能交叉，而且每一條連線除頂點以外，不能再有其它的公共點（牛文元，1987）。 以下的討論，除非特別申明外，都限于二維平面網絡。 （一）關聯矩陣與鄰接矩陣（一）關聯矩陣與鄰接

11、矩陣 n關聯矩陣關聯矩陣測度網絡圖中頂點與邊的關聯關系。 假設網絡圖G（V，E）的頂點集為V=v1，v2，vn，邊集為E=e1，e2，em，則該網絡圖的關聯矩陣就是一個nm矩陣，可表示為： nmnnmmgggggggggGL212222111211)(gij為頂點vi與邊ej相關聯的次數。 v3v1v2v4v5e1e2e3e4e5e6e7該圖的關聯矩陣為： 01110000001100110011000000111010001)(GL例： n鄰接矩陣鄰接矩陣測度網絡圖中各頂點之間的連通性程度。 假設圖G（V，E）的頂點集為V=v1，v2，vn，則鄰接矩陣是一個n階方陣，可表示為： nnnnnn

12、aaaaaaaaaGA212222111211)(aij表示連接頂點vi與vj的邊的數目。 該圖的鄰接矩陣為： 0110110100110110010110110)(GAv3v1v2v4v5e1e2e3e4e5e6e7例： （二）有關測度指標（二）有關測度指標n指數n回路數kn指數n指數對于任何一個網絡圖，都存在著三種共同的基礎指標： 連線（邊或弧）數目m； 結點（頂點）數目n； 網絡中亞圖的數目p。由它們可以產生如下幾個更為一般性的測度指標：指數線點率，是網絡內每一個節點的平均連線數目。 =0，表示無網絡存在；網絡的復雜性增加，則值也增大。沒有孤立點存在的網絡，連線數目為n- p,則指數為

13、（1 1）指數指數nmnpnl如果地理網絡不包含次級亞圖，即P1，則其最低限度連接的 指數值為 。)11 (n(2) (2) 回路數回路數k 回路是一種閉合路徑,它的始點同時也是終點。 若網絡內存在回路，則連線的數目就必須超過n-p（最低限度連接網絡的連接數目）。 回路數k實際連線數目減去最低限度連接的連線數目，即 pnmk(3) (3) 指數指數指數實際回路數與網絡內可能存在的最大回路數之間的比率。網絡內可能存在的最大回路數目為連線的最大可能數目減去最低限度連接的連線數目，即 pnpnpn52)()2(3pnpnm52 所以，指數為%10052pnpnm指數也可以用百分率表示對于非平面網絡，其 指數為%100)1(2/ ) 1(nnnpnm 指數的變化范圍，一般介于0，1區間， 0意味著網絡中不存在回路； 1，說明網絡中已達到最大限度的回路數目。 (4) (4) 指數指數指數網絡內連線的實際數目與連線可能存在的最大數目之間的比率，對于平面網絡，其計算公式為： 指數是測度網絡連通性的一種指標，其數值變化范圍為0，1。 0，表示網絡內無連線，只有孤立點存在；1，則表示網絡內每一個節點都存在與其它所有節點相連的連線。 )2( 3pnm指數也可以用百分比表示%100)2(3pnm%1002/ ) 1(nnm對