數(shù)模(網(wǎng)絡(luò)圖論模型)課件

數(shù)學(xué)建模電子教案重慶郵電大學(xué)數(shù)理學(xué)院沈世云數(shù)學(xué)建模電子教案重慶郵電大學(xué)1第三章網(wǎng)絡(luò)圖論模型最短路(最短路徑)問題二.行遍性問題第三章網(wǎng)絡(luò)圖論模型最短路(最短路徑)問題二.行2圖論（GraphTheory）是運(yùn)籌學(xué)的一個(gè)重要分支，它是建立和處理離散類數(shù)學(xué)模型的一個(gè)重要工具。用圖論的方法往往能幫助人們解決一些用其它方法難于解決的問題。圖論的發(fā)展可以追溯到1736年歐拉所發(fā)表的一篇關(guān)于解決“哥尼斯堡七橋問題”的著名論文。到目前為止，圖論的模型和方法已被廣泛地應(yīng)用于系統(tǒng)工程，通訊工程，計(jì)算機(jī)科學(xué)及經(jīng)濟(jì)學(xué)領(lǐng)域，傳統(tǒng)的物理、化學(xué)、生命科學(xué)也都越來(lái)越廣泛地使用了圖論模型方法。由于這種數(shù)學(xué)模型和方法直觀形象，富有啟發(fā)性和趣味性，因而深受人們的青睞。圖論（GraphTheory）是運(yùn)籌學(xué)的一個(gè)重要分支，它3從七橋問題說(shuō)起

---關(guān)于圖模型哥尼斯堡七橋問題七橋問題是發(fā)生在18世紀(jì)東普魯土的哥尼斯堡的一個(gè)真實(shí)故事。在哥尼斯堡有條普萊格爾河,它有兩條支流在城市中心匯合后流入波羅的海。這條河將城市分割成四塊:A、C兩個(gè)小島和B、D兩塊陸地（如圖）。為通行方便，在四塊陸地之間建了七座橋，每到節(jié)、假日或傍晚，都有許多居民和大學(xué)生來(lái)此散步。久而久之,人們發(fā)現(xiàn)并熱衷于討論這樣一個(gè)問題:能否從四塊陸地之一出發(fā),走遍每座橋一次且僅一次然后回到出發(fā)地?自然有不少人作過實(shí)地嘗試,但一直未能實(shí)現(xiàn)。問題的提出從七橋問題說(shuō)起

---關(guān)于圖模型哥尼斯堡七橋4

1735年,有大學(xué)生寫信把問題告訴了歐拉,請(qǐng)他幫助解決。歐拉從大家的失敗中進(jìn)行抽象的數(shù)學(xué)思考,從數(shù)學(xué)角度成功地解決了問題。

1735年,有大學(xué)生寫信把問題告訴了歐拉,請(qǐng)他幫助解決。歐5

問題分析與模型假設(shè)：

1.問題的本質(zhì)是能否從一地?zé)o重復(fù)地一次走遍七橋,因而與所走過的橋的大小、形狀、長(zhǎng)短、曲直等均無(wú)關(guān)，而只要橋存在，因此不妨將其視為一條弧線；

2.四塊陸地可重復(fù)經(jīng)歷,至于陸地的大小、形狀、質(zhì)地等也與問題的本質(zhì)無(wú)關(guān)，因而可視四塊陸地為四個(gè)點(diǎn)A、B、C、D。

問題分析與模型假設(shè)：6對(duì)四個(gè)陸地A、B、C、D，若其間有橋，則用一條弧線連接起來(lái)，有兩座橋，則連兩條不重合的弧線，便得到一個(gè)圖，并稱代表陸地的四個(gè)點(diǎn)為頂點(diǎn)，代表橋的弧線為邊。這樣一來(lái)，能否從一地出發(fā)走遍七座橋一次且僅一次再回到出發(fā)點(diǎn)就變成了：能否從這個(gè)圖上任一頂點(diǎn)出發(fā)，經(jīng)過每條邊一次且僅一次而回到出發(fā)頂點(diǎn)。這就是眾所周知的這個(gè)圖能否“一筆畫出”的問題。對(duì)四個(gè)陸地A、B、C、D，若其間有橋，則用一條7最短路(最短路徑)問題1、圖論的基本概念2、最短路問題及其算法3、最短路的應(yīng)用最短路(最短路徑)問題1、圖論的基本概念2、最8圖論的基本概念一、圖的概念1、圖的定義2、頂點(diǎn)的次數(shù)

3、子圖二、圖的矩陣表示1、關(guān)聯(lián)矩陣2、鄰接矩陣返回圖論的基本概念一、圖的概念1、圖的定義29定義有序三元組G=(V,E,)稱為一個(gè)圖.圖的定義定義有序三元組G=(V,E,)稱為一個(gè)圖.圖的定10定義定義定義定義11數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件12返回返回13頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù)14例在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。返回例在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的返回15子圖子圖16關(guān)聯(lián)矩陣注：假設(shè)圖為簡(jiǎn)單圖關(guān)聯(lián)矩陣注：假設(shè)圖為簡(jiǎn)單圖17鄰接矩陣注：假設(shè)圖為簡(jiǎn)單圖鄰接矩陣注：假設(shè)圖為簡(jiǎn)單圖18數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件19最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對(duì)頂點(diǎn)之間的最短路最短路問題及其算法一、基本概念二、固20基本概念基本概念21數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件22數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件23數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件24數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件25數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件26數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件27數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件28數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件29數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件30．．31（2）對(duì)任意的，

（2）對(duì)任意的，32數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件33數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件34數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件35算法步驟：算法步驟：36數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件37數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件38u1u2u3u4u5u6u7u8返回u1u2u3u4u5u6u7u8返回39每對(duì)頂點(diǎn)之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（三）算法步驟每對(duì)頂點(diǎn)之間的最短路1、求距離矩陣的方法240算法的基本思想算法的基本思想41算法原理——求距離矩陣的方法返回算法原理——求距離矩陣的方法返回42算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來(lái)查找任何點(diǎn)對(duì)之間最短路的路徑．返回算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑43ij算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：返回ij算法原理——查找最短路路徑的方法pkp2p1p3q144算法步驟算法步驟45TOMATLAB(road2(floyd))返回TOMATLAB返回46一、可化為最短路問題的多階段決策問題二、選址問題1、中心問題2、重心問題返回一、可化為最短路問題的多階段決策問題二、選址問題147可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題48數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件49數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件50返回返回51

選址問題--中心問題TOMATLAB(road3(floyd))選址問題--中心問題TOMATLAB52S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處。返回S(v1)=10,S(v2)=7,S(v3)=6,S(53

選址問題--重心問題返回選址問題--重心問題返回54三樹圖與最小生成樹一般研究無(wú)向圖樹圖：倒置的樹，根(root)在上，樹葉(leaf)在下多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是典型的樹圖三樹圖與最小生成樹一般研究無(wú)向圖55

1、樹的定義及其性質(zhì)

已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。v1v2v3v4v5v61)、一個(gè)連通的無(wú)圈的無(wú)向圖叫做樹。樹中次為1的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分支點(diǎn)。1、樹的定義及其性質(zhì)v1v2v3v4v5v61)、56樹

的性質(zhì)：（1）數(shù)必連通，但無(wú)回路（圈）。（2）n個(gè)頂點(diǎn)的樹必有n-1條邊。（3）樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。（4）樹

連通，但去掉任一條邊，必變?yōu)椴贿B通。（5）樹無(wú)回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。v1v2v3v4v5v6樹的性質(zhì)：v1v2v3v4v5v6572)、設(shè)圖是圖G=(V,E)的一支撐子圖，如果圖是一個(gè)樹,那么稱K是G的一個(gè)生成樹（支撐樹），或簡(jiǎn)稱為圖G的樹。圖G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。一個(gè)圖G有生成樹的充要條件是G

是連通圖。v1v2v3v4v5v1v2v3v4v52)、設(shè)圖是圖G=(V,E58用破圈法求出下圖的一個(gè)生成樹。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8用破圈法求出下圖的一個(gè)生成樹。v1v2v3v4v5e1e259（一）破圈法（一）破圈法60（二）避圈法

在圖中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，再找一條與{e1，e2}不構(gòu)成圈的邊e3。一般設(shè)已有{e1，e2，…，ek}，找一條與{e1，e2，…，ek}中任何一些邊不構(gòu)成圈的邊ek+1，重復(fù)這個(gè)過程，直到不能進(jìn)行為止。（二）避圈法在圖中任取一條邊e1，找一條與e161v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5v1v2v3v4v5v6v1v3v1v3v2v1v3v2v562樹T是連通圖G的生成樹(spanningtree)，若T是G的子圖且包含圖G的所有的節(jié)點(diǎn)；包含圖G中部分指定節(jié)點(diǎn)的樹稱為steinertree每個(gè)節(jié)點(diǎn)有唯一標(biāo)號(hào)的圖稱為標(biāo)記圖，標(biāo)記圖的生成樹稱為標(biāo)記樹(labeledtree)Caylay定理：n(2)個(gè)節(jié)點(diǎn)，有nn2個(gè)不同的標(biāo)記樹2.圖的生成樹2.圖的生成樹632.圖的生成樹如何找到一棵生成樹深探法(depthfirstsearch)：任選一點(diǎn)標(biāo)記為0點(diǎn)開始搜索，選一條未標(biāo)記的邊走到下一點(diǎn)，該點(diǎn)標(biāo)記為1，將走過的邊標(biāo)記；假設(shè)已標(biāo)記到i點(diǎn)，總是從最新標(biāo)記的點(diǎn)向下搜索，若從i點(diǎn)無(wú)法向下標(biāo)記，即與i點(diǎn)相關(guān)聯(lián)的邊都已標(biāo)記或相鄰節(jié)點(diǎn)都已標(biāo)記，則退回到

i

1點(diǎn)繼續(xù)搜索，直到所有點(diǎn)都被標(biāo)記廣探法(breadthfirstsearch)：是一種有層級(jí)結(jié)構(gòu)的搜索，一般得到的是樹形圖2.圖的生成樹如何找到一棵生成樹643.最小生成樹有n個(gè)鄉(xiāng)村，各村間道路的長(zhǎng)度是已知的，如何敷設(shè)光纜線路使n個(gè)鄉(xiāng)村連通且總長(zhǎng)度最短顯然，這要求在已知邊長(zhǎng)度的網(wǎng)路圖中找最小生成樹

最小生成樹的算法：Kruskal算法：將圖中所有邊按權(quán)值從小到大排列，依次選所剩最小的邊加入邊集T，只要不和前面加入的邊構(gòu)成回路，直到T中有n1條邊，則T是最小生成樹3.最小生成樹有n個(gè)鄉(xiāng)村，各村間道路的長(zhǎng)度65

3.最小生成樹Kruskal

算法基于下述定理定理3指定圖中任一點(diǎn)vi，如果vj是距vi最近的相鄰節(jié)點(diǎn)，則關(guān)聯(lián)邊eij必在某個(gè)最小生成樹中。推論

將網(wǎng)路中的節(jié)點(diǎn)劃分為兩個(gè)不相交的集合V1和V2，V2=VV1，則V1和V2間權(quán)值最小的邊必定在某個(gè)最小生成樹中。3.最小生成樹66數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件67數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件68數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件69

3.最小生成樹最小生成樹不一定唯一定理3推論是一個(gè)構(gòu)造性定理，它指示了找最小生成樹的有效算法Prim算法：不需要對(duì)邊權(quán)排序，即可以直接在網(wǎng)路圖上操作，也可以在邊權(quán)矩陣上操作，后者適合計(jì)算機(jī)運(yùn)算

3.最小生成樹最小生成樹不一定唯一70數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件71

3.最小生成樹邊權(quán)矩陣上的Prim算法：1、根據(jù)網(wǎng)路寫出邊權(quán)矩陣，兩點(diǎn)間若沒有邊，則用表示；2、從v1開始標(biāo)記，在第一行打，劃去第一列；3、從所有打的行中找出尚未劃掉的最小元素，對(duì)該元素畫圈，劃掉該元素所在列，與該列數(shù)對(duì)應(yīng)的行打；4、若所有列都劃掉，則已找到最小生成樹(所有畫圈元素所對(duì)應(yīng)的邊)；否則，返回第3步。該算法中，打行對(duì)應(yīng)的節(jié)點(diǎn)在V1中，未劃去的列在V2中3.最小生成樹邊權(quán)矩陣上的Prim算法：723.最小生成樹Prim算法是多項(xiàng)式算法Prim算法可以求最大生成樹網(wǎng)路的邊權(quán)可以有多種解釋，如效率次數(shù)受限的最小生成樹—尚無(wú)有效算法最小Steiner樹—尚無(wú)有效算法3.最小生成樹Prim算法是多項(xiàng)式算法73行遍性問題

行遍性問題

74行遍性問題一、中國(guó)郵遞員問題二、推銷員問題三、建模案例：最佳災(zāi)情巡視路線（一）歐拉圖（二）中國(guó)郵遞員問題（一）哈密爾頓圖（二）推銷員問題行遍性問題一、中國(guó)郵遞員問題二、推銷75數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件76V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割邊G的邊e是割邊的充要條件是e不含在G的圈中．

割邊的定義：設(shè)G連通，eE(G),若從G中刪除邊e后，圖G-{e}不連通，則稱邊e為圖G的割邊．V7e3v1v2v3v4e1e2e4e5V5V6e6e7e877e3v1v2v3v4e1e2e4e5e6歐拉圖e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e3v1v2v3v4e1e2e4e5e6歐拉圖e3v1v78e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6歐拉圖非歐拉圖返回e3v1v2v3v4e1e2e4e5e3v1v2v3v4e179中國(guó)郵遞員問題-定義中國(guó)郵遞員問題-定義80中國(guó)郵遞員問題-算法

Fleury算法-基本思想：從任一點(diǎn)出發(fā)，每當(dāng)訪問一條邊時(shí)，先要進(jìn)行檢查．如果可供訪問的邊不只一條，則應(yīng)選一條不是未訪問的邊集的導(dǎo)出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.中國(guó)郵遞員問題-算法Fleury算法-基本思想：從81V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10V7e3v1v2v3v4e1e2e4e5V5V6e6e7e882

若G不是歐拉圖，則G的任何一個(gè)巡回經(jīng)過某些邊必定多于一次．

解決這類問題的一般方法是，在一些點(diǎn)對(duì)之間引入重復(fù)邊（重復(fù)邊與它平行的邊具有相同的權(quán)），使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的權(quán)的總和為最小．若G不是歐拉圖，則G的任何一個(gè)巡回經(jīng)過某些邊必83V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9V7e3v1v2v3v4e1e2e4e5V5V6e6e7e884數(shù)模(網(wǎng)絡(luò)圖論模型)ppt課件85（３）求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最佳配對(duì)．（３）求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)86返回返回87哈密爾頓圖返回哈密爾頓圖返回88推銷員問題-定義流動(dòng)推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點(diǎn)．問如何安排旅行路線使總行程最?。@就是推銷員問題．若用頂點(diǎn)表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時(shí)間、費(fèi)用），于是推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個(gè)頂點(diǎn)至少一次的最短閉通路問題．推銷員問題-定義流動(dòng)推銷員需要訪問某地區(qū)的所有城89定義在加權(quán)圖G=(V,E)中，（１）權(quán)最小的哈密爾頓圈稱為最佳H圈．（