最小生成樹模型與實(shí)驗(yàn)-展示頁
2025-04-26 02:04本頁面
【正文】 ! U( 1) = 0。 SETS: CITY / 1.. 5/: U。最小生成樹（minimal spanning tree , MST）模型概括為：給定網(wǎng)絡(luò)中一些點(diǎn)和這些點(diǎn)之間的距離，尋找連接所有這些點(diǎn)的最小總距離。2112解： 在中權(quán)值最小的邊有，從中任取一條；在中選取權(quán)值最小的邊；在中權(quán)值最小邊有，從中任取一條邊；在中選?。辉谥羞x取。第三步：把換成，返回第二步。算法的具體步驟如下：第一步：令，（空集）第二步：選一條邊，且是使圖中不含圈的所有邊中權(quán)最小的邊。（2）避圈法(Kruskal算法)：在連通圖中，任取權(quán)值最小的一條邊（若有兩條或兩條以上權(quán)相同且最小，則任取一條），在未選邊中選一條權(quán)值最小的邊，要求所選邊與已選邊不構(gòu)成圈，重復(fù)下去，直到不存在與已選邊不構(gòu)成圈的邊為止。解： 取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。例 。求最小樹通常用以下兩種方法。 ()如果生成樹的權(quán)是的所有生成樹的權(quán)中最小者，則稱是的最小生成樹，簡稱為最小樹。 設(shè)是賦權(quán)圖的一棵生成樹，稱中全部邊上的權(quán)數(shù)之和為生成樹的權(quán)，記為。一般地，設(shè)已有，找出一條不與構(gòu)成圈的邊，重復(fù)這個(gè)過程，直到不能進(jìn)行下去為止。不難發(fā)現(xiàn)，圖的生成樹不是唯一的，對(duì)于上例若這樣做：取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。 最小生成樹的實(shí)例與求解1圖 e7 由以上充分性的證明中，提供了一個(gè)尋求連通圖的生成樹的方法，稱這種方法為“破圈法”。（i i）如果含圈，任取一圈，從圈中任意去掉一條邊，得到圖的一個(gè)生成子圖，如果不含圈，那么是的一棵生成樹（因?yàn)橐滓娛沁B通的）；如果仍含少量圈，那么從中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖的一個(gè)生成子圖，如此重復(fù)，最終可以得到的一個(gè)生成子圖，它不含圈，則是圖的一棵生成樹。證：必要性是顯然的 充分性：設(shè)是連通圖。生成樹與最小樹 設(shè)圖是圖的生成子圖，如果是一棵樹，記，則稱是的一棵生成樹。上章給出了一些樹的性質(zhì)，為使能進(jìn)一步研究這部分知識(shí)，先再列出常用一些樹和生成樹的性質(zhì)。因而，滿足要求的電話線網(wǎng)所對(duì)應(yīng)的圖必定是不含圈的連通圖。為了任何兩個(gè)城市都可以通話，這樣的圖必須是連通的。圖 已知有五個(gè)城市，要在它們之間架設(shè)電話線，要求任何兩個(gè)城市都可以互相通話（允許通過其它城市），并且電話線的根數(shù)最少。上章已討論了圖和樹的簡單基本性質(zhì)。最優(yōu)化模型與實(shí)驗(yàn)第六章 最小生成樹模型與實(shí)驗(yàn)樹是圖論中的一個(gè)重要概念，由于樹的模型簡單而實(shí)用，它在企業(yè)管理、線路設(shè)計(jì)等方面都有很重要的應(yīng)用。167。為使更清楚明了，現(xiàn)在使用實(shí)例來說明。 用五個(gè)點(diǎn)代表五個(gè)城市，如果在某兩個(gè)城市之間架設(shè)電話線，則在相應(yīng)的兩個(gè)點(diǎn)之間聯(lián)一條邊，這樣一個(gè)電話線網(wǎng)就可以用一個(gè)圖來表示。其次，若圖中有圈的話，從圈上任意去掉一條邊，余下的圖仍是連通的，這樣可以省去一根電話線。 一個(gè)無圈的連通圖稱為樹. 某大學(xué)的組織機(jī)構(gòu)如下所示:文科辦公室 教務(wù)處 研究處 理科辦公室 校行政辦公室 研究生院 財(cái)務(wù)科數(shù)學(xué)系校長 行政科物理系 理工學(xué)院 校教學(xué)辦公室 人事學(xué)院
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1