【正文】 v4 v5 e2 e4 e6 e8 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 （二） 避圈法：開始選一條邊，以后每一步中，總從未被選取的邊中選出一條與已選邊不構成圈的邊，重復這個過程，直到不能進行為止。 （ 4）樹 連通，但去掉任一條邊， 必變?yōu)椴贿B通。 （ 二 ） 、 圖的矩陣表示 對于網(wǎng)絡 （ 賦權圖 ） G=（ V， E） ， 其中邊 有權 ， 構造矩陣 ， 其中： 稱矩陣 A為網(wǎng)絡 G的權矩陣 。 )(ivd ?)( ivd? 設 G1=（ V1 , E1 ）， G2 =（ V2 ,E2 ） 如果 V2 ?V1 , E2 ?E1 稱 G2 是 G1 的子圖；如果 V2 = V1 , E2 ?E1 稱 G2 是 G1 的部分圖或支撐子圖。 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 度為零的點稱為弧立點，度為 1的點稱為懸掛點。 ? ?jvV ?}{ keE ?jvkeVv1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 例 ? ?654321 , 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 = (V， E)， 連接點的邊記作 [vi , vj]， 或者 [vj , vi]。圖與網(wǎng)絡分析 (Graph Theory and Network Analysis) 圖與網(wǎng)絡的基本知識 最短路問題 樹及最小樹問題 最大流問題 最小費用最大流問題 哥尼斯堡七橋問題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ） 是歐洲一個城市 ， Pregei河把該城分成兩部分 ， 河中有兩個小島 ， 十八世紀時 ， 河兩邊及小島之間共有七座橋 ，當時人們提出這樣的問題：有沒有辦法從某處（ 如 A） 出發(fā) ， 經(jīng)過各橋一次且僅一次最后回到原地呢 ？ B D A C A B C D 哥尼斯堡七空橋 一筆畫問題 哈密爾頓 （ Hamilton） 回路是十九世紀英國數(shù)學家哈密頓提出 ， 給出一個正 12面體圖形 ， 共有 20個頂點表示 20個城市 ，要求從某個城市出發(fā)沿著棱線尋找一條經(jīng)過每個城市一次而且僅一次 ， 最后回到原處的周游世界線路 （ 并不要求經(jīng)過每條邊 ） 。 如果一個圖是由點和弧所構成的，那么稱它為有向圖，記作 D=(V, A)， 其中 V 表示有向圖 D 的點集合， A 表示有向圖 D 的弧集合。懸掛點的關聯(liá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) 支撐子圖 在實際應用中，給定一個圖 G=（ V， E） 或有向圖 D=（ V， A） ， 在 V中指定兩個點，一個稱為始點（或發(fā)點），記作 v1 ， 一個稱為終點（或收點），記作vn ， 其余的點稱為中間點。 ),( ji vvjiw???????? EvvEvvwajijijiji ),(0),(nnjiaA ?? )(nnjiaA ?? )(???????? EvvEvvajijiji ),(0),(1 設圖 G=（ V， E） 中頂點的個數(shù)為 n， 構造一個 矩陣 ，其中： 稱矩陣 A為網(wǎng)絡 G的鄰接矩陣。 （ 5） 樹 無回路（圈），但不相鄰的兩個點之間加一條邊，恰得到一個回路（圈）。 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ù)破圈法和避圈法兩種方式得到了圖的兩個不同的生成樹，由此可以看到連通圖的生成樹不是唯一的。 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 最短路的一般提法為：設 為連通圖，圖中各邊 有權 （ 表示 之間沒有邊）， 為圖中任意兩點，求一條路 ，使它為從 到 的所有路中總權最短。 v1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 解 （ 1） 首先給 v1以 P標號 ， 給其余所有點 T標號 。 則 v1到 vi的這條路必然也是 v1到 vi的所有路中的最短路。所以工廠在每年年初都要決定設備是否更新。 （ 2） 平衡條件： 對于發(fā)點 vs， 有 對于收點 vt ， 有 對于中間點，有 ? ?? ???Evv Evvsjjsjs sjWff),( ),(? ?? ????Evv Evvtjjtjt tjWff),( ),(? ?? ???Evv Evvijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 截集 中所有弧的容量之和 ，稱為這個截集的容量 ， 記為 。當 f * 是最大流時，就是最小費用最大流。 例 求網(wǎng)絡的最小費用最大流，弧旁權是（ 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(f(1))=3 － 1 (3) L(f (1)) － 2 3 vs v2 v1 vt v3 1 6 4 1 2 － 1 － 2 1 vs v2 v1 vt v3 4 0 0 3 4 3 (4 ) f ( 2) ?2=1 W(f(2))=4 (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) (5) L(f (2)) － 3 vs v2 v1 vt v3 － 1 4 1 2 － 2 － 2 3 － 1 6 6 1 vs v2 v1 vt v3 4 0 1 4 5 3 (6 ) f ( 3) ?3=1 W(f(3))=5 (7) L(f (3)) vs v2 v1 vt v3 － 3 － 1 4 1 2 － 2 3 － 1 6 1 vs v2 v1 vt v3 4 3 4 4 5 0 (8 ) f ( 4) ?4=3 W(f(4))=8 0 vs v2 v1 vt v3 4 4 5 5 5 0 ?5=1 W(f(5))=9 (10 )f ( 5) － 1 2 3 － 1 vs v2 v1 vt v3 － 3 4 1 2 6 (9) L( f ( 4)) 4 6 3 － 1 2 － 1 4 (11) L( f ( 5)) 1 2 6 － 4 vs v2 v1 vt v3 － 6 第六節(jié) 中國郵遞員問題 一 、 歐拉回路與道路 定義 連通圖 G中 ， 若存在一條道路 ， 經(jīng)過每邊一次且僅一次 ， 則