教案圖與網(wǎng)絡(luò)之二ppt課件(編輯修改稿)
2025-05-27 18:11 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 給發(fā)點(diǎn) s標(biāo)號(hào) ,記為 ,括號(hào)中第一個(gè)數(shù)字是使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào) ,第二個(gè)數(shù)字表示從上一個(gè)標(biāo)號(hào)點(diǎn)到這一標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值 。⒉ 找出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn) . ⑴ 考慮從標(biāo)號(hào)點(diǎn) i出發(fā)的弧 (i,j),如有不給 j點(diǎn)標(biāo)號(hào) 。若有 則對(duì) j點(diǎn)標(biāo)號(hào) ,記為 其中 i表示 j點(diǎn)的標(biāo)號(hào)是從 i點(diǎn)延伸過(guò)來(lái)的 , (正向弧 )⑵ 考慮所有指向 i的弧 (h,i),如有 對(duì) h點(diǎn)不標(biāo)號(hào) ,若有 則對(duì) h點(diǎn)標(biāo)號(hào) ,記為 (反向弧 )⑶ 如果某未標(biāo)號(hào)點(diǎn) k有兩個(gè)以上的相鄰的標(biāo)號(hào)點(diǎn) ,為減少迭代次數(shù) ,可按 (1),(2)中的規(guī)則 ,分別計(jì)算 的值 ,取其中最大的一個(gè)標(biāo)記 .⒊ 重復(fù)步驟 2,可能出現(xiàn)兩種結(jié)局 :⑴ 標(biāo)號(hào)過(guò)程中斷 ,t點(diǎn)得不到標(biāo)號(hào) ,說(shuō)明網(wǎng)絡(luò)中不存在增廣鏈 ,網(wǎng)絡(luò)中給定的流就是最大流 .計(jì)算結(jié)束 。⑵ t點(diǎn)得到標(biāo)號(hào) ,這時(shí)反向追蹤 ,在網(wǎng)絡(luò)中找到一條從 s到 t 的由標(biāo)號(hào)點(diǎn)和相應(yīng)的弧連結(jié)而成的增廣鏈 .⒋ 修改流量 :設(shè)在網(wǎng)絡(luò)中原有的流量為 f.⒌ 抹去網(wǎng)絡(luò)圖中的所有標(biāo)號(hào) ,重復(fù)第 1到第 4步 ,一直到在網(wǎng)絡(luò)中找不到任何增廣鏈 ,即出現(xiàn)第 3步的結(jié)局 (1)為止 ,這時(shí)網(wǎng)絡(luò)中的流量為網(wǎng)絡(luò)的最大流 .FordFulkerson標(biāo)號(hào)法 (小節(jié) )n FordFulkerson標(biāo)號(hào)算法，給每個(gè)節(jié)點(diǎn)以一對(duì)標(biāo)號(hào)，第一個(gè)標(biāo)號(hào)表示箭尾節(jié)點(diǎn)，第二個(gè)標(biāo)號(hào)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1