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

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

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

3、10001101111010 65432166654321vvvvvvAvvvvvv例例6.2 下圖所表示的圖可以構(gòu)造鄰接矩陣下圖所表示的圖可以構(gòu)造鄰接矩陣A如下如下對(duì)于賦權(quán)圖對(duì)于賦權(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)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。域應(yīng)用極為廣泛。例例6.2 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。下圖所示。AB CDEF GH運(yùn)動(dòng)員運(yùn)動(dòng)員例例6.3 某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。廠長(zhǎng)廠長(zhǎng)人事科人事科財(cái)務(wù)科財(cái)務(wù)科總工總工程師程師生產(chǎn)副生產(chǎn)副廠長(zhǎng)廠長(zhǎng)經(jīng)營(yíng)副經(jīng)營(yíng)副廠長(zhǎng)廠長(zhǎng)開發(fā)科開發(fā)科技術(shù)科技術(shù)科生產(chǎn)科生產(chǎn)科設(shè)備科設(shè)備科供應(yīng)科供應(yīng)科銷售科銷售科檢驗(yàn)科檢驗(yàn)科動(dòng)力科動(dòng)力科 樹：無(wú)圈的連通圖即為樹

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

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

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

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

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

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

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

12、（費(fèi)用、時(shí)間），從v1修一條公路或架設(shè)一條高壓線到修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離，如何選擇一條路線使距離最短，建立該問(wèn)題的網(wǎng)絡(luò)數(shù)學(xué)模型。最短，建立該問(wèn)題的網(wǎng)絡(luò)數(shù)學(xué)模型。【解】【解】 設(shè)設(shè)xij為選擇弧為選擇弧(i，j)的狀態(tài)變量，選擇弧的狀態(tài)變量，選擇弧(i，j)時(shí)時(shí)xij1，不，不選擇弧選擇弧(i，j)時(shí)時(shí)xij0，得到最短路問(wèn)題的網(wǎng)絡(luò)模型：，得到最短路問(wèn)題的網(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的最短路及最短路長(zhǎng)的最短路及最短路長(zhǎng) v1 到到v7的最短路為：的最短路為：p17=v1, v2, v3, v5, v7，最短路長(zhǎng)為，最短路長(zhǎng)為L(zhǎng)17=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，最短路長(zhǎng)為，最短路長(zhǎng)為L(zhǎng)17=29 14P（0,V1）從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)vs到該點(diǎn)的最短路到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出vs到任意點(diǎn)的最短到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)路線，如果某個(gè)點(diǎn)vj不能標(biāo)號(hào)，說(shuō)明不能標(biāo)號(hào)，說(shuō)明vs不可不可達(dá)達(dá)vj 。二、 所有點(diǎn)對(duì)間的最短路Floyd算法 1、 寫出圖的權(quán)矩陣寫出圖的權(quán)矩陣 )()(不存在到的直達(dá)路線距離到j(luò)ijiijijvvvvldnnijdD)(、輸入權(quán)矩陣（

15、）；、 對(duì)n個(gè)頂點(diǎ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時(shí)，dij(k)=dij(k-1).。、（）中的元素就是到的最短路長(zhǎng)。如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。一、基本概念：一、基本概念：對(duì)網(wǎng)絡(luò)上的每條弧對(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通都給出一個(gè)最大的通過(guò)能力，稱為該弧的過(guò)能力，稱為該弧的，簡(jiǎn)記為，簡(jiǎn)記為cij。容量網(wǎng)絡(luò)中通常規(guī)定。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)一個(gè)(也稱源點(diǎn)，記為也稱源點(diǎn)，記為s)和一個(gè)和一個(gè)(也稱匯點(diǎn)，記為也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為網(wǎng)絡(luò)中其他點(diǎn)稱為。st48441226792. 網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。3. 流與可行流流與可行流 流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，記為是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，記為fij。若若fij=0，稱為零流。，稱為零流。在網(wǎng)絡(luò)中滿足