資源描述：
《圖論模型(最優(yōu)連線問題、最短路問題)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、ch8圖論模型圖論是離散數(shù)學(xué)的重要分支，在物理學(xué)、化學(xué)、系統(tǒng)工程、電力通訊、編碼理論、可靠性理論、科學(xué)管理、電子計算機等各個領(lǐng)域又具有極其廣泛的應(yīng)用。圖論的歷史可以追朔到1736年，這一年29歲的瑞士大數(shù)學(xué)家Euler發(fā)表了圖論的第一篇論文，解決了著名的哥尼斯堡七橋問題。現(xiàn)實生活中的公路交通網(wǎng)、鐵路交通網(wǎng)、灌溉網(wǎng)、自來水（石油、天然氣）管道網(wǎng)、電話線網(wǎng)計算機通訊網(wǎng)、輸電線網(wǎng)等，都可以用上述圖的方式來描述和分析解決問題。著名數(shù)學(xué)家歐拉七橋問題圖的基本概念1定義：由頂點和邊組成的圖形稱為圖。uev2邊e與頂點u、v相關(guān)聯(lián)。頂點u與v
2、相鄰。邊e1與e2相鄰。u=v時，邊e稱為環(huán)。3度定義：與頂點v關(guān)聯(lián)的邊的數(shù)目稱為頂點v的度數(shù)，記為d(v)。（注：環(huán)算2度。）對于有向圖的頂點的度數(shù)，還可分為出度和入度。定理：4圖的矩陣表示①關(guān)聯(lián)矩陣無向圖G，關(guān)聯(lián)矩陣M=（mij）有向圖G，關(guān)聯(lián)矩陣M=（mij）例1v1v2v3v4e1e4e2e3e5②鄰接矩陣無向圖G，鄰接矩陣A=（aij）有向圖G，鄰接矩陣A=（aij）有向賦權(quán)圖G，鄰接矩陣A=（aij）例2v1v2v3v4e1e4e2e3e5v1v2v3v4v1v2v3v4例3v1v2v3v428357v1v2v3v4
3、v1v2v3v48.1最優(yōu)連線問題（最小生成樹）例1現(xiàn)需從自來水廠接自來水管道到各個城鎮(zhèn)，自來水廠到各城鎮(zhèn)之間鋪設(shè)自來水管道價格如下，問如何鋪設(shè)最經(jīng)濟。水廠853191076ABCDE分析：①顯然鋪設(shè)的自來水管道要連通各個頂點；②鋪設(shè)的管道中如果有回路，則去掉一條邊，仍可行。故所鋪設(shè)的管道是連通各個頂點且沒有回路的圖形，稱為圖G的生成樹。我們的目標(biāo)是尋找一顆圖G的生成樹，其各條邊的權(quán)之和最小，稱為最小生成樹。1956年，Kruskal給出了一種求最小生成樹的算法，稱為避圈法。算法如下：（1）選擇邊，使得最??；（2）若已經(jīng)選定邊，
4、則從剩余邊集中選取，使①新選邊與之前選擇的邊組成圖為無圈圖，②新選邊是滿足①的盡可能小的權(quán)。（3）當(dāng)（2）不能繼續(xù)執(zhí)行時停止。（其思想是：在剩余邊集中找邊權(quán)最小的邊添加到生成樹中，同時又不能產(chǎn)生回路即以局部的最優(yōu)謀求全局的最優(yōu)。）上述的描述實際上是最小生成樹的逐步生長過程，上例的最小生成樹如下：水廠853191076ABCDEPrim算法：1)在圖G=(V,E)（V表示頂點，E表示邊）中，從集合V中任取一個頂點（例如取頂點v0）放入集合U中，這時U={v0}，集合T(E)為空。 2)從v0出發(fā)尋找與U中頂點相鄰（另一頂點在V中）
5、權(quán)值最小的邊的另一頂點v1，并使v1加入U。即U={v0,v1}，同時將該邊加入集合T(E)中。 3)重復(fù)(2)，直到U=V為止。 這時T(E)中有n-1條邊，T=(U,T(E))就是一棵最小生成樹。（其思想是：在剩余點集中找連接到U中頂點的最小權(quán)重的邊，添加到生成樹中。（顯然不會產(chǎn)生回路）。仍然是以局部的最優(yōu)謀求全局的最優(yōu)。）上例中，采用Prim算法最小生成樹的生長過程：水廠853191076ABCDE72911492126314678例：如何設(shè)計海底管道網(wǎng)。（Prim算法）有興趣可以用Kruskal算法計算一下，看是否有區(qū)別
6、。8.2最短通路問題1Dijkstra算法在各種網(wǎng)絡(luò)的鋪設(shè)、網(wǎng)絡(luò)的輸送、線路的安排等問題中，經(jīng)常涉及確定一條最短路。1959年，荷蘭數(shù)學(xué)家E.W.Dijkstra給出了該問題的一個解法。32101695115710852u1u2u3u4u5u6u7u8解：算法原理為螞蟻算法（探索算法），每次新連接一個點。所有新到一個點最短路程中最短的那個店，作為新增點。第一步：找從u1出發(fā)到達的距離最近的點u4，min{2,8,1}，將這個距離寫進u4的圈中。將從u1到u4的邊描成紅色，u4成為永久標(biāo)記的點；32101695115710852u
7、1u2u3u4u5u6u7u801第二步：在其余點中找從u1直接到達或從u1經(jīng)u4到達的距離最近的點u2，min{2,8,11,11}。將這個距離寫進u2的圈中，將u1到u2的邊描紅，u2成為永久的標(biāo)志的點；32101695115710852u1u2u3u4u5u6u7u8012第三步：在其余點中找從u1直接到達或從u1經(jīng)u4到達或從u1經(jīng)u2到達的的距離最近的點u5，min{8,11,11,3,9}。32101695115710852u1u2u3u4u5u6u7u80123第四步：min{8,11,11,9,8,6,12}，u
8、6。32101695115710852u1u2u3u4u5u6u7u801236第五步：min{8,11,11,9,8,12,7,11,11}，u3。32101695115710852u1u2u3u4u5u6u7u8012367第六步：min{11,12,11,
