西大數(shù)學(xué)建模賽前培訓(xùn)課件--圖

1、圖的基本概念與模型圖的基本概念與模型樹樹最短路問題最短路問題網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流近代圖論的歷史可追溯到近代圖論的歷史可追溯到18世紀(jì)的七橋問題世紀(jì)的七橋問題穿過穿過Knigsberg城的七座橋，要求每座橋通過一次且僅通過一次。城的七座橋，要求每座橋通過一次且僅通過一次。 這就是著名的這就是著名的“哥尼斯堡哥尼斯堡 7 橋橋”難題。難題。Euler1736年證明了不年證明了不可能存在這樣的路線?？赡艽嬖谶@樣的路線。例例1、有甲、乙、丙、丁、戊五個球隊，、有甲、乙、丙、丁、戊五個球隊，它們之間比賽的情況也可以用圖表示出來。它們之間比賽的情況也可以用圖表示出來。V1V2V3V4V5e5e4e1e

2、2e3e6e7一、圖基本概念一、圖基本概念強調(diào)點與點之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀；每條邊上賦有一個權(quán)；建立網(wǎng)絡(luò)模型，求最大值或最小值。142653876 63162 7 433716 圖的矩陣描述：圖的矩陣描述： 鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1. 鄰接矩陣鄰接矩陣對于圖對于圖G=（V，E），），| V |=n， | E |=m，有，有n n階方階方矩陣矩陣A=(aij) n n，其中其中 其它其它之間有關(guān)聯(lián)邊時之間有關(guān)聯(lián)邊時與與當(dāng)且僅檔當(dāng)且僅檔0vv1jiijav5v1v2v3v4v64332256437 0101011010010101111010

3、10001101111010 65432166654321vvvvvvAvvvvvv例例6.2 下圖所表示的圖可以構(gòu)造鄰接矩陣下圖所表示的圖可以構(gòu)造鄰接矩陣A如下如下對于賦權(quán)圖對于賦權(quán)圖G=(V,E), 其中邊其中邊 有權(quán)有權(quán) , 構(gòu)造矩陣構(gòu)造矩陣B=(bij) n n 其中：其中：),(jivvjiw EvvEvvwbjijijiji),(0),(654321654321 030303302004020576305020007204346040vvvvvvvvvvvvB v5v1v2v3v4v64332256437例例6.4 下圖所表示的圖可以構(gòu)造權(quán)矩陣下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下如下

4、:第二節(jié)第二節(jié) 樹樹樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。域應(yīng)用極為廣泛。例例6.2 乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。下圖所示。AB CDEF GH運動員運動員例例6.3 某企業(yè)的組織機構(gòu)圖也可用樹圖表示。某企業(yè)的組織機構(gòu)圖也可用樹圖表示。廠長廠長人事科人事科財務(wù)科財務(wù)科總工總工程師程師生產(chǎn)副生產(chǎn)副廠長廠長經(jīng)營副經(jīng)營副廠長廠長開發(fā)科開發(fā)科技術(shù)科技術(shù)科生產(chǎn)科生產(chǎn)科設(shè)備科設(shè)備科供應(yīng)科供應(yīng)科銷售科銷售科檢驗科檢驗科動力科動力科 樹：無圈的連通圖即為樹

5、樹：無圈的連通圖即為樹性質(zhì)性質(zhì)1：任何樹中必存在次為：任何樹中必存在次為1的點。的點。性質(zhì)性質(zhì)2：n 個頂點的樹必有個頂點的樹必有n-1 條邊。條邊。性質(zhì)性質(zhì)3：樹中任意兩個頂點之間，恰有且僅有一條鏈。：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質(zhì)性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)性質(zhì)5：樹無回圈，但不相鄰的兩個點之間加一條邊，?。簶錈o回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。得到一個圈。v1v2v3v4v5v6 圖的最小部分樹圖的最小部分樹(支撐樹支撐樹)如果如果G2是是G1的部分圖，又是樹圖，則稱的部分圖，又是樹圖，則稱G2是

6、是G1的部分樹的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多含有多個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2 例如，圖例如，圖4-18（a）是一個有四個頂點（）是一個有四個頂點（n=4）的連通圖，它共有的連通圖，它共有 nn-2=42=16個生成樹。個生成樹。V1V2V3V4圖圖4-18（a）破圈法破圈法：任取一圈，去掉圈中最長邊，直到無圈。：任取一圈，去掉圈中最長邊，直到無圈。5v1v

7、2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)邊數(shù)n-1=5v1v2v3v4v5v643521得到最小樹：得到最小樹：Min C(T)=15避圈法避圈法:去掉去掉G中所有邊，得到中所有邊，得到n個孤立點；然后加邊。個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通圈，直到點點連通(即即:n-1條邊條邊)。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15 1某一點到另一點的最短路的某一

8、點到另一點的最短路的狄克斯屈拉狄克斯屈拉（ Dijkstra）法）法2所有點對間的最短路所有點對間的最短路第三節(jié) 最短路問題就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路距離最短的一條路 .有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應(yīng)用。路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應(yīng)用。 里特城里特城 （Littletown）是一個鄉(xiāng)

9、村的小鎮(zhèn)。它的）是一個鄉(xiāng)村的小鎮(zhèn)。它的消防隊要為包括許多農(nóng)場社區(qū)在內(nèi)大片的地區(qū)提供消防隊要為包括許多農(nóng)場社區(qū)在內(nèi)大片的地區(qū)提供服務(wù)。在這個地區(qū)里有很多道路，從消防站到任何服務(wù)。在這個地區(qū)里有很多道路，從消防站到任何一個社區(qū)都有很多條路線。因為時間是一個到達(dá)火一個社區(qū)都有很多條路線。因為時間是一個到達(dá)火災(zāi)發(fā)生點的主要因素，所以災(zāi)發(fā)生點的主要因素，所以消防隊隊長希望事先能消防隊隊長希望事先能夠確定從消防站到每一個農(nóng)場社區(qū)的最短路夠確定從消防站到每一個農(nóng)場社區(qū)的最短路。例子：里特城例子：里特城 的消防隊問題的消防隊問題最短路：最短路：O A B E F T 19 英里英里1、算法的基本思想、算法的基

10、本思想一種標(biāo)號的迭代過程具體算法是在圖上進(jìn)行的最短路是到的最短路是到則的最短路是到則的最短路經(jīng)過點到終點若起點nnnnnnnnnnsvvpvvvvvpvvvvvvpvvvvvvv,3333222321113212.有向圖的狄克斯屈拉有向圖的狄克斯屈拉(Dijkstra)標(biāo)號算法步驟標(biāo)號算法步驟點標(biāo)號：點標(biāo)號：p(vj) 起點起點vs到點到點vj的最短路長；的最短路長；邊標(biāo)號：邊標(biāo)號：a(i，j)=p(i)+lij，步驟：步驟：(1)令起點的標(biāo)號；令起點的標(biāo)號； p(vs) 0。先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點是先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點是vs ,終點是終點是vt ,以以vi為起為起點

11、點vj為終點的弧記為（為終點的弧記為（i，j）,距離為距離為lij (2)找出所有找出所有vi已標(biāo)號已標(biāo)號vj未標(biāo)號的弧集合未標(biāo)號的弧集合 Ai=(i，j)，如果這，如果這樣的弧不存在或樣的弧不存在或vt已標(biāo)號則計算結(jié)束；已標(biāo)號則計算結(jié)束；(3)計算集合計算集合Ai中弧中弧的標(biāo)號：的標(biāo)號：a(i，j)= p(i)+lij(4)選一個點標(biāo)號選一個點標(biāo)號 返回到第返回到第(2)步。步。)(,),( | ),(min)(kpvAijijiavpkjk處標(biāo)號在終點610123214675811165圖圖519【例【例5-1】圖】圖51中的權(quán)中的權(quán)cij表示表示vi到到vj的距離（費用、時間），從的距離

12、（費用、時間），從v1修一條公路或架設(shè)一條高壓線到修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離，如何選擇一條路線使距離最短，建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型。最短，建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型?！窘狻俊窘狻?設(shè)設(shè)xij為選擇弧為選擇弧(i，j)的狀態(tài)變量，選擇弧的狀態(tài)變量，選擇弧(i，j)時時xij1，不，不選擇弧選擇弧(i，j)時時xij0，得到最短路問題的網(wǎng)絡(luò)模型：，得到最短路問題的網(wǎng)絡(luò)模型：( , )12( , )( , )57131467min102,3,610( , )ijiji jEijkii jEk iEijZc xxxxxxixxxi jE或1，6101232146758111

13、65圖圖51961012920p(9,v2)18P（6, V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)【例【例5-1】用】用Dijkstra算法求圖算法求圖51 所示所示v1到到v7的最短路及最短路長的最短路及最短路長 v1 到到v7的最短路為：的最短路為：p17=v1, v2, v3, v5, v7，最短路長為，最短路長為L17=29 14P（0,V1）610123214675811165圖圖51961012920p(9,v2)18P（6, V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)v1 到到v7的

14、最短路為：的最短路為：p17=v1, v2, v3, v5, v7，最短路長為，最短路長為L17=29 14P（0,V1）從上例知，只要某點已標(biāo)號，說明已找到起點從上例知，只要某點已標(biāo)號，說明已找到起點vs到該點的最短路到該點的最短路線及最短距離，因此可以將每個點標(biāo)號，求出線及最短距離，因此可以將每個點標(biāo)號，求出vs到任意點的最短到任意點的最短路線，如果某個點路線，如果某個點vj不能標(biāo)號，說明不能標(biāo)號，說明vs不可不可達(dá)達(dá)vj 。二、 所有點對間的最短路Floyd算法 1、 寫出圖的權(quán)矩陣寫出圖的權(quán)矩陣 )()(不存在到的直達(dá)路線距離到j(luò)ijiijijvvvvldnnijdD)(、輸入權(quán)矩陣（

15、）；、 對n個頂點的圖G,該方法迭代n步結(jié)束，第k次迭代的矩陣Dk的元素dij(k)按下式選取 dij(k) =mindij(k-1),dik(k-1）+dkj(k-1）其中，i,j=1,2,3,n。但當(dāng)i=k或j=k時，dij(k)=dij(k-1).。、（）中的元素就是到的最短路長。如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡(luò)最大流問題。這就是一個網(wǎng)絡(luò)最大流問題。一、基本概念：一、基本概念：對網(wǎng)絡(luò)上的每條弧對網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個最大的通都給出一個最大的通過能力，稱為該弧的過能力，稱為該弧的，簡記為，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定。容量網(wǎng)絡(luò)中通常規(guī)定一個一個(也稱源點，記為也稱源點，記為s)和一個和一個(也稱匯點，記為也稱匯點，記為t)，網(wǎng)絡(luò)中其他點稱為網(wǎng)絡(luò)中其他點稱為。st48441226792. 網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點到收點之間允許通過的最大流量。是指網(wǎng)絡(luò)中從發(fā)點到收點之間允許通過的最大流量。3. 流與可行流流與可行流 流流是指加在網(wǎng)絡(luò)各條弧上的實際流量，記為是指加在網(wǎng)絡(luò)各條弧上的實際流量，記為fij。若若fij=0，稱為零流。，稱為零流。在網(wǎng)絡(luò)中滿足