【正文】 21 , vvvvvvV ?},{ 10987654321 eeeeeeeeeeE ，?},{ 211 vve ? },{ 212 vve ?},{ 323 vve ? },{ 434 vve ?},{ 315 vve ? },{ 536 vve ?},{ 537 vve ? },{ 658 vve ?},{ 669 vve ? },{ 6110 vve ?圖 1 如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的 ， 則稱其為無(wú)向圖 ， 記作G = (V， E)， 連接點(diǎn)的邊記作 [vi , vj]， 或者 [vj , vi]。 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 得出第二次就座方案是（ 1， 3， 5， 7，2， 4， 6， 1），那么第三次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊。圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis) 圖與網(wǎng)絡(luò)的基本知識(shí) 最短路問(wèn)題 樹及最小樹問(wèn)題 最大流問(wèn)題 最小費(fèi)用最大流問(wèn)題 哥尼斯堡七橋問(wèn)題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ） 是歐洲一個(gè)城市 ， Pregei河把該城分成兩部分 ， 河中有兩個(gè)小島 ， 十八世紀(jì)時(shí) ， 河兩邊及小島之間共有七座橋 ，當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒(méi)有辦法從某處（ 如 A） 出發(fā) ， 經(jīng)過(guò)各橋一次且僅一次最后回到原地呢 ？ B D A C A B C D 哥尼斯堡七空橋 一筆畫問(wèn)題 哈密爾頓 （ Hamilton） 回路是十九世紀(jì)英國(guó)數(shù)學(xué)家哈密頓提出 ， 給出一個(gè)正 12面體圖形 ， 共有 20個(gè)頂點(diǎn)表示 20個(gè)城市 ，要求從某個(gè)城市出發(fā)沿著棱線尋找一條經(jīng)過(guò)每個(gè)城市一次而且僅一次 ， 最后回到原處的周游世界線路 （ 并不要求經(jīng)過(guò)每條邊 ） 。 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 得到第三次就座方案是 （ 1， 4， 7， 3，6， 2， 5， 1） ， 那么第四次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 ， 只留下 7點(diǎn)孤立點(diǎn) ， 所以該問(wèn)題只有三個(gè)就座方案 。 如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作 D=(V, A)， 其中 V 表示有向圖 D 的點(diǎn)集合， A 表示有向圖 D 的弧集合。 一個(gè)無(wú)環(huán)，無(wú)多重邊的圖稱為簡(jiǎn)單圖，一個(gè)無(wú)環(huán)，有多重邊的圖稱為多重圖。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。 定理 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 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)。 如 :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)之間均至少有一條通路，則稱此圖為連通圖，否則稱為不連通圖。 ),( ji vvjiw???????? EvvEvvwajijijiji ),(0),(nnjiaA ?? )(nnjiaA ?? )(???????? EvvEvvajijiji ),(0),(1 設(shè)圖 G=（ V， E） 中頂點(diǎn)的個(gè)數(shù)為 n， 構(gòu)造一個(gè) 矩陣 ，其中： 稱矩陣 A為網(wǎng)絡(luò) G的鄰接矩陣。 樹的性質(zhì)： （ 1） 樹必連通，但無(wú)回路（圈）。 （ 5） 樹 無(wú)回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。 ),( 1EVK ?),( 1EVK ?（一） 破圈法：在圖中任選一個(gè)圈，從這個(gè)圈中去掉一條邊。 v1 v2 v3 v4 v5 v6 v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 根據(jù)破圈法和避圈法兩種方式得到了圖的兩個(gè)不同的生成樹，由此可以看到連通圖的生成樹不是唯一的。 破圈法 ：在原圖中 ， 任選一個(gè)圈 ， 從圈中去掉權(quán)最大 的一條邊 。 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 最短路的一般提法為：設(shè) 為連通圖，圖中各邊 有權(quán) （ 表示 之間沒(méi)有邊）， 為圖中任意兩點(diǎn)，求一條路 ，使它為從 到 的所有路中總權(quán)最短。 vi 為剛得到 P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn) vj， 其中 ，且 vj為 T標(biāo)號(hào)。 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) 。 min L(μ)=10 ⑧ P=T=10 由此看到，此方法不僅求出了從 V1 到 V8 的最短路長(zhǎng)，同時(shí)也求出了從 V1 到 任意一點(diǎn) 的最短路長(zhǎng)。 則 v1到 vi的這條路必然也是 v1到 vi的所有路中的最短路。 解： （ 1） 分析：可行的購(gòu)置方案 （ 更新計(jì)劃 ） 是很多的 ， 如： 1） 每年購(gòu)置一臺(tái)新的 ， 則對(duì)應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購(gòu)置新的 ， 一直用到第五年年底 ， 則總費(fèi)用為： 11+5+6+8+11+18 = 59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。所以工廠在每年年初都要決定設(shè)備是否更新。 對(duì)于 D中的每一個(gè)弧 （ vi , vj） ∈ E ,都有一個(gè)非負(fù)數(shù) cij,叫做弧的容量 。 （ 2） 平衡條件： 對(duì)于發(fā)點(diǎn) vs， 有 對(duì)于收點(diǎn) vt ， 有 對(duì)于中間點(diǎn)，有 ? ?? ???Evv Evvsjjsjs sjWff),( ),(? ?? ????Evv Evvtjjtjt tjWff),( ),(? ?? ???Evv Evvijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 f 是一個(gè)可行流 ， 如果滿足： 則稱 為從 vs到 vt 的關(guān)于 f 的一條增廣鏈。 截集 中所有弧的容量之和 ，稱為這個(gè)截集的容量 ， 記為 。 Evv ij ?),( 0?ijf),( jiv ?? ),m i n ( iijj f ?? ?Evv ji ?),( ijij cf ?),( jiv ?? ),m i n ( ijijij fc ?? ??調(diào)整過(guò)程 設(shè) 1． 令 2． 去掉所有標(biāo)號(hào) ， 回到第一步 ， 對(duì)可行流重新標(biāo)號(hào) 。當(dāng) f * 是最大流時(shí)，就是最小費(fèi)用最大流。 （ 3） 在 L( f (k1) )中 ， 尋求從 vs到 vt的最短路 。 例 求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)是（ bij , cij） (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 3 vs v2 v1 vt v3 1 6 4 1 2 2 (1) L(f (0)) (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 0 vs v2 v1 vt v3 3 0 0 3 3 3 (2) f ( 1) ?1=3 W