空間網(wǎng)絡分析

空間對象分類看得見的線狀分布：如河流、道路、鐵路、輸電線路、供水管道、政區(qū)邊界等。上述線狀分布在三維空間中是實際存在的，是看得見，摸得著的；看不見的線狀分布：如地理區(qū)域之間、城市之間、工廠之間的聯(lián)系，無線通訊網(wǎng)和航空線路等。這些線狀分布是不可見的，只有通過設計和調查在相關圖件上加以表達。無論是何種線狀分布，它們都是通過線連接在點上的。這些點稱為頂點或節(jié)點，兩個點之間的線稱為環(huán)、弧或邊，節(jié)點和環(huán)線系統(tǒng)就稱為網(wǎng)絡。節(jié)點和環(huán)線是構成網(wǎng)絡的兩個基本要素。空間網(wǎng)絡的類型空間網(wǎng)絡的拓撲分類平面網(wǎng)絡（二維）非平面網(wǎng)絡（非二維）線型“流”系統(tǒng)線型柵格系統(tǒng)線型立體系統(tǒng)道路型樹型環(huán)網(wǎng)型細胞型交錯型網(wǎng)絡圖基本概念有向圖和無向圖路與回路圖中的一條路，就是由圖中的一個頂點、一條邊，再一個頂點、一條邊…排列而成，而且要求排在它前面的頂點和排在它后面的頂點都是它的端點。對于有向路來說，要求排在每一條邊之前和之后的頂點分別是這條邊的起點和終點連通性如果無向圖內任意兩個頂點之間存在著一條連接它們的路，則稱這個無向圖是連通的，如圖5-22(a)，反之，則稱為不連通的，如圖5-22(b)。連通性也可以用來研究有向圖。一個有向圖，如果不考慮它的邊的方向，如果它是連通的，則稱這個有向圖是連通的；如果在一個有向圖中，它的任意兩個頂點都存在著一條連接它們的有向路，那么這個有向圖就稱為具有強連通性。圖5-22(c)是不連通圖，而圖5-22(d)則是強連通圖。網(wǎng)絡圖的矩陣表達鄰接矩陣：G的頂點集V中每兩點間的鄰接關系唯一確定。（頂點與頂點之間的鄰接關系）

dij=1Vi和Vj鄰接

dij=0Vi和Vj不鄰接關聯(lián)矩陣：G的v個頂點和e條邊的無向關聯(lián)矩陣。（頂點與邊之間的關聯(lián)關系）

aij=1ei

和Vj鄰接

bij=0ei和Vj不鄰接路徑分析1）靜態(tài)求最佳路徑：在給定每條鏈上的屬性后，求最佳路徑。2）N條最佳路徑分析：確定起點或終點，求代價最小的N條路徑，因為在實踐中最佳路徑的選擇只是理想情況，由于種種因素而要選擇近似最優(yōu)路徑。3）最短路徑或最低耗費路徑：確定起點、終點和要經過的中間點、中間連線，求最短路徑或最小耗費路徑。4）動態(tài)最佳路徑分析：實際網(wǎng)絡中權值是隨權值關系式變化的，可能還會臨時出現(xiàn)一些障礙點，需要動態(tài)的計算最佳路徑。路徑分析路徑分析例題路徑分析（pathanalysis）

迪克斯查（E.W.Dijkstra）提出的標號法是解決最短路徑問題最好的方法。這個方法的突出優(yōu)點是：它不僅求出了起點到終點的最短路徑及其長度，而且求出了起點到圖中其它各頂點的最短路徑和長度。路徑分析：設是一個有向圖的網(wǎng)絡，對于它的每條邊或每一對頂點都可以對應一個數(shù)。在實際應用過程中，對于的取值是這樣規(guī)定的：1.如果邊以為起點，為終點，則取這個邊的長度；2.如果頂點不是某一條邊為起點和終點，那么取值為：3.如果，取值為0。標號法過程v1v2v3v4v5v6V7v8v1012∞∞∞∞∞V210333∞∞∞V32302∞∞∞4V4∞32023∞3V5∞3∞203∞∞V6∞∞∞3301∞V7∞∞∞∞∞101v8∞∞43∞∞10W=v1v2v3v4v5v6V7v8起點0(∞)(∞)(∞)(∞)(∞)(∞)(∞)v10(1)(2)(∞)(∞)(∞)(∞)(∞)V201(2)(4)(4)(∞)(∞)(∞)V3012(4)(4)(∞)(∞)(6)V40124(4)(7)(∞)(6)V501244(7)(∞)(6)V801244(7)(7)6v701244(7)76標定定位配置分析(location-allocationanalysis)服務點的最優(yōu)區(qū)位問題在城市管理中，利用GIS技術確定服務點的最優(yōu)區(qū)位問題十分重要，如確定幼兒園、商場、消防隊、醫(yī)院、交通場站等的最優(yōu)位置，以達到服務、資源的最優(yōu)配置。最優(yōu)服務點的最優(yōu)區(qū)位問題有兩種算法供選擇

服務點的最優(yōu)區(qū)位問題算法1設G是一個n有個頂點：m條邊：的無向連通圖，那么對于每一個頂點，它與各頂點間的最短路徑的長度為：

最大數(shù)稱為頂點的最大服務距離，用表示

服務點的最優(yōu)區(qū)位問題算法1求出一個點使得具有最小的值。這樣處理數(shù)據(jù)的含義是很明顯的。因為在圖上找出這個點后，把服務點設在這個位置上，對于分散在各個頂點上的服務對象來說，最遠的服務對象與服務點之間的距離達到了最小。這個點稱為圖的中心。

首先計算出的距離表最后求，定出均是G的中心其次，計算每一行的最大值

服務點的最優(yōu)區(qū)位問題算法2設G是一個n有個頂點：m條邊：的無向連通圖，那么對于每一個頂點，它與各頂點間的最短路徑的長度為：

并設每個頂點有一個正負荷。現(xiàn)求出一個頂點，使得

最小，此點被認為是G點的中央點首先，計算G的距離方陣其次求出最后得到的中央點是和P-中心問題在m個候選點中選擇p個供應點，為n個需求點服務，并使得服務中心到各個需求點之間的總距離(時間，費用)為最小?？梢悦枋鰹椋篢eitz-Bart算法選取p個候選點作為起始供應點集Pt:C1,C2,...Cp將所有的需求點分配給他們最臨近的供應點，使其距離最短。計算總的加權距離Bt從未選取的候選點中選取一候選點Cb對Pt中的每個供應點Cj用Cb替換之，并計算總加權距離的變化如果供應點Cj用Cb替換后總加權距離減少，那么就替換總加權距離減少最多的供應點。重復3-5步，直至未被選取的點集為空當所有不在Pt中的候選點試過后其結果記為P’t重復2-7步，直到總加權距離不變?yōu)橹怪行姆辗秶拇_定中心服務范圍為滿足下列條件的網(wǎng)絡邊和結