1、WELCOME 1-第6章 圖與網(wǎng)絡(luò)分析-第六章 圖與網(wǎng)絡(luò)分析 圖是一種模型，如公路、鐵路交通圖， 通訊網(wǎng)絡(luò)圖等。 圖示對現(xiàn)實(shí)的抽象，以點(diǎn)和線段的連接組合表示。2-第6章 圖與網(wǎng)絡(luò)分析-6.1 圖的基本概念和模型一、概念（1）圖：點(diǎn)V和邊E的集合，用以表示對某種現(xiàn)實(shí)事物的抽象。記作 G=V,E,V=v1,v2,vn, E=e1,e2,em點(diǎn)：表示所研究的事物對象； 邊：表示事物之間的聯(lián)系。v1v2v3v4v0e1e2e3e4e5e6e7e0（2）若邊e的兩個(gè)端點(diǎn)重合，則稱e為環(huán)。（3）多重邊：若某兩端點(diǎn)之間多于一條邊，則稱為多重邊。3-第6章 圖與網(wǎng)絡(luò)分析-（4）簡單圖：無環(huán)、無多重邊的圖稱為

2、簡單圖。（5）鏈：點(diǎn)和邊的交替序列，其中點(diǎn)可重復(fù)，但邊不能重復(fù)。（6）路：點(diǎn)和邊的交替序列，但點(diǎn)和邊均不能重復(fù)。（7）圈：始點(diǎn)和終點(diǎn)重合的鏈。（8）回路：始點(diǎn)和終點(diǎn)重合的路。（9）連通圖：若一個(gè)圖中，任意兩點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖。（10）子圖，部分圖：設(shè)圖G1=V1,E1, G2=V2,E2, 如果有V1V2，E1E2，則稱G1是G2的一個(gè)子圖；若V1=V2，E1E2，則稱G1是G2的一個(gè)部分圖。（11）次：某點(diǎn)的關(guān)聯(lián)邊的個(gè)數(shù)稱為該點(diǎn)的次，以d(vi)表示。4-第6章 圖與網(wǎng)絡(luò)分析-二、圖的模型 例：有甲、乙、丙、丁、戊、己六名運(yùn)動(dòng)員報(bào)名參加A、B、C、D、E、F六個(gè)項(xiàng)目的比

3、賽。如表中所示，打“”的項(xiàng)目是各運(yùn)動(dòng)員報(bào)名參加比賽的項(xiàng)目。問：六個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，才能做到使每名運(yùn)動(dòng)員不連續(xù)地參加兩項(xiàng)比賽？甲 乙 丙 丁 戊 己項(xiàng)目人ABCDEF 5-第6章 圖與網(wǎng)絡(luò)分析-建立模型：解：項(xiàng)目作為研究對象，排序。設(shè) 點(diǎn)：表示運(yùn)動(dòng)項(xiàng)目。邊：若兩個(gè)項(xiàng)目之間無同一名運(yùn)動(dòng)員參加。ABCDEFACDEFBAFEDCBACBFEDAFBCDE順序：6-第6章 圖與網(wǎng)絡(luò)分析-6.2 樹圖和圖的最小部分樹（1）樹：無圈的連通圖稱為樹圖，簡稱為樹。一、樹圖的概念7-第6章 圖與網(wǎng)絡(luò)分析-（2）樹的特性： 樹是邊數(shù)最多的無圈連通圖。在樹中任加一條邊，就會(huì)形成圈。 樹是邊數(shù)最少的連通圖。

4、在樹中任減一條邊，則不連通。（3）圖的最小部分樹：定義：若G1是G2的一個(gè)部分圖，且為樹圖，則稱G1是G2的一個(gè)部分樹。G2：ABCD547365576G1：ACBD8-第6章 圖與網(wǎng)絡(luò)分析-定義：樹枝總長為最短的部分樹稱為圖的最小部分樹。二、最小部分樹的求法例：要在下圖所示的各個(gè)位置之間建立起通信網(wǎng)絡(luò)，試確定使總距離最佳的方案。樹枝：樹圖中的邊稱為樹枝。9-第6章 圖與網(wǎng)絡(luò)分析-SABCDET252414317557最小部分樹長Lmin=1410-第6章 圖與網(wǎng)絡(luò)分析-1. 避圈法：將圖中所有的點(diǎn)分V為V兩部分，V最小部分樹內(nèi)點(diǎn)的集合V非最小部分樹內(nèi)點(diǎn)的集合 任取一點(diǎn)vi加粗，令viV， 取

5、V中與V相連的邊中一條最短的邊(vi,vj)， 加粗(vi,vj)，令vjV 重復(fù) ，至所有的點(diǎn)均在V之內(nèi)。2. 破圈法： 任取一圈，去掉其中一條最長的邊， 重復(fù)，至圖中不存在任何的圈為止。11-第6章 圖與網(wǎng)絡(luò)分析-SABCDET252414317557 最小部分樹長Lmin=1412-第6章 圖與網(wǎng)絡(luò)分析-6.3 最短路問題 在圖示的網(wǎng)絡(luò)圖中，從給定的點(diǎn)S出發(fā)，要到達(dá)目的地T。問：選擇怎樣的行走路線，可使總行程最短？方法：Dijkstra（D氏）標(biāo)號(hào)法按離出發(fā)點(diǎn)的距離由近至遠(yuǎn)逐漸標(biāo)出最短距離和最佳行進(jìn)路線。S1求某兩點(diǎn)間最短距離的D（Dijkstra）氏標(biāo)號(hào)法24713-第6章 圖與網(wǎng)絡(luò)分

6、析-SABCDET25241431755702447891413594 最短路線：S AB E D T最短距離：Lmin=1314-第6章 圖與網(wǎng)絡(luò)分析-2求任意兩點(diǎn)間最短距離的矩陣算法 構(gòu)造任意兩點(diǎn)間直接到達(dá)的最短距離矩陣D（0）= dij（0） S A B C D E T S 0 2 5 4 A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0D（0）= 構(gòu)造任意兩點(diǎn)間直接到達(dá)、或者最多經(jīng)過1個(gè)中間點(diǎn)到達(dá)的最短距離矩陣D（1）= dij（1）15-第6章 圖與網(wǎng)絡(luò)分析-其中 dij（1）= min dir（0）+

7、 drj（0） ， S A B C D E T S 0 2 4 4 9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8 5 3 4 1 0 6 T 12 10 11 5 7 0D（1）=irjdir（0）drj（0）rdSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0）, dSD（0）+ dDE（0） , dSE（0）+ dEE（0）, dST（0）+ dTE（0） =8例如16-第6章 圖與網(wǎng)絡(luò)分析-其中 d

8、ij（2）= min dir（1）+ drj（1） S A B C D E T S 0 2 4 4 8 7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0D（2）=irjdir（1）drj（1）r 構(gòu)造任意兩點(diǎn)間最多可經(jīng)過3個(gè)中間點(diǎn)到達(dá)的最短距離矩陣 D（2）= dij（2）17-第6章 圖與網(wǎng)絡(luò)分析-其中 dij（3）= min dir（2）+ drj（2） S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2

9、 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0D（3）=irjdir（2）drj（2）r 構(gòu)造任意兩點(diǎn)間最多可經(jīng)過7個(gè)中間點(diǎn)到達(dá)的最短距離矩陣 D（3）= dij（3）18-第6章 圖與網(wǎng)絡(luò)分析-說明：一般，對于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1） ，k=0，1，2，3， 最多可經(jīng)過2k-1個(gè)中間點(diǎn)： 其數(shù)列為 0，1，3，7，15，31， 2k-1， 收斂條件：當(dāng) D（k+1）= D（k）時(shí)，計(jì)算結(jié)

10、束；設(shè)網(wǎng)絡(luò)中有p個(gè)點(diǎn)，即有p-2個(gè)中間點(diǎn)，則 2k-1-1 p-2 2k-1 k-1log2 (p-1) k Klog2(p-1)+1，計(jì)算到 k=lg(p-1)/lg2 +1時(shí)，收斂，計(jì)算結(jié)束。19-第6章 圖與網(wǎng)絡(luò)分析- 例：有7個(gè)村鎮(zhèn)要聯(lián)合建立一所小學(xué)，已知各村鎮(zhèn)小學(xué)生的人數(shù)大致為S30人， A40人，B20人，C15人，D35人，E25人， T50人。問：學(xué)校應(yīng)建在那一個(gè)地點(diǎn)，可使學(xué)生總行程最少？ S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1

11、5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0L=30 40 20 15 35 25 50人數(shù)= 1325 1030 880 1035 910 865 1485T解：20-第6章 圖與網(wǎng)絡(luò)分析-6.4 中國郵路問題問題：一名郵遞員從郵局出發(fā)，試選擇一條最短的投遞路線？v1v2v3v4v5v6v8v7v9v10v11v12v13郵局4445512412544742221-第6章 圖與網(wǎng)絡(luò)分析-22-第6章 圖與網(wǎng)絡(luò)分析-奇點(diǎn)：圖中次為奇數(shù)的點(diǎn)稱為奇點(diǎn)。偶點(diǎn)：圖中次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。結(jié)論：最短投遞路線應(yīng)具有下述特征： 若圖中所有的點(diǎn)均為偶點(diǎn)，則可不重復(fù)走遍所有街道； 重

12、復(fù)走的路線長度應(yīng)不超過所在回路總長度的一半。23-第6章 圖與網(wǎng)絡(luò)分析-步驟：兩兩連接所有的奇點(diǎn)，使之均成為偶點(diǎn)；2. 檢查重復(fù)走的路線長度，是否不超過其所在回路總長的一半，若超過，則調(diào)整連線，改走另一半。24-第6章 圖與網(wǎng)絡(luò)分析-v1v2v3v4v5v6v8v7v9v10v11v12v13郵局44455124125447422投遞距離：L=60+18=7825-第6章 圖與網(wǎng)絡(luò)分析-6.5 網(wǎng)絡(luò)最大流問題一、網(wǎng)絡(luò)最大流中有關(guān)概念 有向圖：含有以箭頭指示方向的邊的網(wǎng)絡(luò)圖。 弧：有向圖上的邊稱為弧。用（vi,vj）表示。 弧的容量：弧上通過負(fù)載的最大能力，簡稱容量。以cij表示。 流：加在網(wǎng)絡(luò)

13、每條弧上的一組負(fù)載量，以fij表示。 可行流：能夠通過網(wǎng)絡(luò)的負(fù)載量，通常應(yīng)滿足兩個(gè)條件： 容量限制條件：對所有的弧，0 fijcij 中間點(diǎn)平衡條件：對任何一個(gè)中間點(diǎn)，流入量=流出量 發(fā)點(diǎn)、收點(diǎn)、中間點(diǎn)：流的起源點(diǎn)稱發(fā)點(diǎn)，終到點(diǎn)稱收點(diǎn)，其余的點(diǎn)稱中間點(diǎn)。 最大流；能夠通過網(wǎng)絡(luò)的最大流量。 割集：一組弧的集合，割斷這些弧，能使流中斷。簡稱割。26-第6章 圖與網(wǎng)絡(luò)分析-8(8)v1vsv2v3v4vt7(5)9(4)9(9)2(0)6(1)5(5)10(8)(0,+)(vs,2)(v2,2)(v1,2)(v3,1)(v4,1)5(4)cijfij27-第6章 圖與網(wǎng)絡(luò)分析- 割的容量：割集中各弧

14、的容量之和。 最小割：所有割集中容量之和為最小的一個(gè)割集。 前向弧+：一條發(fā)點(diǎn)到收點(diǎn)鏈中，由發(fā)點(diǎn)指向收點(diǎn)的弧，又稱正向弧。 后向弧-：一條發(fā)點(diǎn)到收點(diǎn)鏈中，由收點(diǎn)指向發(fā)點(diǎn)的弧，又稱逆向弧。 增廣鏈：由發(fā)點(diǎn)到收點(diǎn)之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij0，則稱這樣的鏈為增廣鏈。定理：網(wǎng)絡(luò)的最大流量等于它的最小割集的容量。定理：當(dāng)網(wǎng)絡(luò)中不存在任何增廣鏈時(shí)，則網(wǎng)絡(luò)達(dá)到最大流狀態(tài)。二、兩個(gè)定理28-第6章 圖與網(wǎng)絡(luò)分析-st6(4)5(3)4(4)8(7)設(shè)有如下增廣鏈：f=1 該網(wǎng)絡(luò)沒有達(dá)到最大流狀態(tài)。29-第6章 圖與網(wǎng)絡(luò)分析-三、網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法(Ford-Fulkerson標(biāo)號(hào)

15、算法)基本思想：尋找增廣鏈，改善流量分布；再重復(fù)，直到不 存在任何增廣鏈為止。步驟： 給始點(diǎn)標(biāo)號(hào)：（0，+）從已標(biāo)號(hào)點(diǎn)i出發(fā)，看與其相關(guān)聯(lián)的未標(biāo)號(hào)點(diǎn)j上的弧，對+，若有0fijcij，則可對j點(diǎn)標(biāo)號(hào)，記（i, (j)），其中 (j)=min (i) ，cij - fij對-，若有0 fji cij，也可對j點(diǎn)標(biāo)號(hào)，記（ i, (j)），其中 (j)=min (i) ，fji （注：若有多個(gè)可標(biāo)號(hào)點(diǎn)，可任選其中之一。） 若標(biāo)號(hào)中斷，則得到最大流狀態(tài)，否則，重復(fù)，繼續(xù)標(biāo)號(hào)，至收點(diǎn)得到標(biāo)號(hào)，轉(zhuǎn)。30-第6章 圖與網(wǎng)絡(luò)分析-當(dāng)收點(diǎn)得到標(biāo)號(hào)，則沿標(biāo)號(hào)得到的增廣鏈進(jìn)行流量調(diào)整：對+，fij = fij +

16、 (t)對-，fij = fij - (t) 其余弧上的流量不變。 重復(fù)上述過程。 最小割集：已標(biāo)號(hào)點(diǎn)集合與未標(biāo)號(hào)點(diǎn)集合相連接的弧中， 流量=容量的弧。31-第6章 圖與網(wǎng)絡(luò)分析-8(8)v1vsv2v3v4vt7(6)9(5)9(9)2(0)6(0)5(5)10(9)5(3)(0,+)(vs,1)(v2,1)(v1,1)最大流量：fmax=14最小割集：(v3, vt), (v2, v4)32-第6章 圖與網(wǎng)絡(luò)分析-6.6 網(wǎng)絡(luò)模型的實(shí)際應(yīng)用 例1：王經(jīng)理花費(fèi)12000元購買了一臺(tái)微型車，以后年度的維護(hù)費(fèi)用取決于年初時(shí)汽車的役齡，如表示。為避免使用舊車帶來較高的維護(hù)費(fèi)用，王經(jīng)理可選擇賣掉舊車，購買新車使用的方案，舊車的預(yù)計(jì)收入如表示。為簡化計(jì)算，假定任何時(shí)刻購買新車都需花費(fèi)12000元，王經(jīng)理的目標(biāo)是使凈費(fèi)用最小（購置費(fèi)+維護(hù)費(fèi)-賣舊車收入）。役齡(年)年維護(hù)費(fèi)預(yù)計(jì)收入單位：元012345200040005000900012000700060002000 1000 033-第6章 圖與網(wǎng)絡(luò)分析-解：用網(wǎng)絡(luò)圖模型描述，歸結(jié)為最短路問題。77777123456121212122121213131441年初5年末34-第6章 圖與網(wǎng)絡(luò)分析-例2：圖示島