【正文】 3 4 10 2 3 1 2 6 2 4 10 1 (5,2) (10,5) (6,2) (9,5) (12,5) (0,0) (3,1) (1,1) v1 v4 v2 v8 v7 v6 v5 v9 6 3 6 2 3 4 10 2 3 1 2 6 2 4 10 1 (5,2) (10,5) (6,2) (9,5) (12,5) 從 v1 到 v8 的最短路的長(zhǎng)度為： 12 從 v1 到 v8 的最短路線為： v8 v5 v2 v1 步驟： 給起點(diǎn)一個(gè)永久標(biāo)號(hào) （ 0， 0） 。從 v4出發(fā)沿 （ v4 ,v6）到達(dá) v6，經(jīng)過(guò)的路程是 d（ v1,v4） + w46=1 +10=11單位。由于所有的權(quán) wij ≥0， 因此，不論他如何再?gòu)?v2 或者 v3 到達(dá) v4 ， 所經(jīng)過(guò)的總路程都不會(huì)比 1少，于是就有 d（ v1 ,v4） =1。 如果從 v1出發(fā) ，沿 （ v1 ,v3） 到達(dá) v3 ， 則是 d（ v1 ,v1） +w13=3單位 。 因?yàn)?Wij ≥0， d（ v1 ,v1） =0。算法的每一步是去修改T標(biāo)號(hào)，把某一個(gè)具有 T 標(biāo)號(hào)的點(diǎn)改變?yōu)榫哂?P 標(biāo)號(hào)的點(diǎn)，使圖 D中具有 P 標(biāo)號(hào)的頂點(diǎn)多一個(gè)。 并且 ， 這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn) vs到任意一個(gè)點(diǎn) vj的最短路 。 P0的權(quán) S(P0) 叫做從 vs到 vt 的距離，記作 d（ vs， vt）。設(shè)一個(gè)賦權(quán)有向圖 D=（ V， A）， 對(duì)于每一個(gè)弧 a =（ vi ,vj） ，相應(yīng)地有一個(gè)權(quán) wij。比如從 v1出發(fā)，經(jīng)過(guò) v2 , v5到達(dá) v8 或者從 v1出發(fā)，經(jīng)過(guò)v4 ， v6 ， v7 到達(dá) v8 等等。 167。 從網(wǎng)絡(luò)圖中任意節(jié)點(diǎn)開始尋找與該節(jié)點(diǎn)關(guān)聯(lián)的權(quán)數(shù)最小的邊，得到另一節(jié)點(diǎn)后，再?gòu)倪@個(gè)新節(jié)點(diǎn)開始尋找與該節(jié)點(diǎn)關(guān)聯(lián)的權(quán)數(shù)最小的另一邊 …… 。這時(shí)得到一個(gè) 不含圈的圖，如圖 所示，即是最小支撐樹。再取一個(gè)圈（ v3 , v5 , v2 ,v3），去掉邊 [v2 , v5]。 例 某六個(gè)城市之間的道路網(wǎng)如圖 所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使得電話線的總長(zhǎng)度最短。 再如，城市間交通線的建造等，都可以歸結(jié)為這一類問(wèn)題。 設(shè) G=（ V， E） 是一個(gè)連通圖， G的每一條 [vi ,vj]對(duì)應(yīng)一個(gè)非負(fù)的權(quán) Wij。這里所指的權(quán)，是具有廣義的數(shù)量值。在剩下的圖中，再取一個(gè)圈（ v1,v2,v4,v3,v1），去掉邊 e4 。就是從圖中任取一個(gè)圈，去掉一條邊。 若 G1不含圈，則 G1是 G的一個(gè)支撐樹。 例如 ,圖 是圖 的一個(gè)支撐樹 圖 v6 v5 v2 v3 v4 v1 a v6 v5 v2 v3 v4 v1 b 顯然 ,如果圖 K=(V,EI)是圖 G=(V,E)的一個(gè)支撐樹 ,那么 K 的邊數(shù)是 p(G)1， G中不屬于支撐樹 K 的邊數(shù)是 q(G)p(G)+1。 定理 圖 G是一個(gè)樹的充分必要條件是任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈 。 圖 v6 v3 v4 v2 v5 v1 定義 一個(gè)無(wú)圈的連通圖叫做 樹 。 表示任意兩個(gè)城市之間均可以通話 ， 這個(gè)圖必須是連通圖 。 樹和最小支撐樹 一 、 樹及其性質(zhì) 在各種各樣的圖中 ， 有一類圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖 ， 這就是樹 。 設(shè) G1=[ V1 , E1 ],G2=[ V2 ,E2 ] G1 G2真子圖 G3子圖 部分圖 G4導(dǎo)出子圖 G5 生成樹 G6 G5余樹 有向圖：關(guān)聯(lián)邊有方向 ?。?有向圖的邊 a=(u ,v),起點(diǎn) u ,終點(diǎn) v； 路： 若有從 u 到 v 不考慮方向的鏈 ,且 各方向一致 ,則稱之為從 u到 v 的路； 初等路 : 各頂點(diǎn)都不相同的路； 初等回路 :u = v 的初等路 。 v0 ， vn分別為鏈的起點(diǎn)和終點(diǎn) 。 v1 v5 v4 v3 v2 簡(jiǎn)單圖 （ 2） （ 4） （ 3） （ 3） （ 2） v1 v5 v4 v3 v2 多重圖 （ 4） （ 6） （ 3） （ 3） （ 2） 定理 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 d(v6)=3。 d(v2)=5 。 度為零的點(diǎn)稱為弧立點(diǎn) ， 度為 1的點(diǎn)稱為懸掛點(diǎn) 。 如果一個(gè)圖 G中 ， 一條邊的兩個(gè)端點(diǎn)是相同的 ,那么稱為這條邊是環(huán) ， 如圖 中的邊 [v3 ,v3]是環(huán) 。 如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的 ， 那么稱為它為 有向圖 ， 記作 D=(V, A)， 其中 V表示有向圖 D的點(diǎn)集合 ， A表示有向圖 D的弧集合 。 綜上所述 ， 圖論中的圖是由點(diǎn)和點(diǎn)與點(diǎn)之間的線所組成的 。 石家莊 太原 北京 天津 塘沽 濟(jì)南 青島 徐州 連云港 南京 上海 鄭州 武漢 重慶 圖 例 有六支球隊(duì)進(jìn)行足球比賽，我 們分別用點(diǎn) v1 ， … ， v6表示這六支球隊(duì)，它 們之間的比賽情況，也可以用圖反映出來(lái)， 已知 v1隊(duì)?wèi)?zhàn)勝 v2 隊(duì)， v2 隊(duì)?wèi)?zhàn)勝 v3 隊(duì)， v3 隊(duì) 戰(zhàn)勝 v5隊(duì)，如此等等。 歐拉在他的論文中證明了這是不可 能的 ， 因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相 連接 ， 不可能將它一筆畫出 ， 這就是古典圖論中的 第一個(gè)著名問(wèn)題 。 關(guān)于圖的第一篇論文是瑞士數(shù)學(xué)家歐拉（ E. Euler）在 1736年發(fā)表的解決“哥尼 斯堡” 七橋難題的論文； 德國(guó)的哥尼斯堡城有一條普雷格爾河，河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接，（見圖 a） 當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問(wèn)題，一個(gè)漫步者如何能夠走過(guò)這七座橋，并且每座橋只能走過(guò)一次，最終回到原出發(fā)地。 例如 ， 各種通信線路的架設(shè) ，輸油管道的鋪設(shè) ， 鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問(wèn)題 ， 都可以應(yīng)用圖論的方法 ，簡(jiǎn)便 、 快捷地加以解決 。 167。 最短路問(wèn)題 167。第八章 圖與網(wǎng)絡(luò)分析 主要內(nèi)容： 167。 167。 167。 隨著科學(xué)技術(shù)的進(jìn)步，特別是電子計(jì)算機(jī)技術(shù)的發(fā)展，圖論的理論獲得了更進(jìn)一步的發(fā)展，應(yīng)用更加廣泛。盡管試驗(yàn)者很多，但是都沒有成功。 在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛? 之間的關(guān)系，常常在紙上用點(diǎn)和線來(lái)畫出各式各樣 的示意圖。這個(gè)勝負(fù)情況，可以 用圖 圖 v3 v5 v2 v4 v6 v1 從以上的幾個(gè)例子可以看出 ， 我們用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖 ， 反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系 。 通常 ， 我們把 點(diǎn)與點(diǎn)之間不帶箭頭的線叫做 邊 ， 帶箭頭的線叫做 弧 。 一條方向從 vi 指向vj 的弧 ， 記作 (vi , vj)。 如果兩個(gè)端點(diǎn)之間有兩條以上的邊 ， 那么稱為它們?yōu)槎嘀剡?， 如圖 [v1 ,v2] ,[v2 ,v1]。 懸掛點(diǎn)的邊稱為懸掛邊 。 d(v3)=4 。 d(v7)=0 其中 v5 為懸掛點(diǎn)， v7 為孤立點(diǎn)。 證明： 設(shè) V1， V2 分別是圖 G中奇點(diǎn)和偶點(diǎn)的 集合，由定理 ，有 ? ? ?? ? ????1 22Vv Vv Vvqvdvdvd )()()(因?yàn)? 是偶數(shù)， 也是偶數(shù)，因此 ??Vvvd )( ?? 1Vvvd )(?? 2Vvvd )(也必是偶數(shù)，從而 V1 中的點(diǎn)數(shù)是偶數(shù)。記作（ v0 ,v1 , v2， ,v3 , …, v n1 , vn ） 簡(jiǎn)單鏈： 鏈中所含的邊均不相同； 初等鏈： 鏈中所含的點(diǎn)均不相同 , 也稱通路； 圈： 若 v0 ≠ vn 則稱該鏈為開鏈，否則稱 為 閉鏈或回路或圈 ； 簡(jiǎn)單圈： 如果在一個(gè)圈中所含的邊均不相同初等 圈： 除起點(diǎn)和終點(diǎn)外鏈中所含的點(diǎn) 均 不相同的圈； 連通圖： 圖中任意兩點(diǎn)之間均 至少有一條通路，否則 稱為不連通圖。 連通圖： 若不考慮方向 是無(wú)向連通圖 。 例 已知有六個(gè)城市 ， 它們之間 要架設(shè)電話線 ， 要求任意兩個(gè)城市均可以互相通話 ， 并且電話線的總長(zhǎng)度最短 。 并且 ，這個(gè)圖必須是無(wú)圈的 。 下面介紹樹的一些重要性質(zhì)： 定理 設(shè)圖 G=（ V， E） 是一個(gè)樹 P(G) ≥2，那么圖 G中至少有兩個(gè)懸掛點(diǎn) 。 從以上定理 ， 不難得出以下 結(jié)論 ： （ 1） 從一個(gè)樹中任意去掉一條邊 ， 那么剩下的圖不是連通圖 ， 亦即 ， 在點(diǎn)集合相同的圖中 ， 樹是含邊數(shù)最少的連通圖 。 定理 一個(gè)圖 G有支撐樹的充要條件是 G 是連通圖 。若 G1仍然含圈，則任取 G1的一個(gè)圈，再?gòu)娜χ腥我馊サ粢粭l邊，得到圖G的一支撐子圖 G2。再對(duì)剩下的圖重復(fù)以上步驟，直到不含圈時(shí)為止，這樣就得到一個(gè)支撐樹。再?gòu)娜Γ?v3,v4 v5,v3）中去掉邊 e6 。根據(jù)實(shí)際研究問(wèn)題的不同，可以具有不同的含義。 定義 如果圖 T=（ V， EI） 是圖 G的一個(gè)支撐樹，那么稱 EI上所有邊的權(quán)的和為支撐樹 T的權(quán)，記作 S(T)。 下面介紹尋求最小支撐樹的方法 破圈法 。 圖 v3 v2 v1 v4 v6 v5 5 3 1 4 2 圖 3 v6 v5 v2 v3 v4 6 2 5 5 4 4 1 v1 7 3 解： 這個(gè)問(wèn)題的解決就是要求所示賦權(quán)圖 。再取一個(gè)圈（ v3 , v5 ,v4 , v2 ,v3），去掉邊 [v3 ,v5]。 關(guān)于破圈法正確性的證明略去。注意尋找過(guò)程中，節(jié)點(diǎn)不得重復(fù)，即在找最小權(quán)數(shù)邊時(shí)不考慮已選過(guò)的邊 ,反復(fù)進(jìn)行，直到得到最短樹或證明網(wǎng)絡(luò)不存在最短樹。 8. 3最短路問(wèn)題 例 8． 6 如圖 ，每個(gè)弧旁邊的數(shù)字表示這條單行線的長(zhǎng)度。但不同的路線，經(jīng)過(guò)的總長(zhǎng)度是不同的。 Vs ,vt是 D中的兩個(gè)頂點(diǎn)， P 是 D中從 vs到 vt 的任意一條路，定義路的權(quán)是 P 中所有弧的權(quán)的和，記作 S(p)。 由于 D是有向圖，很明顯 d（ vs， vt） 與 d（ vt， vs） 一般不相等 。 Dijkstra算法的基本思想是從 vs出發(fā)，逐步向外尋找最短路。這樣，至多經(jīng)過(guò) P1 步，就可求出從 vs 到各點(diǎn) vj 的最短路。 這時(shí) ， v1是具有 P標(biāo)號(hào)的點(diǎn) 。 同理 ， 沿 （ v1 ,v4） 到達(dá) v4， 是 d（ v1, v1） +w14=1單位 。 這樣就使 v4 變成具有 P標(biāo)號(hào)的點(diǎn)。而 min {d（ v1 ,v1） +w12， d（ v1 ,v1） +w13， d（ v1 ,v4） +w46}=d（ v1,v1）+w13=3單位。永久標(biāo)號(hào)用下劃線表示；標(biāo)號(hào)中的第一個(gè)數(shù)表示從起點(diǎn)到該點(diǎn)的距離；第二個(gè)數(shù)表示該點(diǎn)的前面沒有點(diǎn)了。 最小費(fèi)用流問(wèn)題 一 引言 在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問(wèn)題 。 ?問(wèn)題描述 連通網(wǎng)絡(luò) G(V, A) 有 m 個(gè)節(jié)點(diǎn) , n條弧 , 弧 eij 上的流量上界為 cij, 求從起始節(jié)點(diǎn) vs 到終點(diǎn) vt 的最大流量。 網(wǎng)絡(luò) D上的流 ， 是指定義在弧集合 A上的一個(gè)函數(shù) f={f(vi ,vj)}={fjj} f(vi ,vj)=fij叫做弧 (vi ,vj)上的流量 。 對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流 ， 有幾個(gè)顯著的特點(diǎn)： (1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等 。 網(wǎng)絡(luò)系統(tǒng)中最大流問(wèn)題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流 f,其流量 v(f)達(dá)到最大值。 設(shè) μ是網(wǎng)絡(luò) D中連接發(fā)點(diǎn) νs和收點(diǎn) vt的一條鏈 。 2． 在弧 （ vi,vj） ∈ μ–上 ， 有 0fij?cij,即 μ–中的每一條弧是非零流弧 。 定義 設(shè)一個(gè)網(wǎng)絡(luò) D=（ V， A， C） 。 定理 在一個(gè)網(wǎng)絡(luò) D中，最大流的流量等于分離 vs 和 vt 的最小截集的截量。如有增廣鏈，那么可以按照定理 ，不斷改進(jìn)和增大可行流 f 的流量，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。 如果標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去 ， 并且 vt未被標(biāo)號(hào) ， 則表示不存在關(guān)于 f 的增廣鏈 。 每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這