【正文】 圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis) 圖與網(wǎng)絡(luò)的基本知識 最短路問題 樹及最小樹問題 最大流問題 最小費用最大流問題 哥尼斯堡七橋問題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ） 是歐洲一個城市 ， Pregei河把該城分成兩部分 ， 河中有兩個小島 ， 十八世紀(jì)時 ， 河兩邊及小島之間共有七座橋 ，當(dāng)時人們提出這樣的問題：有沒有辦法從某處（ 如 A） 出發(fā) ， 經(jīng)過各橋一次且僅一次最后回到原地呢 ？ B D A C A B C D 哥尼斯堡七空橋 一筆畫問題 哈密爾頓 （ Hamilton） 回路是十九世紀(jì)英國數(shù)學(xué)家哈密頓提出 ， 給出一個正 12面體圖形 ， 共有 20個頂點表示 20個城市 ，要求從某個城市出發(fā)沿著棱線尋找一條經(jīng)過每個城市一次而且僅一次 ， 最后回到原處的周游世界線路 （ 并不要求經(jīng)過每條邊 ） 。 有 7個人圍桌而坐 ， 如果要求每次相鄰的人都與以前完全不同 ， 試問不同的就座方案共有多少種 ？ 用頂點表示人 ， 用邊表示兩者相鄰 ， 因為最初任何兩個人都允許相鄰 ， 所以任何兩點都可以有邊相連 。 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， 2， 3， 4，5， 6， 7， 1），繼續(xù)尋求第二次就座方案時就不允許這些頂點之間繼續(xù)相鄰，因此需要從圖中刪去這些邊。 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），那么第三次就座方案就不允許這些頂點之間繼續(xù)相鄰，只能從圖中刪去這些邊。 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） ， 那么第四次就座方案就不允許這些頂點之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 ， 只留下 7點孤立點 ， 所以該問題只有三個就座方案 。 1 2 3 7 6 4 5 引論 圖的用處 某公司的 組織機構(gòu)設(shè)置圖 總公司 分公司 工廠或辦事處 一、 圖與網(wǎng)絡(luò)的基本知識 （一）、 圖與網(wǎng)絡(luò)的基本概念 E A D C B 一個圖是由點和連線組成。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊） 一個圖是由點集 和 中元素的無序?qū)Φ囊粋€集合 構(gòu)成的二元組 ， 記為 G =(V， E)， 其中 V 中的元素 叫做頂點 ， V 表示圖 G 的點集合； E 中的元素 叫做邊 ， E 表示圖 G 的邊集合 。 ? ?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òu)成的 ， 則稱其為無向圖 ， 記作G = (V， E)， 連接點的邊記作 [vi , vj]， 或者 [vj , vi]。 如果一個圖是由點和弧所構(gòu)成的，那么稱它為有向圖，記作 D=(V, A)， 其中 V 表示有向圖 D 的點集合， A 表示有向圖 D 的弧集合。一條方向從 vi指向 vj 的弧，記作 (vi , vj)。 v4 v6 v1 v2 v3 v5 V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 圖 2 一條邊的兩個端點是相同的 ,那么稱為這條邊是環(huán)。 如果兩個端點之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀? 一個無環(huán)，無多重邊的圖稱為簡單圖，一個無環(huán)，有多重邊的圖稱為多重圖。 每一對頂點間都有邊相連的無向簡單圖稱為完全圖。 有向完全圖則是指任意兩個頂點之間有且僅有一條有向邊的簡單圖。 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 度為零的點稱為弧立點，度為 1的點稱為懸掛點。懸掛點的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。 以點 v為端點的邊的個數(shù)稱為點 v 的度（次），記作 。 )(vd 圖中 d(v1)= 4， d(v6)= 4（ 環(huán)計兩度 ） 定理 1 所有頂點度數(shù)之和等于所有邊數(shù)的 2倍。 定理 2 在任一圖中，奇點的個數(shù)必為偶數(shù)。 所有頂點的入次之和等于所有頂點的出次之和。 有向圖中 ， 以 vi 為始點的邊數(shù)稱為點 vi的出次 ， 用 表示 ；以 vi 為終點的邊數(shù)稱為點 vi 的入次 ， 用 表示； vi 點的出次和入次之和就是該點的次 。 )(ivd ?)( ivd? 設(shè) G1=（ V1 , E1 ）， G2 =（ V2 ,E2 ） 如果 V2 ?V1 , E2 ?E1 稱 G2 是 G1 的子圖；如果 V2 = V1 , E2 ?E1 稱 G2 是 G1 的部分圖或支撐子圖。 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) 支撐子圖 在實際應(yīng)用中，給定一個圖 G=（ V， E） 或有向圖 D=（ V， A） ， 在 V中指定兩個點，一個稱為始點（或發(fā)點），記作 v1 ， 一個稱為終點（或收點），記作vn ， 其余的點稱為中間點。對每一條弧 ，對應(yīng)一個數(shù) ，稱為弧上的 “ 權(quán) ” 。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。 Avv ji ?),(jiw 由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列稱為鏈。 如 :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圖中任意兩點之間均至少有一條通路，則稱此圖為連通圖，否則稱為不連通圖。 其鏈長為 n ， 其中 v0 ， vn 分別稱為鏈的起點和終點 。若鏈中所含的邊均不相同，則稱此鏈為簡單鏈；所含的點均不相同的鏈稱為初等鏈 , 也稱通路。 （ 二 ） 、 圖的矩陣表示 對于網(wǎng)絡(luò) （ 賦權(quán)圖 ） G=（ V， E） ， 其中邊 有權(quán) ， 構(gòu)造矩陣 ， 其中： 稱矩陣 A為網(wǎng)絡(luò) G的權(quán)矩陣 。 ),( ji vvjiw???????? EvvEvvwajijijiji ),(0),(nnjiaA ?? )(nnjiaA ?? )(???????? EvvEvvajijiji ),(0),(1 設(shè)圖 G=（ V， E） 中頂點的個數(shù)為 n， 構(gòu)造一個 矩陣 ，其中： 稱矩陣