運籌學第八章ppt課件-資料下載頁
2025-05-03 18:36本頁面
【正文】 收點 t ∈ V2， G=（ V， EE’)不連通，稱 E‘為 G的割集。 割集的 容量 ： ∑ fij， vi ∈ V1, vj ∈ V2， 記 C（ V1， V2） 第四節(jié) 最大流問題 定理 41: 設 G=（ V， E， C）， V1， V2為割集， fij為 G的任一可行流， W為其流量，必有 CV1， V2） ≥W 最大流 —最小割定理 : 設 G=（ V， E， C）， E’=（ V1， V2）為割集， fij為最大流充分必要條件 W=min（ C（ V1， V2） | E’為 G的割集） 定理 42: 設 G=（ V， E， C）， fij為為最大流充分必要條件不存在增廣鏈 利用該定理求最大流，如何求？ 枚舉法 把求 最大流 轉化為求是否存在 增廣鏈 問題 第四節(jié) 最大流問題 如何求 增廣鏈？ 最大流的 標號算法 算法 ： （前提條件為已經存在可行流） 1）從發(fā)點開始標號（） 2）選擇一個已經標號頂點 vi， 對于與頂點 vi相鄰而未標號的頂點 （ vj）進行如下處理 ： （ 1）若（ vi ， vj） ∈ E， 且 fijcij， 則令 δj = min(cijfij, δi)， 并給 vj標以（ +vi, δj) （ 2） 若（ vj ， vi） ∈ E， 且 fji0， 則令 δj = min(fji, δi)， 并給 vj標以（ vi, δj) 3）重復（ 2）直到收點 vt或不再有頂點可標記為止。 一、標號過程 二、調整過程 其實，這是尋找增廣鏈的過程，如果不能把 vt進行標號時，即不存在增廣鏈，根據(jù)定理，初始流就是最大流，結束，否則轉第二步 1）令 fij = fij + δt 前向邊 fij – δt 后向邊 fij 其他 2)擦除所有標號，重新開始 第四節(jié) 最大流問題 5）非標準網絡的最大流問題 （ 1）發(fā)點不唯一 （ 2）收點不唯一 （ 3）收發(fā)點都不唯一 例： P273 6）最大匹配問題 （ 2）匹配定義： （ 1）背景：簡介 ——工作安排 二部圖 G=（ X， Y， E）， 若 M中任意兩條邊都沒有公共端點 例： P274 第四節(jié) 最大流問題
教學課件相關推薦
鄂ICP備17016276號-1