運(yùn)籌學(xué)圖與網(wǎng)絡(luò)ppt課件(完整版)
【正文】 去購(gòu)置費(fèi)，但維修費(fèi)用就高了。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。 最短路問(wèn)題的 Dijkstra算法 (雙標(biāo)號(hào)法） 步驟： V1以標(biāo)號(hào) (0,s) I，沒(méi)標(biāo)號(hào)的點(diǎn)的集合 J以及弧的集合 ，則計(jì)算結(jié)束。 網(wǎng)絡(luò)概念 ? 圖只能用來(lái)研究事物之間有沒(méi)有某種關(guān)系 ， 而不能研究這種關(guān)系的強(qiáng)弱程度 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 樹(shù)及最小樹(shù)問(wèn)題 ■ 任何樹(shù)至少有一個(gè)懸掛節(jié)點(diǎn) 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 ■ 如果樹(shù)的節(jié)點(diǎn)個(gè)數(shù)為 m，則邊的個(gè)數(shù)為 m1 ■ 樹(shù)中任意兩個(gè)節(jié)點(diǎn)之間只有唯一的一條鏈 ■ 在樹(shù)的任意兩個(gè)不相鄰的節(jié)點(diǎn)之間增加一條邊，則形成唯一的圈 樹(shù)及最小樹(shù)問(wèn)題 ? 一個(gè)沒(méi)有圈的圖稱為一個(gè) 無(wú)圈圖 或稱為 林 。 ? 若 V1?V2 ， ? E1={ [u,v] | u∈ V1, v∈ V1}，則稱 G1是 G2中 由 V1導(dǎo)出的 導(dǎo)出子圖 。 ? 例如圖中 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 是一個(gè)圈。由定理1有 qddVV2)()(21?? ???? ????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 鏈 ? 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為 鏈 。 ? 無(wú)環(huán)也無(wú)多重邊的圖稱作 簡(jiǎn)單圖 。 ? 邊數(shù) 集合 E中元素的個(gè)數(shù)，記作 q(G)。 ? 若 e=[u,v]∈ E，則稱 u和 v為 e的端點(diǎn) ，而稱 e為 u和 v的 關(guān)聯(lián)邊 ，也稱 u， v與邊 e相 關(guān)聯(lián) 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的次 ? 次 點(diǎn) v作為邊的端點(diǎn)的次數(shù)，記作 d(v)，如圖中，d(v1)=5, d(v4)=6等 ? 端點(diǎn)次為奇數(shù)的點(diǎn)稱作奇點(diǎn) ；次為偶數(shù)的點(diǎn)稱作 偶點(diǎn) 。 ? v0稱為鏈的 起點(diǎn) ， vn稱為鏈的 終點(diǎn) 。 143746211 , ????? eeee連通性 ? 若一個(gè)圖 G的任意兩點(diǎn)之間均至少有一條通路（初等鏈）連接起來(lái)，則稱這個(gè)圖 G是一個(gè) 連通圖 ，否則稱作不連通圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 有向圖 ? 在有些圖中，邊是沒(méi)有方向的，即 [u,v]=[v,u]，這種圖稱為 無(wú)向圖 。 ? 一個(gè)連通的無(wú)圈圖則稱為 樹(shù) ， 一個(gè)林的每個(gè)連通子圖都是一個(gè)樹(shù) 。 ? 網(wǎng)絡(luò) 賦權(quán)的圖 ? 權(quán) 程度的度量 ， 數(shù)量描述 。如果 vt已標(biāo)號(hào)（ lt,kt），則 vs到 vt的距離為 lt，而從 vs到 vt的最短路徑，則可以從 kt反向追蹤到起點(diǎn) vs 而得到。 ? 解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。 vi vj vi vj cij 0 （ a） （ b） cij cij vi vj （ cji） （ c） vi vj cij cji （ d） 求最大流的基本算法 （ 1）找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于零。 一、最小費(fèi)用最大流的數(shù)學(xué)模型 例 7 由于輸油管道的長(zhǎng)短不一，所以在例 6中每段管道（ vi,vj ）除 了有不同的流量限制 cij外，還有不同的單位流量的費(fèi)用 bij ， cij的單位為萬(wàn) 加侖 /小時(shí)， bij的單位為百元 /萬(wàn)加侖。從采地 v1向銷地 v7運(yùn)送石 油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大流 量和最小費(fèi)用。 （ 2）找出這條路上各條弧的最小的順流的容量 pf，通過(guò)這條路增加網(wǎng)絡(luò)的流量 pf。 ? 把所有弧的權(quán)數(shù)計(jì)算如下表： v1 v2 v3 v4 v5 v6 1 2 3 4 5 6 1 16 22 30 41 59 2 16 22 30 41 3 17 23 31 4 17 23 5 18 6 (繼上頁(yè) ) 把權(quán)數(shù)賦到圖中，再用 Dijkstra算法求最短路。也可直接在無(wú)向圖中用 Dijkstra算法來(lái)求解。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。顯然哈密爾頓回路有且只有 n 條邊，若|V|=n ? 連通圖具有哈密爾頓回路的充分必要條件是什么？這個(gè)問(wèn)題是由愛(ài)爾蘭數(shù)學(xué)家哈密爾頓 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1