運籌學(xué)第八章ppt課件(參考版)
2025-05-06 18:36本頁面
【正文】 一、標號過程 二、調(diào)整過程 其實，這是尋找增廣鏈的過程，如果不能把 vt進行標號時，即不存在增廣鏈，根據(jù)定理，初始流就是最大流，結(jié)束，否則轉(zhuǎn)第二步 1）令 fij = fij + δt 前向邊 fij – δt 后向邊 fij 其他 2)擦除所有標號，重新開始 第四節(jié) 最大流問題 5）非標準網(wǎng)絡(luò)的最大流問題 （ 1）發(fā)點不唯一 （ 2）收點不唯一 （ 3）收發(fā)點都不唯一 例： P273 6）最大匹配問題 （ 2）匹配定義： （ 1）背景：簡介 ——工作安排 二部圖 G=（ X， Y， E）， 若 M中任意兩條邊都沒有公共端點 例： P274 第四節(jié) 最大流問題 。 零流邊 ：如果 fij = 0 非零流邊 ：如果 fij 〉 0 前向邊 ：如果鏈 lst , 如果方向與 st同向，稱前向邊；否則稱為反向邊 最大流 —最小割定理 頂點的流量 ： ∑ fij － ∑ fji 割 集：設(shè) G=（ V， E， C）， E’是 E的子集， V1 ∪ V2 =V， V1∩V2=φ且發(fā)點 s ∈ V1， 收點 t ∈ V2， G=（ V， EE’)不連通，稱 E‘為 G的割集。問如何進行調(diào)度，才能充分利用能夠提供的運量，使盡可能的煤運往 B地？ 2 10 3 1 3 5 8 9 4 7 4 網(wǎng)絡(luò) ： 加權(quán) 有向 連通圖 ，僅有一個 入次為 0的點，有一個 出次為 0的點。樹中次為 1的點稱葉，否則稱分支點 定理 6 1. T是樹 2. T無圈且 m=n1(其中 n為頂點數(shù)， m為邊數(shù)，下同 ) 3. T連通且 m=n1 4. T無圈，但加一條新邊即得唯一圈 5. T連通，但舍去任一邊則不連通 6. T任意兩點有唯一鏈相連 定義十四 無向圖 G中，如生成圖為樹，則該樹為圖 G的生成樹 定理 無向圖 G中有生成樹充分必要條件為 G連通樹 第一節(jié) 圖與網(wǎng)絡(luò)的基本知識 第二節(jié) 樹及其最小生成樹 最小生成樹算法： 1） Kruskal 2） 破圈法 避圈法（ Kruskal） 6 4 4 5 8 4 3 5 5 7 2 5 6 vs 6 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1