運籌學圖與網絡ppt課件(完整版)

　　

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