圖與網(wǎng)絡ppt課件(參考版)
2025-05-15 07:51本頁面
【正文】 弧上的數(shù)字為每段的距離（里數(shù)），求 Va,Vb間的最短路。 第一 標號過程 ? 可擴充量 ? 標號 – 正向 (Vi,Vj) – 反向 (Vj,Vi) ij ij ijij ic f V i jVf V i j???????? ???? ????m in( , ( ) ) ,()m in( , ( ) ) ,ijVV??[ , ( )]ijVV??[ , ( )]第二 調(diào)整過程 39。 0 ( , )0 ( , )ij ij i jij ij i jf c v vc f v v????? ? ? ??? ? ? ???最大流算法 —— 標號算法 ? 思路： 找出一條從發(fā)點輸送正流到收點的鏈 ——增廣鏈，利用這條路把盡可能多的流從發(fā)點送到收點，重復這個過程，直到再也找不出增廣鏈為止，這時網(wǎng)絡上的流就是最大流。 0 ij ijfc??ij k ijkff???s i jtijf f W????最大流－最小割 最大流－最小割 ? 在容量網(wǎng)絡中割集是由 vs到 vt的必經(jīng)之路，無論拿掉哪個割集， vs到 vt便不再相通，所以任何一個可行流的流量不會超過任一割集的容量； ? 定理：任一個網(wǎng)絡 G中，從 vs到 vt的最大流的流量等于分離 vs、 vt的最小割的容量。 基本概念 ? 容量： G=(V,E)，每條邊上有非負數(shù) cij稱為邊的容量； ? 發(fā)點（源），收點（匯），中間點； ? 對 G中的邊（ vi,vj）有流量 fij,稱集合 f={fij}為網(wǎng)絡 G上的流； 基本概念 ? 可行流 – 容量限制：對 G中的每條邊（ vi,vj） ,有 – 平衡條件：對中間點 vi,有 對收點、發(fā)點有 ? 所謂最大流問題，就是在容量網(wǎng)絡中，尋找流量最大的可行流。 ? 可以用求最短路問題的方法來解決總費用最少的設備更新計劃問題。若購買新設備就要支付購置費；若繼續(xù)使用舊設備，則需支付維修費用。 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 (4) (4) (7) (13) (8) v3(2) v6 7 計算結(jié)果見上圖， v1到 v7的最短路為： 76431 vvvvv ????765431 vvvvvv ?????同時得到 v1到其余各點的最短路。 D氏標號法步驟 最短路問題 ? ? ? ? ? ? ? v1 v2 v7 v5 v4 1 7 1 3 4 4 4 5 2 5 7 2 v3 v6 最短路求解 圖中 ( )內(nèi)的數(shù)表示 P標號， [ ]內(nèi)的數(shù)表示 T標號 。 ? 開始給發(fā)點標上 P(Vs)=0, 其余節(jié)點標上臨時標號T(Vj)=∞， j≠1。迪科斯徹 ? 家鄉(xiāng)： 荷蘭 ? 出生年月： 1930年 5月 11日 ? 去世年月： 2022年 8月 6日 ? 成就： – 1972年獲得過素有計算機科學界的諾貝爾獎之稱的圖靈獎 – 1989年 ACM SIGCSE計算機科學教育教學杰出貢獻獎 – 2022年 ACM PODC最具影響力論文獎 D氏標號法 ? 思路： 從始點出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。 V2 V1 V3 V4 V5 圖的基本概念小結(jié) ? 邊、弧 ? 無向圖、有向圖 –
教學課件相關推薦
鄂ICP備17016276號-1