【正文】 稱為 頂點 ； U是有序積 V V的一個子集，其元素稱為 弧 。令邊是僅有一端為 U1中頂點的各條邊的最短邊，則在包含 中 中所有邊的生成樹中，必存在含 et=(vi,vj)的最小生成樹。 167。其中， vi,vj是賦權(quán)圖 G中給定的頂點， vi稱為起點， vj稱為終點。 167。 求一個連通圖 G的生成樹的主要方法有： 避回路法 ： 任取圖 G的一條邊 e1，再取一條邊 e2 ， e2和 e1不構(gòu)成回路；然后再取一條邊 e3 ， e3和 e1 e2不構(gòu)成回路。 T中的邊稱為 樹枝 ，屬于 G而不屬于 T中的邊稱為 弦 。 圖論基礎（ 7） 割邊 ： 如果去掉圖的一條邊后，剩下的圖的支比原圖增加，則稱這樣的邊為割邊，或稱為 橋 。若在 T中的任何兩個不鄰接的頂點連一條邊 e，則Ｔ＋ e恰有一條回路。 圖論基礎（ 6） 二、樹 基本概念 樹 :一個連通的無回路的圖。 交 ：由 G1和 G2中的公共邊組成的圖，記作 。若不存在連接 u和 v的路，則記 d(u,v)=∞ 。 連通圖 ：一個圖的每一對頂點都有一條路連接。用Ｃ n記由一條有n個頂點的回路構(gòu)成的一個圖。 圖論基礎（ 4） 鏈 :設 μ=v 0e1v1e2v2… envn是路徑，若路徑 μ 的邊e1,e2,… ,en均不同，則 μ 稱為鏈。 這條路徑連接 v0和 vn，也可記作 v0v1… vn1vn，有時也稱它為（ v0, vn）路徑。只有一條邊兩個頂點的圖是 1度正則的。 圖論基礎（ 3） 頂點的度 :G的頂點 v的度 d(v)是指 G中與 v關聯(lián)的邊的數(shù)目，每個環(huán)算作兩條邊。有 n個頂點的完全圖記作 Kn。 有限圖 ：一個圖中頂點集及邊集都是有限集。 167。 圖論基礎（ 1） 一、圖 圖的概念 圖 :一個圖 G是指一個有序三元組（ V（ G）， E（ G）， Ψ G），其中 V（ G）是非空的頂點集， E（ G）是邊集， Ψ G是關連函數(shù)，它使 G的每條邊對應于 G的無序頂點對（不必相異）。 最短路徑分析 167。第五章 網(wǎng)絡分析模型 167。 最佳路徑分析 167。 邊 :E中的每個頂點對（ u,v）稱為 G的邊，記為 e =（ u,v）或簡記為 e = uv，稱 u，v是邊 e的 端點 ，且稱 u和 v是 鄰接的頂點 。 圖論基礎（ 2） 若連結(jié)兩個頂點有不止一條邊，這些邊稱為 多重邊 。 （ u,v） 空圖 ：沒有邊的圖，記為 Φ 。 子圖 ：所有的頂點和邊都屬于 G的圖稱為 G的子圖。 設 G是一個（ p,q）圖，那么 G的各個頂點度的和是邊數(shù)的二倍，即 正則圖 ：如果圖 G的所有頂點的度均相等，則稱為正則的。完全圖是正則的。如果 v0=vn，它稱為 閉合的 ，否則稱為 開的 。 路 :若路徑的所有頂點都不同 (從而所有的邊必然不同 )，它稱為路。若 n為奇數(shù)，則Ｃ n稱為奇回路，若 n為偶數(shù)，則Ｃ n稱為偶回路。 連通支 ： G的一個最大的連通子圖稱為一個連通支。 167。 差 ：由 G1中去掉 G2的邊所得到的圖稱為 G1和 G2的差，記作 。 林 :每個支都是樹的分離圖稱為林。 定理 ：設Ｇ是一個（ p,q）圖，若Ｇ是連通的，且 q = p1，則Ｇ是一棵樹。 記 W(G)為圖 G不連通子圖的數(shù)目，則 G的割邊是指使得W(Ge)W(G)的邊 e。 生成林 :若 G為分離圖，則稱 T為生成林。如此下去，最后得到的不含回路的連通生成子圖就是 G的一棵生成樹。 圖論基礎（ 9） 三、最短路徑和最小生成樹 最短路徑 賦權(quán)圖 :若圖 G的每一條邊（ vi,vj）相應的有一個數(shù) l（ vi,vj）（或簡記為 lij） ,稱此數(shù)為該邊的 權(quán) ，則圖 G為賦權(quán)圖。從 vi到 vj的最短路徑的權(quán)記作 d（ vi,vj）。 圖論基礎（ 10） 最小生成樹問題（ MST） 最小生成樹問題 :在賦權(quán)網(wǎng)絡 N中，求解權(quán)數(shù)總和最小的生成樹。 ? ? ? ?? ?0,},{ ??? lll ewEeewW其中，? ? ? ? min?? ?? Tt Ee tewTW?kjjET1??167。 基礎圖 ：若對有向圖 D，可以在頂點集合 V上作一個圖 G，使得對應于 D的每一條弧， G有一條相同端點的邊，這樣得到的無向圖 G稱為有向圖 D的基礎圖。v0稱為 w的 起點 ， vk稱為 w的 終點 ， k稱為 w的 長 。 如果在有向圖 D中，存在一條（ u,v）的有向路，那么頂點 v叫做在 D中從頂點 u出發(fā)是可到達的 ，或者說 由 u可到達 v。 入度 :有向圖 D中從頂點 v為終點的弧的數(shù)目叫做 v的入度，記作 。 圖論基礎（ 14） 定理 ：設 D是連通有向圖，對任意 v∈V （ D），如果 那么 D恰有一條有向回路。 從 Ae中去掉一行，且秩為 p1的矩陣，稱為 D的 關聯(lián)矩陣 ，記作 A。 167。 網(wǎng)絡分析的主要研究內(nèi)容 ：最短路徑分析、資源分配、連通分析、流分析等。 167。資源通過在網(wǎng)絡中的流動實現(xiàn)傳輸和分配。屬性信息包括阻礙強度、資源需求量、資源流動的約束條件。 中心 ：網(wǎng)絡中具有一定的容量，能夠從鏈上獲取資源的結(jié)點所在地。其屬性主要是拐角的阻礙強度。主要有概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型、物理數(shù)據(jù)模型。 物理數(shù)據(jù)模型： 是通過一定的數(shù)據(jù)結(jié)構(gòu)，完成空間數(shù)據(jù)的物理組織、空間存取及索引方法的設計。 設 P為 G中兩點間的一條有向路徑，定義 P的權(quán)值 則 G中兩點間權(quán)最小的有向路徑稱為這 兩點的最佳路徑 。 ? ? ? ?? ????PEeewPW167。按研究的目標可有不同的分類。 Dijkstra算法的基本思想 ： 標記源點到已得到點的最短路徑，再尋找到下一個點的最短路徑（由近及遠尋找起點到其他節(jié)點的最佳路徑，直至到達目標節(jié)點）。將起源點 s標號，記 k=s，其他點尚未處理； （ 2）距離計算。從已標記的點中找到連接到點 i的前一點 j*,并令 i=j*作為前一點。 Dijkstra算法 例： 用 Dijkstra算法求解如圖所示的最短路徑。 Dijkstra算法 （ 4） k=4， 顯然 d（ 3） = 50最小，標記 （ v4,v3） ，即 （ v4,v3）是從 v4到 v3的最短路徑。 反向追蹤，可得 v0到 vi的最短路徑。若存在，則比較（ vi,vj）和（ vi,v1,vj）的路徑長度，較短者為從 vi到 vj的中間頂點的序號不大于 1的最短路徑； 2）假如在路徑上再增加一個頂點 v2，若路徑（ vi,… ,v2）和（ v2,… ,vj）分別是當前找到的中間頂點的序號不大于 1的最短路徑，那么后來的路徑（ vi,… ,v2,… ,vj）有可能是從 vi到 vj的中間頂點不大于 2的最短路徑。 Floyd算法 Floyd算法的基本步驟 ： （ 1）設置初值，令 Aij＝ w(vi,vj)，若 w(vi,vj)＜ ∞ ， 且 i≠j ，則令 Pij＝ [i]+[j]； （ 2）對 k＝ 1,2,… ,n, j ＝ 1,2,… ,n, 判斷是否有 Aik+Akj＜ Aij，若是，置 Aij ＝ Aik+Akj ， Pij ＝ Pik+Pkj ； （ 3）迭代 n次之后，算法結(jié)束， Aij 為從 vi到 vj 的最短路徑的長度， Pij 為相應的最短路徑 。 估計函數(shù)： f*(j)=g(j)+h*(j) 優(yōu)點： 可以首先搜索可能性較大的結(jié)點，提高搜索效率。 （ 1）設置初值； （ 2）從 T中