如何連接通信站使費(fèi)用最少

數(shù)學(xué)實(shí)驗(yàn)第12章如何連接通信站使費(fèi)用最少

---最小生成樹2022/12/13

數(shù)學(xué)家之擅長(zhǎng)證明緣于對(duì)證明過(guò)程的大量研讀和反復(fù)實(shí)踐。同樣，可以通過(guò)涉獵引人入勝、特色各異的算法，嘗試設(shè)計(jì)各種問(wèn)題的解決方法，培養(yǎng)算法設(shè)計(jì)的成熟性和機(jī)敏性。

---作者2022/12/13實(shí)驗(yàn)?zāi)康恼莆兆钚∩蓸涞腜rim算法和Kruskal算法，了解貪婪算法的基本思想，發(fā)揮聯(lián)想力，把知識(shí)融會(huì)貫通，舉一反三。初步領(lǐng)會(huì)用Matlab語(yǔ)言編寫非數(shù)值計(jì)算問(wèn)題的編程技術(shù)；通過(guò)實(shí)例學(xué)習(xí)怎樣建立最小生成樹模型；通過(guò)自己提出問(wèn)題，動(dòng)手做實(shí)驗(yàn)，并在文獻(xiàn)檢索、調(diào)查研究、動(dòng)手和動(dòng)腦等方面得到鍛煉，提高創(chuàng)造力和解決實(shí)際問(wèn)題的能力。2022/12/13主要內(nèi)容樹圖—直觀現(xiàn)象的表示工具引例：計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)生成樹算法及其MATLAB程序?qū)崿F(xiàn)范例：制造系統(tǒng)設(shè)計(jì)的分組技術(shù)布置實(shí)驗(yàn)2022/12/1312.1樹圖—直觀形象的表示工具2022/12/1312.1樹圖—直觀形象的表示工具一個(gè)連通圖連通圖：其中任意兩點(diǎn)之間都有路徑，當(dāng)一條路徑的起點(diǎn)和終點(diǎn)是同一頂點(diǎn)時(shí)，稱這條路徑為圈2022/12/1312.1樹圖—直觀形象的表示工具

樹：沒有圈的連通圖

--樹中任意兩點(diǎn)間有唯一路徑。

--樹的邊數(shù)恰好為頂點(diǎn)數(shù)減1。--在樹中任意去掉一條邊，將會(huì)不連通。

--樹中任意兩個(gè)不相鄰頂點(diǎn)間添一邊后，就恰好含一個(gè)圈。2022/12/1312.1樹圖—直觀形象的表示工具2022/12/1312.2引例—計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)

城市電信局有許多業(yè)務(wù)如收費(fèi)，營(yíng)業(yè)，112，114等，希望在全市范圍實(shí)現(xiàn)計(jì)算機(jī)聯(lián)網(wǎng)服務(wù)，共享各種資源。一個(gè)主要關(guān)心的問(wèn)題是用數(shù)據(jù)通訊線把一組站點(diǎn)聯(lián)結(jié)起來(lái)，而不允許通訊線在非站點(diǎn)處相交，如何連接可使通訊線的花費(fèi)最?。?022/12/1312.2引例—計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)假設(shè)各站點(diǎn)間可以鋪設(shè)通訊線路進(jìn)行連接的情況如圖所示，頂點(diǎn)為站點(diǎn)，邊為連接兩站點(diǎn)之間的通訊線，邊的權(quán)為其費(fèi)用。2022/12/1312.2引例—計(jì)算機(jī)網(wǎng)絡(luò)絡(luò)的線路設(shè)設(shè)計(jì)思考：1）左圖中哪哪些是多余余的？2）最經(jīng)濟(jì)的的網(wǎng)絡(luò)應(yīng)具具備什么特特性？3）如何求出出最經(jīng)濟(jì)的的連接路線線圖？2022/12/812.2引例—計(jì)算機(jī)網(wǎng)絡(luò)絡(luò)的線路設(shè)設(shè)計(jì)最經(jīng)濟(jì)的網(wǎng)網(wǎng)絡(luò)不應(yīng)該該有任何封封閉的回路路。橡筋圈上剪剪一刀后，，仍然是一一個(gè)整段。。聯(lián)想2022/12/812.2引例—計(jì)算機(jī)網(wǎng)絡(luò)絡(luò)的線路設(shè)設(shè)計(jì)生成數(shù)或支支撐樹（spanningtree）：若G的子圖T是樹，且其其頂點(diǎn)集等等于G的頂點(diǎn)集。。2022/12/812.2引例—計(jì)算機(jī)網(wǎng)絡(luò)絡(luò)的線路設(shè)設(shè)計(jì)確定應(yīng)在哪哪些站點(diǎn)之之間鋪設(shè)通通訊線路，，是否可看看作是在相相應(yīng)的加權(quán)權(quán)圖中構(gòu)造造最小費(fèi)用用的生成樹樹的問(wèn)題？？生成樹的權(quán)權(quán)：其上所有有邊權(quán)之和和。2022/12/812.2引例—計(jì)算機(jī)網(wǎng)網(wǎng)絡(luò)的線線路設(shè)計(jì)計(jì)2022/12/812.2引例—計(jì)算機(jī)網(wǎng)網(wǎng)絡(luò)的線線路設(shè)計(jì)計(jì)2022/12/812.3生成樹算算法及其其MATLAB程序?qū)崿F(xiàn)現(xiàn)Kruskal算法算法的MATLAB程序?qū)崿F(xiàn)現(xiàn)背景聚焦焦Prim算法2022/12/8Kruskal算法2022/12/8Kruskal算法思考：計(jì)算機(jī)如如何實(shí)現(xiàn)現(xiàn)上述非非數(shù)值計(jì)計(jì)算算法法？計(jì)算機(jī)如如何判斷斷一些邊邊是否形形成圈？？2022/12/8Kruskal算法2022/12/8Kruskal算法給每個(gè)子子樹一個(gè)個(gè)不同的的編號(hào)2022/12/82022/12/8Kruskal算法2022/12/82022/12/8Kruskal算法2022/12/8最小生成樹算算法的背景聚聚焦1956年，美國(guó)電話話電報(bào)公司（（AT&T）利用最小生生成樹計(jì)算出出對(duì)幾家商業(yè)業(yè)客戶的索價(jià)價(jià)。一張大比例的的美國(guó)地圖鋪鋪在地板上，，尋找聯(lián)結(jié)所所有站點(diǎn)的總總長(zhǎng)度最小的的網(wǎng)絡(luò)。用手工（并且且跪著）操作作的方式完成成的問(wèn)題很有有限。2022/12/8最小生成樹算算法的背景聚聚焦2022/12/8最小生成樹算算法的背景聚聚焦2022/12/8Prim算法算法的手工操操作：任選一個(gè)頂點(diǎn)點(diǎn)v1，將其涂紅；；在一個(gè)端點(diǎn)為為紅色，另一一個(gè)端點(diǎn)為黃黃色的邊中，，找一條權(quán)最最小的邊涂紅紅，把該邊的的黃端點(diǎn)也涂涂成紅色；重復(fù)②直到所有頂點(diǎn)點(diǎn)都成紅色為為止，最終的的紅色邊和頂頂點(diǎn)便是最小小生成樹。2022/12/8Prim算法法2022/12/8提示示2022/12/8注意意2022/12/812.4范例例：：制制造造系系統(tǒng)統(tǒng)的的分分組組技技術(shù)術(shù)2022/12/812.4范例例：：制制造造系系統(tǒng)統(tǒng)的的分分組組技技術(shù)術(shù)2022/12/812.4范例：：制造造系統(tǒng)統(tǒng)的分分組技技術(shù)2022/12/812.4范例：：制造造系統(tǒng)統(tǒng)的分分組技技術(shù)思考：1）ω(i,j)=0和ω(i,j)=1分別表表示什什么？？2）ω表達(dá)了了什么么？2022/12/8建模2022/12/82022/12/82022/12/82022/12/8布置實(shí)驗(yàn)2022/12/8布置實(shí)驗(yàn)2022/12/82022/12/8實(shí)驗(yàn)內(nèi)容2022/12/8實(shí)驗(yàn)內(nèi)容2022/12/82022/12/82022/1