地理网络的图论描述课件.pptVIP

地理網路的圖論描述地理網路的圖論描述地理網路的測度通俗意義上的“圖”，主要是指各種各樣的地圖、遙感影像圖，或者是由各種符號、文字代表的示意圖，或者是由各種地理數據繪製而成的曲線圖、直方圖等等。圖論中的“圖”，是一個數學概念，這種“圖”能從數學本質上揭示地理實體與地理事物空間分佈格局，地理要素之間的相互聯繫以及它們在地域空間上的運動形式、地理事件發生的先後順序等。（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橋問題東普魯士的哥尼斯堡城（現在的加裏寧格勒）是建在兩條河流的匯合處以及河中的兩個小島上的，共有7座小橋將兩個小島及小島與城市的其他部分連接起來，那麼，哥尼斯堡人從其住所出發，能否恰好只經過每座小橋一次而返回原處？圖論研究結果告訴我們，其答案是否定的。（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）中，若頂點與邊交替出