教案圖與網(wǎng)絡(luò)之二ppt課件-在線瀏覽
2025-06-17 18:11本頁(yè)面
【正文】 rson標(biāo)號(hào)法⒈ 首先給發(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)整值 。若有 則對(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é)束 。否則不存在增廣鏈。經(jīng)過(guò)調(diào)整網(wǎng)絡(luò)流 v(f)增加一個(gè)調(diào)整量：例 42：第一次迭代第二次迭代第三次迭代：最優(yōu)解四、確定網(wǎng)絡(luò)中最大流的方法n 最大流時(shí)始節(jié)點(diǎn)的凈流出量n 最大流時(shí)中介點(diǎn)的凈流入量n 最小割集的容量n 割集n 割集容量n 最小割集n 最小割集最大流定理n 標(biāo)號(hào)法求得最小割集在下圖中 ,括弧外的數(shù)字表示最大通過(guò)量 ,括弧內(nèi)的數(shù)字為負(fù)載 .割集 :將網(wǎng)絡(luò)流中的發(fā)點(diǎn)和收點(diǎn)分割開(kāi) ,使 s到 t的流中斷的一個(gè)弧集合 . 割量 :割的弧集合中各弧的容量之和 ,用表示 ,顯然 , 割 割的容量
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1