or教案23_圖論-資料下載頁
2025-09-30 15:13本頁面
【正文】 Cij。 問：如何調(diào)運使得收點的車輛最多？ ? 20 ? ? ? ? ? ? ? 10 50 20 15 20 10 30 10 30 20 50 多源、多匯的最大流問題 解決方法：虛設(shè)一個發(fā)點和一個收點？ 定義弧上的最大容量？ 運用 Fordfulkerson算法 ? 20 ? ? ? ? ? ? ? 10 50 20 15 20 10 30 10 30 20 50 ? ? 20 80 15 +? +? ? 20 ? ? ? ? ? ? ? 10 50 20 15 20 10 30 10 30 20 50 20 80 15 +? +? 計算結(jié)果： 110輛車 t s 最大匹配問題 考慮工作分配問題。 n個工人， m件工作。每人能力不同各勝其中某幾項，假定每人只做一件工作，每件工作只用一人作，怎樣分配才能使盡量多的工作完成，更多的人有工作？ 記 x1,x2,…,x n表示工人 記 y1,y2,…,y m表示工作 邊（ xi, yj ）表示 xi勝任 yj工作 上述問題構(gòu)成一個二部圖 G=(X,Y,E) 尋找邊集 E中的子集，使得集中的任何兩條邊沒有公共端點，最好的分配方案是此邊集合的邊數(shù)越多越好 ? x1 ? x2 ? ? xn ? y1 ? y2 ? ? yn ? +? +? vs vt 最大匹配問題可以化成多發(fā)點、多收點的最大流問題 例如： 5位待業(yè)者， 5項工作，他們各自能勝任工作情況如下圖所示： 要求設(shè)計一個就業(yè)方案，使得盡量多的人能就業(yè)。 ? x1 ? x2 ? x3 ? x4 ? x5 ? y1 ? y2 ? y3 ? y4 ? y5 vs vt ? x1 ? x2 ? x3 ? x4 ? x5 ? y1 ? y2 ? y3 ? y4 ? y5 1 vt 1 1 1 1 1 1 1 1 1 1 1 就業(yè)方案為最多 4人能就業(yè)。 x v1 v6 v2 v4 v5 v3 y 14 16 9 4 19 7 22 6 12 5 3 13 15 6 例 1 v2 v5 v3 4 9 3 10 6 4 3 4 3 4 8 2 v1 v5 v4 vt vs 練習(xí) 例 3 某產(chǎn)品從倉庫運往市場銷售。已知各倉庫的可供量、各市場的需求量及從 i倉庫至 j倉庫的路徑的運輸能力如下表（表中 0代表無路可通），試求從倉庫可運往市場的最大流量？ 市場 j 倉庫 i 1 2 3 4 可供量 A B C 30 0 20 10 0 10 0 10 40 40 50 5 20 20 100 需求量 20 20 60 20 多源、多匯 的最大流問題。 30 10 40 10 50 A B C 4 3 2 1 5 10 40 10 20s 100 20 20 t 60 20 20 2
外語相關(guān)推薦
鄂ICP備17016276號-1