【正文】 v6 1 5 2 3 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學(xué)院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 單位： 100米 : 衛(wèi)星加密電視的開播 ,受到大 家歡迎 ,要想收看加密電視必 須建一套有線電視網(wǎng)．我們 考慮這樣一個具體問題：設(shè) 某市六個個區(qū)之的相互距離 如下表所示，試確定表數(shù)據(jù) 形成的網(wǎng)絡(luò)中，如何布線能 布線最??？ 1 2 3 4 5 6 1 0 13 51 77 68 50 2 13 0 60 70 67 59 3 51 60 0 57 3 62 4 77 70 57 0 20 55 5 68 67 36 20 0 34 6 50 59 2 55 34 0 河南城建學(xué)院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 ２ .問題求解 : 最優(yōu)布線問題，就是要求任何兩地都有鏈相連，而使總線路最短，這個問題在圖論中也稱為最小樹題．作下圖，其中頂點 v1 ， v２ ， v３ ， v４ ， v５ ， v６ 分別表示兩區(qū)之間的距離． V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學(xué)院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 對于上圖，我們要找使布線最省的網(wǎng)絡(luò)模型．圖論中的破圈法可以解 決這個問題，具體過程如下：在圈 v1v２ v３ v1中，去掉最長邊 v２ v３ ＝ 60，同 樣去掉圈 v1v３ v６ v1， v２ v４ v５ v２ ， v３ v４ v５ v３ ， v3 v5v６ v3， v4v5 v6 v4， v1v3v4v1， v1v6v2v1， v2v5v6v2中最長的邊 v1v３ ＝ 51， v2v4＝ 70， v3v4＝ 57， v3v5＝ 36,v4v6＝ 55， v1v4＝ 77， v1v5＝ 68， v2v6＝ 59， v2v5＝ 67，最后構(gòu) 成的圖（如下）就是最省的 布線圖 ． 13 2 50 34 20 v2 v3 v1 v6 v4 v6 V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學(xué)院 167?，F(xiàn)要求從點到某一點 t的最 短路。 ? 所謂 k正則圖，即每頂點皆度 k的圖。 匈亞利算法： 0 * ⑥ 再給 X中 M1的非飽和點 x4給以標(biāo)號 0和標(biāo)記 *, 然后去掉 x4的標(biāo)記 *, 將與 x4鄰接的兩個點 y2, y3都給以標(biāo)號 4. 4 4 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 例 18：求下圖的最大匹配。（非同列同行的零） STEP3：最優(yōu)判別：達到 n個獨立零元。 河南城建學(xué)院 定義 2 滿足下述條件的流 f 稱為 可行流 ： ① (容量限制條件 ) 對每一邊 vivj, 有 0≤ fij ≤Cij 。 sv2v1v3vtv2 3 4 3 1 2 5 最大流問題 河南城建學(xué)院 定理 2 (最大流 —— 最小割定理 ) 任一個網(wǎng)絡(luò)中 G中 , 從 vs到 vt的 最大流的流量 等于分割 vs, vt的 最小割的 容量 . 推論 可行流 f是最大流的充要條件是不存在從 vs到 vt的 (關(guān)于 f的 )可增廣鏈 . 最大流問題 河南城建學(xué)院 實際問題中 ,一個網(wǎng)絡(luò)會出現(xiàn)下面兩種情況： ⑴ 發(fā)點和收點都不止一個 . 解決的方法是再虛設(shè)一個發(fā)點 vs和一個收點 vt ,發(fā) 點 vs到所有原發(fā)點邊的容量都設(shè)為無窮大 , 所有原收 點到收點 vt 邊的容量都設(shè)為無窮大 . ⑵ 網(wǎng)絡(luò)中除了邊有容量外 ,點也有容量 . 解決的方法是將所有有容量的點分成兩個點 ,如點 v有容量 Cv ,將點 v分成兩個點 v39。 PT圖 河南城建學(xué)院 例 24 一項工程由 13道工序組成 , 所需時間 (單位：天 )及先行工序如下表所示 (P172). 工序序號 A B C D E F G H I J K L M 所需時間 2 6 3 2 4 3 8 4 2 3 2 5 6 先行工序 A A B C,D D D D G,H G H,E J K 試問這項工程至少需要多少天才能完成 ? 那些工程不能延誤 ? 那些工程可以延誤 ? 最多可延誤多少天 ? PT圖 河南城建學(xué)院 工序序號 A B C D E F G H I J K L M 所需時間 2 6 3 2 4 3 8 4 2 3 2 5 6 先行工序 A A B C,D D D D G,H G H,E J K 先作出該工程的 PT圖 . A B 2 2 C 6 D 3 E 2 F 2 G 2 H 2 K 4 N 3 I 8 J 8 4 4 2 L 3 M 25 6 虛擬結(jié)點 PT圖 河南城建學(xué)院 這項工程至少需 要多少天才能完成 ? 就是要求 A到 N的最長路 ,此路徑稱為 關(guān)鍵路徑 . 那些工程不能延誤 ? 那些工程可以延誤 ? 最多可延誤多少天 ?關(guān)鍵路徑上的那些工程不能延誤 . AB22C6 D3E2F2G2H2K4N3I8J8442L3M256PT圖 河南城建學(xué)院 定理 若有向圖 G中 不存在有向回路 ,則可以將 G 的結(jié)點重新編號為 u1, u2, …, un,使得對任意 的邊 ui uj∈ E(G),都有 i＜ j . 關(guān)鍵路徑 最長路算法 各工序最早啟動時間算法步驟： ① 對結(jié)點重新編號為 u1, u2, …, un . ② 賦初值 ?(u1)= 0. ③ 依次更新 ?(uj ),j = 2, 3, … , n . ?(uj )= max{?(ui )+ ?(ui ,uj )|uiuj∈ E(G)}. ④ 結(jié)束 . PT圖 河南城建學(xué)院 此例不必重新編號，只要按字母順序即可 . ?(A)=0, ?(B)=?(C)=2, ?(D)=8, ?(E)=max{2+3,8+2}=10, ?(F)=?(G)=?(H)=?(D)+2=10, ?(I)=max{?(G)+8,?(H)+4}=18, ?(J)=?(G)+8=18, ?(K)=max{?(E)+4,?(H)+4}=14, ?(L)=?(J)+3=21, ?(M)=?(K)+8=22, ?(N)=max{?(F)+3,?(I)+2,?(L)+5,?(M)+6}=28. AB22C6 D3E2F2G2H2K4N3I8J8442L3M256最早啟動時間 : PT圖 河南城建學(xué)院 這項工程至少需要 28天才能完成 . 關(guān)鍵路徑 (最長路徑 ): A→B→D→E→K→M→N A→B→D→H→K→M→N 工序 A,B,D,E,H,K,M不能延誤 . 各工序允許延誤時間 t(uj )等于各工序 最晚啟動時間 ?(uj )減去各工序 最早啟動時間 ?(uj ). 即 t(uj )=?(uj )?(uj ). PT圖 河南城建學(xué)院 最晚啟動時間 算法步驟 (已知結(jié)點重新編號 )： ① 賦初值 ?(un )=?(un). ② 更新 ?(uj ),j = n 1, n 2, … , 1 . ?(uj )= min{?(ui ) ?(ui ,uj )|uiuj∈ E(G)}. ③ 結(jié)束 . 根據(jù)工序 uj允許延誤時間 t(uj )是否為 0,可判斷該工序是否在關(guān)鍵路徑上 . PT圖 河南城建學(xué)院 ?(N)=28, ?(M)=286=22, ?(L)=285=23, ?(K)=?(M)8=14, ?(J)=?(L)3=20,?(I)=282=26, ?(H)=min{?(K)4,?(I)4}=10, ?(G)=min{?(J)8,?(I)8}=12, ?(F)=283=25, ?(E)=?(K)4=10, ?(D)=min{?(E)2,?(F)2,?(G)2,?(H)2}=8, ?(C)=?(E)3=7,?(B)=?(D)6=2,?(A)=0. AB22C6 D3E2F2G2H2K4N3I8J8442L3M256最晚啟動時間 : PT圖 河南城建學(xué)院 各工序 允許延誤時間 如下： t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0, t(C)=5,t(F)=15,t(G)=2,t(I)=8,t(J)=2, t(L)=2. PT圖 河南城建學(xué)院 定義：一個工程由若干相互獨立的活動組成，每 個活動稱為 工序 ，相鄰兩個工序在時間上的分界 點稱為 事項 ，它表示緊前工序的結(jié)束和緊后工序 的開始，我們 用頂點表示事項 ，用 有向邊表示工 序 。用 kv?表示在不誤總工期的條件下，以 vk為開工事項 所有工序如期開工，事項 vk的最遲執(zhí)行時間， ? ?表示。表示起點事項，用 nvv 1? ? ? ? ? ? ? ? 總工期則： ???? nn vvvv ???? ,011最長路的權(quán)。這樣得到的賦權(quán)有向圖 G=（ V,E）稱為 PERT圖 。v ) = Cv . 最大流問題 河南城建學(xué)院 例 21：求網(wǎng)絡(luò)的最大流。 當(dāng) f ij＜ C ij時 , 則稱流 f 對邊 是非飽和的 . 把 f ij = 0的邊稱為 零流邊 , f ij ＞ 0的邊稱為 非零流邊 . 若 μ 為網(wǎng)絡(luò)中從 vs到 vt的一條鏈 (有向圖中的路 ), 定義鏈的方向是從 vs到 vt , 邊的方向與鏈的方向相同稱為 前向邊 , 前向邊的全體記為 μ + 。 STEP4：求覆蓋線： 1）封鎖沒有畫框零元的行，封鎖就打 √； 2）在封鎖行中未畫框零元的列也封鎖； 3）在封鎖列中畫框零元的行也封鎖； 4）未封鎖行與封鎖列畫上覆蓋線。 匈亞利算法： 0 4 4 * * 2 3 ⑦ 去掉 x1的標(biāo)記 *, 因為與 x1鄰接的兩個點 y2, y3都有標(biāo)號 4, 所以去掉 x3的標(biāo)記 *. 而與 x3鄰接的兩個點 y2, y3也都有標(biāo)號 4, 此時 X中所有有標(biāo)號的點都已去掉了標(biāo)記 *(如下圖所示 ), 因此 M1是 G的最大匹配 .沒有完美匹配。 河南城建學(xué)院 工作安排問題之一 給 n個工作人員 x1, x2, … , xn安排 n項工作 y1, y2, … , yn. n個工作人員中每個人能勝任一項或幾項工作 , 但并 不是所有工作人員都能從事任何一項工作 . 比如 x1能做 y1, y2工作 , x2能做 y2, y3, y4工作等 . 這樣便提出一個問題 , 對所有的工作人員能不能都分配一件他所能勝任的工作？ 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 我們構(gòu)造一個二部圖 G = ( X, Y, E ), 這里 X = {x1, x2, … , xn},Y = { y1, y2, … , yn}, 并且當(dāng)且僅當(dāng)工作人員 xi勝任工作 yj時 , xi與