【正文】 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 圖 2 一條邊的兩個(gè)端點(diǎn)是相同的 ,那么稱為這條邊是環(huán)。 一個(gè)無環(huán)，無多重邊的圖稱為簡單圖，一個(gè)無環(huán)，有多重邊的圖稱為多重圖。 有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡單圖。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。 以點(diǎn) v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn) v 的度（次），記作 。 定理 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 有向圖中 ， 以 vi 為始點(diǎn)的邊數(shù)稱為點(diǎn) vi的出次 ， 用 表示 ；以 vi 為終點(diǎn)的邊數(shù)稱為點(diǎn) vi 的入次 ， 用 表示； vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次 。 v1 v2 v3 v4 v5 v6 v7 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 (a) e5 e7 v1 v2 v5 v6 v7 e1 e6 e8 (b) 子圖 v1 v2 v3 v4 v5 v6 v7 e1 e6 e7 e9 e10 e11 (c) 支撐子圖 在實(shí)際應(yīng)用中，給定一個(gè)圖 G=（ V， E） 或有向圖 D=（ V， A） ， 在 V中指定兩個(gè)點(diǎn)，一個(gè)稱為始點(diǎn)（或發(fā)點(diǎn)），記作 v1 ， 一個(gè)稱為終點(diǎn)（或收點(diǎn)），記作vn ， 其余的點(diǎn)稱為中間點(diǎn)。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。 如 :v0 ， e1， v1， e2， v2， e3 ， v3 ,… ,vn1 , en ， vn， 記作（ v0 ， v1 ， v2， v3 , … , vn1 ， vn ）， e3 v1 v2 v3 v4 v5 v6 e7 e8 e1 e2 e4 e5 e6 e9 e10 1圖中任意兩點(diǎn)之間均至少有一條通路，則稱此圖為連通圖，否則稱為不連通圖。若鏈中所含的邊均不相同，則稱此鏈為簡單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈 , 也稱通路。 ),( ji vvjiw ???????? EvvEvvwajijijiji ),(0),(nnjiaA ?? )(nnjia ?? )( ???????? EvvEvvajijiji ),(0),(1 設(shè)圖 G=（ V， E） 中頂點(diǎn)的個(gè)數(shù)為 n， 構(gòu)造一個(gè) 矩陣 ，其中： 稱矩陣 A為網(wǎng)絡(luò) G的鄰接矩陣。 v1 v2 v3 v4 v5 v6 一個(gè)連通的無圈的無向圖叫做樹。 樹 的性質(zhì)： （ 1） 樹必連通，但無回路（圈）。 （ 3） 樹 中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。 （ 5） 樹 無回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。圖 G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 ),( 1EVK ?用避圈法求出下圖的一個(gè)生成樹。 一般設(shè)已有 {e1，e2， … ， ek}， 找一條與 {e1， e2， … ， ek}中任何一些邊不構(gòu)成圈的邊 ek+1， 重復(fù)這個(gè)過程，直到不能進(jìn)行為止。 如果圖 G的生成樹 T* 的權(quán) S(T*)， 在 G 的所有生成樹 T 中的權(quán)最小 ， 即 那么稱 T*是 G 的最小生成樹 。 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 5 v1 v2 v3 v4 v5 v6 1 2 3 4 4 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 最短路的一般提法為：設(shè) 為連通圖，圖中各邊 有權(quán) （ 表示 之間沒有邊）， 為圖中任意兩點(diǎn)，求一條路 ，使它為從 到 的所有路中總權(quán)最短。 ),( EVG ?jil ???jil ts vv ,? sv ),( jiv jiv ,tv ? ?? ?? ),()(ji vvjilL(一 )、 狄克斯屈拉 (Dijkstra)算法 適用于 wij≥0， 給出了從 vs到任意一個(gè)點(diǎn) vj的最短路 。 vi 為剛得到 P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn) vj， 其中 ，且 vj為 T標(biāo)號(hào)。若全部節(jié)點(diǎn)均為 P標(biāo)號(hào)，則停止，否則用 vk代替 vi， 返回步驟（ 2）。 v1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 解 （ 1） 首先給 v1以 P標(biāo)號(hào) ， 給其余所有點(diǎn) T標(biāo)號(hào) 。 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 求從 V1 到 V8 的最短路線 。 min L(μ)=10 ⑧ P=T=10 由此看到，此方法不僅求出了從 V1 到 V8 的最短路長，同時(shí)也求出了從 V1 到 任意一點(diǎn) 的最短路長。本例中 V1 到 V8 的最短路線是： v1 → v 2 → v 5→ v 6 → v 8 1v 2v3v4v5v 9v8v7v6v6 2 3 1 2 1 6 4 10 3 6 2 3 4 2 10 1v3v2v5v8v（ 二 ） 、 逐次逼近法 算法的基本思路與步驟： 首先設(shè)任一點(diǎn) vi到任一點(diǎn) vj都有一條弧 。 則 v1到 vi的這條路必然也是 v1到 vi的所有路中的最短路 。 從第二步起 ， 使用遞推公式： 求 ， 當(dāng)進(jìn)行到第 t步 ， 若出現(xiàn) 則停止計(jì)算， 即為 v1到各點(diǎn)的最短路長。 解： （ 1） 分析：可行的購置方案 （ 更新計(jì)劃 ） 是很多的 ， 如： 1） 每年購置一臺(tái)新的 ， 則對(duì)應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購置新的 ， 一直用到第五年年底 ， 則總費(fèi)用為： 11+5+6+8+11+18 = 59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。 求解步驟： 1） 畫賦權(quán)有向圖： 設(shè) Vi 表示第 i年初 ， (Vi ,Vj )表示第 i 年初購買新設(shè)備用到第 j年初 （ j1年底 ） ， 而 Wi j 表示相應(yīng)費(fèi)用 ，則 5年的一個(gè)更新計(jì)劃相當(dāng)于從 V1 到 V6的一條路 。所以工廠在每年年初都要決定設(shè)備是否更新。計(jì)劃期（五年）內(nèi)中每年的購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表所示，工廠要制定今后五年設(shè)備更新計(jì)劃，問采用何種方案才能使包括購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。 對(duì)于 D中的每一個(gè)弧 （ vi , vj） ∈ E ,都有一個(gè)非負(fù)數(shù) cij,叫做弧的容量 。 網(wǎng)絡(luò) D上的流，是指定義在弧集合 E上的一個(gè)函數(shù) 其中 f(vi ,vj) =fij 叫做弧 (vi， vj)上的流量。 （ 2） 平衡條件： 對(duì)于發(fā)點(diǎn) vs， 有 對(duì)于收點(diǎn) vt ， 有 對(duì)于中間點(diǎn)，有 ? ?? ???Evv Evvsjjsjs sjWff),( ),( ?? ? ???Evv Evv tjjtjt tj Wff),( ),(? ?? ? ??Evv Evv ijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 2v1v 3v 4v 5v6v 7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 圖中 為零流弧，其余為非飽和弧。 f 是一個(gè)可行流 ， 如果滿足： 則稱 為從 vs到 vt 的關(guān)于 f 的一條增廣鏈。 即 中的每一條弧都是非飽和弧 ??即 中的每一條弧都是非零流弧 ?2v1v 3v 4v 5v6v 7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) ? ?7766633232211 ),(,),(,),(,),(, vvvvvvvvvvvvv?? ? ?),(),(),( 766321 vvvvvv??? ? ?),( 23 vv????是一個(gè)增廣鏈 顯然圖中增廣鏈不止一條 容量網(wǎng)絡(luò) G =（ V， E， C） ， vs為始點(diǎn) ，vt為終點(diǎn) 。