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