【正文】 最小生成樹問題v1 3317285410 34v7v6 v5v4v2 v3(a)v1 3317285434v7v6 v5v4v2 v3(b)v1 33 725434v7v6 v5v4v2 v31(c)v1 33 72434v7v6 v5v4v2 v31(d)v4v1 33 7234v7v6 v5v2 v31(e)v1 33 723v7v6 v5v4v2 v31(f)例 7. 某大學準備對其所屬的 7個學院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡的可能聯(lián)通的途徑如下圖，圖中 v1,…,v 7 表示 7個學院辦公室，請設計一個網(wǎng)絡能聯(lián)通 7個學院辦公室，并使總的線路長度為最短 ()。性質(zhì) 4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。v1 v2 v3 v4 v5 v6 最短路問題最短路問題Page 38把所有弧的權數(shù)計算如下表，把權數(shù)賦到圖中，再用Dijkstra算法求最短路。權數(shù)表示兩地間公路的長度（單位：公里）。 最短路問題Dijkstra 雙標號法 的步驟：例 1. 求下圖中 v1到 v6的最短路 最短路問題Dijkstra 雙標號法 ：v235 2753 1512v1v6v5v3v4v235 2753 1512v1v6v5v3v4（ 0， s）0+30+20+5（ 2， 1）2+1（ 3， 1）(3,3)3+73+5(8,4) v1到 v6的最短距離為 8；最短路為：v1 → v 3 → v4 → v6Page 26最短路問題最短路問題求網(wǎng)絡圖的最短路，設圖的起點是 vs,終點是 vt ,以 vi為起點 vj為終點的弧記為 (i, j) 距離為 dijP標號標號 (點標號點標號 )： b(j) — 起點 vs到點 vj的最短路長；T標號標號 (邊標號邊標號 )： k(i,j)=b(i)+dij，步驟： 1. 令起點的標號； b(s)＝ 0。假定 v1→v 2 →v 3 →v 4是 v1 →v 4的最短路，則 v1 →v 2 →v 3一定是 v1 →v 3的最短路， v2 →v 3 →v 4也一定是 v2 →v 4的最短路。ABCDEF在圖中找到一個點序列，使得依次排列的兩點不相鄰，即能滿足要求。 圖與網(wǎng)絡的基本概念有向圖的定義：圖 D被定義為 “ 點 ” 和 “ 弧 ” 的集合，記作：其中 : V—— 點集； A—— 弧集a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳Page 12無向圖 G＝ (V, E)，對 G的每一條 邊 (vi , vj) 相應賦予數(shù)量指標 wij，稱 wij為邊 (vi , vj)上的 權 ，稱圖 G為 賦權圖賦權的有向圖 D = (V, A)，指定一點為 發(fā)點 （ vs），指定另一點為 收點 （ vt），稱其它點為 中間點 ，并把 D 中每一條弧的 賦權數(shù) cij 稱為弧 (vi,vj)的 容量 ，這樣的賦權有向圖 D就稱為 網(wǎng)絡①②③④ ⑤⑥91020157 1419256l 賦權圖，網(wǎng)絡 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念權可以代表距離、費用、通過能力 (容量 ) 等等Page 13圖的基本概念與模型圖的基本概念與模型 出次與入次 有向圖中，以 vi為始點的邊數(shù)稱為點 vi的 出次 ，用 d+(vi)表示；以 vi為終點的邊數(shù)稱為點 vi 的 入次 ，用表示 d(vi) ； vi 點的出次和入次之和就是該點的次。 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念Page 7如果 邊 e 的兩個端點相重，稱該邊為 環(huán)如右圖中邊 e1為環(huán)如果兩個點之間多于一條邊，稱為多重邊 ，如右圖中的 e4和 e5對無環(huán)、無多重邊的圖稱作 簡單圖v3e7e4e8e5e6e1e2 e3v1v2v4 v5l 環(huán)，多重邊，簡單圖 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念Page 8與某一個 點 vi 相關聯(lián)的 邊的數(shù)目 稱為 點 vi的 次 （也叫做度），記作 d(vi)右圖中 d(v1)＝ 4， d(v3)=5， d(v5)=1次為奇數(shù)的點稱作 奇點 ，次為偶數(shù)的點稱作 偶點 ，次為 1的點稱為 懸掛點 ，次為 0的點稱作 孤立點 。一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關系并不是重要的。nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這里只關心圖中有多少個點、以及哪些點之間有連線。 e2=[v1,v2]。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a) (b) (c)(a)明顯為二部圖， (b)也是二部圖，但不明顯，改畫為 (c)時可以清楚看出。A B C D E F甲 √ √乙 √ √ √丙 √ √丁 √ √戊 √ √ √己 √ √ √Page 15圖的基本概念與模型圖的基本概念與模型解：用圖來建模。最短路問題對一個賦權的圖（ G或 D）中的指定的兩個點 Vs 和 Vt 找到一條從 Vs 到 Vt 的路，使得這條路上所有 弧（邊）的權數(shù)的總和最小，這條路被稱之為從 Vs到 Vt的最短路。4. 對 B中的每一條弧，計算 Sij = Li + Cij 。 最短路問題最短路問題Page 29例 3. 求下圖 v1到各點的最短距離及最短路線。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就高了。廠長人事科 財務科 總工程師 生產(chǎn)副 廠長 經(jīng)營副 廠長開發(fā)科 技術科 生產(chǎn)科 設備科 供應科 銷售科 檢驗科動力科 最小生成樹問題最小生成樹問題Page 42性質(zhì) 1：任何樹中必存在次為 1的點。求解最小生成樹的破圈算法Page 55v1v2 v4v5v64352 158 78破圈法 ：任取一圈，去掉圈中最長邊，直到無圈。容量網(wǎng)絡中通常規(guī)定一個 發(fā)點發(fā)點 (也稱源點，記為 s)和一個 收點收點 (也稱匯點，記為 t)，網(wǎng)絡中其他點稱為 中間點中間點 。（零流即是可行流）網(wǎng)絡最大流問題：指滿足容量限制條件和中間點平衡的條件下，使 v(f)值達到最大。 最大流問題一、最大流的數(shù)學模型二、最大流問題的網(wǎng)絡圖論解法 對網(wǎng)絡上弧的容量的表示作改進。 最大流問題二、最大流問題的網(wǎng)絡圖論解法基本算法步驟：① 第一次迭代：選擇路為 v1 → v4 → v7 。(6,6)(3,4) (5,7)(2,5)(2,4)（ 2,3） (4,4)(1,3)(2,8)（ 3,2）v1v2v5v7v4v3v6(6,3)22v1v2 v5v7v4v3v6123522 355 最小費用最大流問題 例 8最大流問題可能有多種解法，如：12v1v2v5v7v4v3v6123632 345解 1解 2一、最小費用最大流的數(shù)學模型 例 9. 由于輸油管道的長短不一，所以在例 6中每段管道（ vi,vj ）除了有不同的流量限制 cij外，還有不同的單位流量的費用 bij ， cij的單位為萬加侖 /小時， bij的單位為百元 /萬加侖。v5(6,6)(3,4) (5,7)(2,5) (0,4)（ 2,3） (3,4)(0,3)(2,8)（ 3,2）v1v2v7v4v3v6(5,3)(1,3)(0,8)(1,3)（ 0,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(1,4)（ 0,3）圖 112911第一次迭代后的總流量 最小費用最大流問題二、最小費用最大流問題的網(wǎng)絡圖論解法 ② 第二次迭代：找到最短路 v1 → v4 → v7。(3,6)(0,4) (1,7)(2,5) (1,4)（ 0,3） (1,4)(0,3)(0,8)（ 0,2）v1v2v5v7v4v3v6(0,3)(6,3)(2,8)(1,3)（ 3,2）(3,6)(3,4)(0,5)（ 1,4） (4,7)(3,4)（ 2,