《圖與網(wǎng)絡》ppt課件-全文預覽
【正文】 在一個連通圖中割集是一些邊的集合，從 G中移去這些邊，則 G不連通，并且不存在這些邊的真子集使圖不連通 最短路問題 ? 設 G=(V,E)為連通圖，圖中各邊 (vi,vj)有權(quán) lij (lij=∞表示 vi,vj之間無邊 )， vs,vt為圖中任意兩點，求一條路 μ，使它是從 vs到 vt的所有路中總權(quán)數(shù)最小的路?；芈放c圈的區(qū)別是所有弧的方向一致。 ? 城中的居民經(jīng)常沿河過橋散步，于是提出了一個問題：能否一次走遍 7座橋，而每座橋只許通過一次，最后仍回到起始地點。第四章 圖與網(wǎng)絡 圖和網(wǎng)絡 ? 圖論廣泛地應用與物理學、化學、控制論、信息、科學管理、電子計算機等領(lǐng)域。 哥尼斯堡七橋問題 ? 18世紀在哥尼斯堡城 (今俄羅斯加里寧格勒 )的普萊格爾河上有 7座橋，將河中的兩個島和河岸連結(jié)，如圖 1所示。 ? 回路：起點和終點重合與同一節(jié)點的路。要求任何兩個城市都可以相互通話（允許通過其他城市），并且電話線的根數(shù)最少。 ? 條件： 網(wǎng)絡中所有的弧權(quán)為非負。 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3[∞] v6 [∞] [∞] [∞] [∞] [∞] 7 (1) 首先給 v1以 P標號 ,P(v1)=0,其余所有點給 T標號 ,T(vi)=+∞； 最短路算法 (2) 由于弧 (v1,v2)、 (v1,v3) 、 (v1,v4)屬于 D，且 v2 、 v3 、 v4為 T標號，所以修改這三個點的標號： T(v2)=min{T(v2), P(v1)+ω12}=min{∞,0+4}=4 T(v3)=min{T(v3), P(v1)+ω13}=min{∞,0+2}=2 T(v4)=min{T(v4), P(v1)+ω14}=min{∞,0+5}=5 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3[2] v6 [4] [5] [∞] [∞] [∞] 7 最短路算法 (3) 比較所有 T標號， T(v3)最小， 故令 P(v3)=2 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3(2) v6 [4] [5] [∞] [∞] [∞] 7 最短路算法 (4) v3為剛得到 P標號的點，考察弧 (v3,v4)，(v3,v6)的端點 v4,v6 T(v4)=min{T(v4), P(v3)+ ω34}=min{5,2+2}=4 T(v6)=min{T(v6), P(v3)+ ω36}=min{∞,2+7}=9 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3(2) v6 [4] [5] [∞] [∞] [∞] 7 最短路算法 (5) 比較所有 T標號， T(v2), T(v4)最小，所以令P(v2)=P(v4) =4 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3(2) v6 [4] [4] [9
教學課件相關(guān)推薦
鄂ICP備17016276號-1