【正文】 表示 。 ? ? }{),( jiji fvvff ??稱滿足下列條件的流為可行流： （ 1）容量條件：對于每一個?。?vi ,vj） ∈ E 有 0 ? fij ? cij 。 年份 1 2 3 4 5 購置費 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費 5 7 12 18 25 年份 1 2 3 4 5 購置費 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費 5 7 12 18 25 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 30 四、 最大流問題 （ 一 ） 、 基本概念 設(shè)一個賦權(quán)有向圖 D=（ V, E） ,在 V中指定一個發(fā)點vs和一個收點 vt ,其它的點叫做中間點 。 2）求解 （標號法） W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6++8+11+18=59 W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18 W34 =12+5=17 W35 =12+5+6=23 W36 =12+5+6+8=31 例四、 某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時間的推移逐漸損壞。 }{min 11 jiiij lPP ?? ),2,1(1)1(1 njlP jj ??? ）（ nklPjikiikj ,3,2][min )1(1)(1 ???? ?)(1kjP ）（ njPP tjtj ,2,1)1(1)(1 ??? ? ）（ njP tj ,2,1)(1 ??例二、 － 1 8 v1 v2 v3 v4 v5 － 2 6 － 3 － 5 － 1 － 3 － 5 2 1 － 1 2 1 1 v6 v7 v8 3 7 v1 v2 v3 v4 v5 v6 v7 v8 P(1) P(2) P(3) P(4) v1 0 1 2 3 0 0 0 0 v2 6 0 2 1 5 5 5 v3 3 0 5 1 2 2 2 2 v4 8 0 2 3 7 7 7 v5 1 0 1 3 3 v6 1 0 1 7 1 1 1 v7 1 0 5 5 5 v8 3 5 0 6 6 求圖中 v1到 各點的最短路 － 1 8 v1 v2 v3 v4 v5 － 2 6 － 3 － 5 － 1 － 3 － 5 2 1 － 1 2 1 1 v6 v7 v8 3 7 （ 0， 0） （ v3 ， 5） （ v1 ， 2） （ v3 ， 7） （ v2 ， 3） （ v4 ， 5） （ v3 ， 1） （ v6 ， 6） 例三、求： 5年內(nèi)，哪些年初購置新設(shè)備，使 5年內(nèi)的總費用最小。 顯然 ， 從 v1到 vj的最短路是從 v1出發(fā) ， 沿著這條路到某個點 vi再沿弧 (vi,vj)到 vj。 3 V 1 V 2 V V 4 V 5 V V 6 7 V 8 3 7 2 1 2 3 3 4 1 2 2 6 V1 V2 V3 V4 V5 V6 V7 V8 ① P=0 T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ ② P=T=3 T=+∞ T=7 T=+∞ T=+∞ T=+∞ T=+∞ ③ T=6 T=7 P=T=5 T=+∞ T=+∞ T=+∞ ④ P=T=6 T=6 T=8 T=+∞ T=+∞ ⑤ P=T=6 T=8 T=9 T=12 ⑥ P=T=8 T=10 T=10 ⑦ P=T=9 T=11 再無其它 T 標號 ， 所以 T(V8)=P(V8)=10。 0)( ?svP ),3,2()( nivP i ?????Evv ji ?),( ])(,)(min [)( jiijj lvPvTv ?? )](min[)(ik vTvP ?例一、 用 Dijkstra算法求下圖從 v1到 v6的最短路。 三 、最短路問題 算法步驟： vs以 P標號 ，這表示從 vs到 vs的最短距離為 0，其余節(jié)點均給 T標號， 。 ),( 1EVT ? )(min)( * TSTS T? 某六個城市之間的道路網(wǎng)如圖 所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使電話線的總長度最短。 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 v1 v2 v3 v4 v5 e2 e4 e6 e8 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 （一） 破圈法 （二） 避圈法 在圖中任取一條邊 e1， 找一條與 e1不構(gòu)成圈的邊 e2，再找一條與 {e1， e2}不構(gòu)成圈的邊 e3。 v1 v2 v3 v4 v5 v6 設(shè)圖 是圖 G=(V , E )的一支撐子圖， 如果圖 是一個樹 ,那么稱 K 是 G 的一個生成樹（支撐樹），或簡稱為圖 G 的樹。 （ 2） n 個頂點的樹必有 n1 條邊 。 654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB?????????????????????例 權(quán)矩陣為： 鄰接矩陣為： v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 654321654321 030303302023020576305020007204346040vvvvvvvvvvvvA?????????????????????問題 ? 圖（頂點、邊）、有限圖、無限圖 ? 無向圖、有向圖、環(huán)、多重邊 ? 多重圖、簡單圖、完全圖、有向完全圖、二部圖 ? 頂點的次、出次、入次、懸掛點、孤立點、奇點、偶點 ? 子圖、生成子圖（支撐圖）、網(wǎng)絡(luò)（賦權(quán)圖） ? 鏈、初等鏈、圈、初等圈、回路、連通圖 ? 圖的矩陣表示、鄰接矩陣 ? 歐拉道路、歐拉回路、中國郵路問題 樹的概念 ? 樹、樹葉、分枝點 ? 數(shù)的性質(zhì) ? 生成子圖、生成樹、樹枝、弦 ? 最小生成樹 ? 避圈法、破圈法 ? 有向樹、根樹、葉、分枝點、叉樹 二 、 樹及最小樹問題 已知有六個城市 ， 它們之間 要架設(shè)電話線 ， 要求任意兩個城市均可以互相通話 ， 并且電話線的總長度最短 。 其鏈長為 n ， 其中 v0 ， vn 分別稱為鏈的起點和終點 。對每一條弧 ，對應(yīng)一個數(shù) ，稱為弧上的 “ 權(quán) ” 。 所有頂點的入次之和等于所有頂點的出次之和。度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。 每一對頂點間都有邊相連的無向簡單圖稱為完全圖。一條方向從 vi指向 vj 的弧，記作 (vi , vj)。圖與網(wǎng)絡(luò)分析在物流系統(tǒng)中的應(yīng)用 (Graph Theory and Network Analysis) 圖與網(wǎng)絡(luò)的基本知識 最短路問題 樹及最小樹問題 B D A C A B C