圖與網(wǎng)絡(luò)ppt課件-資料下載頁(yè)
2025-05-12 07:51本頁(yè)面
【正文】 ，如何安排各管道的輸油量，才能使從 vs到 vt總油量最大？ 最大流問(wèn)題 ? 管道網(wǎng)絡(luò)中每邊的最大通過(guò)能力即容量是有限的，實(shí)際流量也并不一定等于容量； ? 如何充分利用裝置的能力，以取得最好效果（流量最大），這類問(wèn)題通常稱為最大流問(wèn)題。 基本概念 ? 容量： G=(V,E)，每條邊上有非負(fù)數(shù) cij稱為邊的容量； ? 發(fā)點(diǎn)（源），收點(diǎn)（匯），中間點(diǎn)； ? 對(duì) G中的邊（ vi,vj）有流量 fij,稱集合 f={fij}為網(wǎng)絡(luò) G上的流； 基本概念 ? 可行流 – 容量限制：對(duì) G中的每條邊（ vi,vj） ,有 – 平衡條件：對(duì)中間點(diǎn) vi,有 對(duì)收點(diǎn)、發(fā)點(diǎn)有 ? 所謂最大流問(wèn)題，就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。 ? 當(dāng) fij=cij,則稱流對(duì)邊（ vi,vj）是飽和的。 0 ij ijfc??ij k ijkff???s i jtijf f W????最大流－最小割 最大流－最小割 ? 在容量網(wǎng)絡(luò)中割集是由 vs到 vt的必經(jīng)之路，無(wú)論拿掉哪個(gè)割集， vs到 vt便不再相通，所以任何一個(gè)可行流的流量不會(huì)超過(guò)任一割集的容量； ? 定理：任一個(gè)網(wǎng)絡(luò) G中，從 vs到 vt的最大流的流量等于分離 vs、 vt的最小割的容量。 最大流算法 ? 增廣鏈（路） – 容量網(wǎng)絡(luò) G， μ為從 vs到 vt的一條鏈，給 μ定向?yàn)閺膙s到 vt，與 μ同向的邊稱為前向邊，記為 μ＋ 與 μ反向稱為后向邊，記為 μ－ f 為可行流，如果滿足： 則稱記為 μ為從 vs到 vt的一條增廣鏈。 0 ( , )0 ( , )ij ij i jij ij i jf c v vc f v v????? ? ? ??? ? ? ???最大流算法 —— 標(biāo)號(hào)算法 ? 思路： 找出一條從發(fā)點(diǎn)輸送正流到收點(diǎn)的鏈 ——增廣鏈，利用這條路把盡可能多的流從發(fā)點(diǎn)送到收點(diǎn)，重復(fù)這個(gè)過(guò)程，直到再也找不出增廣鏈為止，這時(shí)網(wǎng)絡(luò)上的流就是最大流。 ? 增廣鏈： 從發(fā)點(diǎn)到收點(diǎn)的鏈，前向弧的流量小于容量，后向弧的流量大于零。 第一 標(biāo)號(hào)過(guò)程 ? 可擴(kuò)充量 ? 標(biāo)號(hào) – 正向 (Vi,Vj) – 反向 (Vj,Vi) ij ij ijij ic f V i jVf V i j???????? ???? ????m in( , ( ) ) ,()m in( , ( ) ) ,ijVV??[ , ( )]ijVV??[ , ( )]第二 調(diào)整過(guò)程 39。( ) , ( , )( ) , ( , )( , )ij t i jij ij t i jij i jf V V Vf f V V Vf V V?????? ? ? ??? ? ? ?????最大流問(wèn)題 1 ? 2[ ,1]V[ ,4]s??1[ ,1]VVs V2 V1 3,3 5,1 V4 V3 Vt 4,3 2,2 5,3 2,1 3,0 1,1 1,1 [ , ]s ?? 2[ ,1]V? 3[ ,1]V[c,f] 最大流問(wèn)題 2 [ ,3]s?Vs V2 V1 3,3 5,2 V4 V3 Vt 4,3 2,2 5,3 2,2 3,0 1,0 1,0 [ , ]s ?習(xí)題 ? 用標(biāo)號(hào)法求圖示的最短路 習(xí)題 ? Va, Vb兩城市公路網(wǎng)。弧上的數(shù)字為每段的距離（里數(shù)），求 Va,Vb間的最短路。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1