離散數(shù)學(xué)圖的基本概論-資料下載頁(yè)
2025-01-16 20:24本頁(yè)面
【正文】 li(r)* +wij}， li(r)* 是剛剛獲得 p標(biāo)號(hào)頂點(diǎn)的 p標(biāo)號(hào)。 令 r ? r+1， 轉(zhuǎn) step1。 例 求下圖中頂點(diǎn) v0與 v5之間的最短路徑 v0 v2 v1 v4 v3 v5 1 2 1 4 7 5 3 2 6 解 ：利用標(biāo)號(hào)法算法解此題 開(kāi)始， r?0， v0獲 p標(biāo)號(hào)： l0(0)* = 0 l1(0) = w01 = 1 通過(guò)集 P0 = {v0}， 未通過(guò)集 T0 = {v1， v2 ， v3， v4， v5}， l2(0) = w02 = 4 l4(0) = ? = l5(0) l3(0) = w03 = ? 未通過(guò)集的 t 標(biāo)號(hào)： v0 v2 v1 v4 v3 v5 1 2 1 4 7 5 3 2 6 第一步 ： r = 1， 計(jì)算 = l1(1)* = 1， 所以 i=1， P1 = {v0, v1}， T1 = {v2,v3 ,v4,v5} 修改未通過(guò)集的 t標(biāo)號(hào)： l2(1) = min{l2(0), l1(1)* + w12} = min{4,3} = 3 l3(1) = min{l3(0), l1(1)* + w13} = min{?,8} = 8 l4(1) = min{l4(0), l1(1)* + w14} = 6 l5(1) = min{l5(0), l1(1)* + w15} = ? }{m in )0(0jv lTj?vi獲 p標(biāo)號(hào) l1(1)*， 修改通過(guò)集與未通過(guò)集 : 修改通過(guò)集與未通過(guò)集 P2 = {v0, v1, v2}， T2 = {v3 ,v4,v5} 修改未通過(guò)集的 t標(biāo)號(hào)： l3(2) = min{l3(1), l2(2)* + w23} = min{8,3+?} = 8 l4(2) = min{l4(1), l2(2)* + w24} = min{6,3+1} = 4 l5(2) = min{l5(0), l2(2)* + w25} = min{?,3+?} = ? ，，計(jì)算第二步 23}{m i n2 )1(2( 1 )jTv1j???? ? illr3 )*2(22 ?lpv 標(biāo)號(hào)獲修改通過(guò)集與未通過(guò)集 P3 = {v0, v1, v2 ,v4},T3 = {v5 ,v3} 修改未通過(guò)集的 t標(biāo)號(hào)： l3(3) = min{l3(2), l4(3)* + w43} = min{8,4+3} = 7 l5(3) = min{l5(2), l4(3)* + w45} = min{?,4+6} = 10 ，所以，計(jì)算第三步 44}{m i n3 )2(4( 2 )jTv2j???? ? illr4)*3(44 ?lpv 標(biāo)號(hào)獲修改通過(guò)集與未通過(guò)集 P4 = {v0, v1, v2 ,v4 ,v3},T4 = {v5} 修改未通過(guò)集的 t標(biāo)號(hào)： l5(4) = min{l5(3), l3(4)* + w35} = min{10,7+2} = 9 ，所以，計(jì)算第四步 37}{m i n4 )3(3( 3 )jTv3j???? ? illr7*)4(33 ?lpv 標(biāo)號(hào)：獲修改通過(guò)集與未通過(guò)集 P5 = {v0, v1, v2 ,v4 ,v3 ,v5}, T5 = ? 由于 T5 = ?， 過(guò)程結(jié)束，得 v0到 v5的最短路徑為： ? = v0, v1, v2 ,v4 ,v3 ,v5 ， 且 w(?) = 9 ，所以，計(jì)算第五步 59}{m i n5 )4(5( 4)jTv4j???? ? illr9)*5(55 ?lpv 標(biāo)號(hào)：獲標(biāo)號(hào)法的說(shuō)明： (1)標(biāo)號(hào)法可求任何頂點(diǎn) Vs到其它任一頂點(diǎn)之間的最短路徑 ， 只是算法的 “ 開(kāi)始 ” 步中 ，先給頂點(diǎn) Vs加 p標(biāo)號(hào) 0， 即 ls(0)* = 0， 然后算法往下計(jì)算 。 (2)若已經(jīng)求出從 vi到 vj的最短路徑，則從 vi到此路徑上其余各頂點(diǎn)的最短路徑也都求出了。 歐拉圖與哈密爾頓圖 如果存在一條通路，它經(jīng)過(guò) G的每條邊一次且僅一次，則稱(chēng)該通路為 歐拉通路 ； 具有歐拉回路的圖 ––– 歐拉圖 。 歐拉圖 ：給定無(wú)孤立頂點(diǎn)的圖 G， 存在一條回路，它經(jīng)過(guò) G的每條邊一次且僅一次，則此回路為 歐拉回路 。 如果 歐拉圖的判定定理 ： (1) 無(wú)向圖 G具有一條 歐拉回路 ， 當(dāng)且僅當(dāng) G是 連通 的 ， 并且所有頂點(diǎn)的 度數(shù)全為偶數(shù) ； (2) 有向圖 D具有單向 歐拉回路 ， 當(dāng)且僅當(dāng) D是 連通 的 ， 并且每個(gè)頂點(diǎn)的 入度等于出度 。 (3) 無(wú)向圖 G有 歐拉通路 ，當(dāng)且僅當(dāng)它連通且有 零個(gè)或兩個(gè) 奇數(shù)度頂點(diǎn)； (4) 有向圖 D有 歐拉通路 ，當(dāng)且僅當(dāng)它連通且 除兩個(gè)頂點(diǎn)外 ，各頂點(diǎn)的 入度均等于出度 。 證明較復(fù)雜 (略 )。 哈密爾頓圖 ：給定圖 G， 如果存在一條經(jīng)過(guò) G的每個(gè)頂點(diǎn)一次且恰好一次的通路(回路 )，則稱(chēng)該通路 (回路 )為哈密爾頓通路 (回路 )。 具有哈密爾頓回路的圖稱(chēng)為哈密爾頓圖。 哈密爾頓圖的充分必要條件 至今仍未解決 。 例 下列圖哪些為歐拉圖： (1) (2) (3) (4) 小結(jié)與學(xué)習(xí)要求 1. 本章圍繞圖中元素間的鄰接與關(guān)聯(lián)關(guān)系討論了圖論中幾個(gè)基本問(wèn)題：圖的連通性問(wèn)題 ，道路問(wèn)題 ， 可達(dá)性問(wèn)題 ， 最短路徑問(wèn)題 。 2. 要仔細(xì)領(lǐng)會(huì)和掌握下列基本概念和相關(guān)結(jié)論：子圖 、 度 、 通路 、 回路 、 支 、 割點(diǎn) ， 割邊 ， 獨(dú)立點(diǎn) ， 權(quán) ， 補(bǔ)圖 ， 同構(gòu)圖等 。 3. 熟練掌握標(biāo)號(hào)法 。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1