[高等教育]第l六章運(yùn)籌學(xué)圖與網(wǎng)絡(luò)-文庫(kù)吧資料
2025-01-27 22:47本頁(yè)面
【正文】 Vvvjjjiii????例 2 如圖 S,A,B,C,D,E,T代表村鎮(zhèn) ,村鎮(zhèn)之間的連線上賦予了權(quán)值 (可代表距離 ,費(fèi)用 ,流量等 )現(xiàn)沿圖中連線架設(shè)電線 ,使各村鎮(zhèn)全部通電 ,問(wèn)如何架設(shè)使電線總長(zhǎng)最短 .(該圖稱(chēng)為賦權(quán)圖或無(wú)向網(wǎng)絡(luò) ). SABCDET2 25557734411SABCDET2 25557734411最小生成樹(shù)總長(zhǎng) =2+2+1+3+1+5=14 方法二 :破圈法 在無(wú)向網(wǎng)絡(luò)圖 N中任取一個(gè)回路 ,去掉這個(gè)回路中權(quán)數(shù)最大的邊 ,得一新網(wǎng)絡(luò) ,在 中再任取一回路 ,去掉這個(gè)回路中權(quán)數(shù)最大的邊 ,得 . 如此繼續(xù)下去 ,直到剩下的子圖中不再含回路為止 ,最后的這個(gè)子圖為 N的最小部分樹(shù) . 1N 1N2NSABCDET2 25557734411電線總長(zhǎng) =2+2+1+3+1+5=14 第三節(jié) 最短路 (Shortest path)問(wèn)題 最短路問(wèn)題是指在給定的網(wǎng)絡(luò) (有向圖和無(wú)向圖 )中 ,找出任意兩點(diǎn)間距離最短的一條路 ,這里的距離是權(quán)值的代表 .最短路問(wèn)題可應(yīng)用于選址 ,管道鋪設(shè)時(shí)的選線 ,設(shè)備更新 ,投資等方面 . 本節(jié)介紹從某一點(diǎn)到其他各點(diǎn)之間最短距離的 Dijkstra算法和網(wǎng)絡(luò)圖上任意兩點(diǎn)的最短距離的矩陣算法 . 一 .無(wú)向圖最短路的 Dijkstra算法 (1959) 基本思想 :最短路的子路一定還是最短路 . .,432143513513131321414321這與假設(shè)矛盾還短比那么就有之間的最短路是設(shè)否則的最短路一定是則的最短路是設(shè)vvvvvvvvvvvvvvvvvvvvvvvv????????????????1v 2v3v4v5vDijkstra標(biāo)號(hào)法的步驟 : .,.0,的最短路到點(diǎn)現(xiàn)在求短路點(diǎn)的最點(diǎn)出發(fā)到表示從用顯然不相鄰則令若相鄰時(shí)的距離表示兩點(diǎn)用TSiSLddjijidsiiiijij???.,。\,.3。, 54 ee⒋ 次 ,奇點(diǎn) ,偶點(diǎn) ,孤立點(diǎn) ,懸掛點(diǎn) :與某一點(diǎn) 相關(guān)聯(lián)的邊的數(shù)目 ,稱(chēng)為點(diǎn) 的次 ,記為 如 次為奇數(shù)的點(diǎn)稱(chēng)為奇點(diǎn) ,否則稱(chēng)為偶點(diǎn) ,次為 1的點(diǎn)稱(chēng)為懸掛點(diǎn) ,次為 0的點(diǎn)稱(chēng)為孤立點(diǎn) . iviv ? ?,ivd? ? ? ? ? ?1 3 54 , 5 , 1 .d v d v d v? ? ?⒌ 鏈 (chain),圈 (cycle),路 (route,path),回路 ,連通圖 :圖中某些點(diǎn)和邊的交替序列 ? ?kk vevev , 110 ???若其中各邊 互不相同 ,且對(duì)任意的點(diǎn) 均相鄰 ,稱(chēng)之為鏈 . keee , 21 ?)2(,1, ktvv itti ???如果鏈中所有的頂點(diǎn)各不相同 ,這樣的鏈稱(chēng)為路 . ? ?? ?473852473422133851,vevevvevevevevev????判斷 哪一個(gè)是鏈 ,哪一個(gè)是路 : 21,??., 2121 是一條路而不是路但是都是鏈 ????對(duì)起點(diǎn)和終點(diǎn)相重合的鏈稱(chēng)為 圈 .起點(diǎn)和終點(diǎn)重合的路稱(chēng)為 回路 .在一個(gè)圖中 ,如果任意兩點(diǎn)間至少存在一條 鏈 ,則稱(chēng)該圖為 連通圖 ,否則為不連通的 . ⒍ 完全圖 ,子圖 ,支撐子圖 (部分圖 ) 一個(gè)簡(jiǎn)單圖中 ,如果任意兩點(diǎn)之間均有邊相連 ,稱(chēng)為完全圖 . ).(,.,],[],[212121212121222111部分圖的一個(gè)支撐子圖是則稱(chēng)若有的一個(gè)子圖是則稱(chēng)如果有圖GGEEVVGGEEVVEVGEVG??????4e6e 7e8e2v3v4v 5v是圖一的子圖aa b1v2v3v4v 5v2e 3e4e6e7e8e是一個(gè)支撐子圖b例 1 有甲 ,乙 ,丙 ,丁 ,戊 ,己六名運(yùn)動(dòng)員報(bào)名參加A,B,C,D,E,F六個(gè)項(xiàng)目比賽 .報(bào)名情況如下表 ,問(wèn)六個(gè)項(xiàng)目的比賽順序如何安排 ,做到每名運(yùn)動(dòng)員不連續(xù)參加兩項(xiàng)比賽 . A B C D E F 甲 * * * 乙 * * * 丙 * * 丁 * * 戊 * * * 己 * * * 解 :把比賽項(xiàng)目看作研究對(duì)象 ,用點(diǎn)表示 .如果兩個(gè)項(xiàng)目 沒(méi)有 同一名運(yùn)動(dòng)員參加 ,表明它們?cè)诒荣愴樞蛏峡膳旁谝黄?,在代表這兩個(gè)項(xiàng)目的點(diǎn)之間連一條線 ,得一圖形 .在該圖中找一條包含全部頂點(diǎn)的路 ,就是符合要求的比賽順序 . ABCDEF結(jié)果 :比賽順序是 A,C,B,F,E,D. 練習(xí) 1 有甲 ,乙 ,丙 ,丁 ,戊 ,己六名運(yùn)動(dòng)員報(bào)名參加 A,B,C,D,E,F六個(gè)項(xiàng)目比賽 .報(bào)名情況如下表 ,問(wèn)六個(gè)項(xiàng)目的比賽順序如何安排 ,做到每名運(yùn)動(dòng)員不連續(xù)參加兩項(xiàng)比賽 . A B C D E F 甲 * * 乙 * * * 丙 * * 丁 * * 戊 * * 己 * * 練習(xí) 2 有八種化學(xué)藥品 A,B,C,D,P,R,S,T要放進(jìn)儲(chǔ)藏室保管 ,出于安全原因 ,下列各組藥不能放在同一室內(nèi) ,AR,AC,AT,RP,PS,ST,TB,BD, DC,RS,RB,PD,SC,SD,問(wèn)儲(chǔ)藏這八種藥至少需幾間房 ?具體的放置方法是什么 ? 第二節(jié) 樹(shù)和圖的最小部分樹(shù) (最小生成樹(shù) ) (Tree and minimal spanning tree) 樹(shù)的定義 :無(wú)圈的連通圖稱(chēng)為樹(shù) ,記為 T=(V,E). 鐵路的轉(zhuǎn)用線 ,管理機(jī)構(gòu)圖 ,學(xué)科分類(lèi)圖 ,AHP決策方法等 ,都可用樹(shù)來(lái)表示 . 樹(shù)的特點(diǎn) : ,即在樹(shù)上再任意增加一條邊 ,必定出現(xiàn)圈 。若點(diǎn) 與同一條邊關(guān)聯(lián) ,稱(chēng)點(diǎn) 相鄰 。? 圖的基本概念與模型 ? 樹(shù)圖和圖的最小部分樹(shù) ? 最短路問(wèn)題 ? 網(wǎng)絡(luò)的最大流 第五章 圖與網(wǎng)絡(luò)模型 (Graph and work modeling ? 教學(xué)目的與要求 :給學(xué)生建立起用圖建模的思想 ,學(xué)會(huì)用圖分析問(wèn)題 . ? 重點(diǎn)與難點(diǎn) :圖的各種概念 ,最短路的求法 ,最大流的求法 ,其中難點(diǎn)是最大流的求法 . ? 教學(xué)方法 :課堂講授結(jié)合 WinQSB軟件的使用 . ? 思考題 ,討論題 ,作業(yè) :本章習(xí)題 . ? 參考資料 :見(jiàn)前言 . ? 學(xué)時(shí)分配 :8學(xué)時(shí) . 序言 哥尼斯堡七橋問(wèn)題 : A BCD德國(guó)的哥尼斯堡城有一條普雷格爾河 ,河中有兩個(gè)島嶼 ,河的兩岸與島嶼之間有七座橋相互連接 .當(dāng)?shù)鼐用駸嶂杂谝豁?xiàng)活動(dòng) ,一個(gè)散步者如何能走過(guò)這七座橋 ,且每座橋只能走一次 ,最終回到出發(fā)地 .試驗(yàn)者很多 ,但沒(méi)有人才成功 . 1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文 ,解決了著名的哥尼斯堡七橋問(wèn)題 . 歐拉將哥尼斯堡七橋問(wèn)題抽象成如下的圖形 : A BCD哥尼斯堡七橋問(wèn)題變?yōu)?,能否從圖的某一點(diǎn)開(kāi)始不重復(fù)地一筆畫(huà)出這個(gè)圖形 .你能一筆畫(huà)出嗎 ? 歐拉
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1