Primf及Krusf最小成樹及matlab源代碼

五樹與生成樹

樹是一種特殊的圖,它是圖論中重要的概念之一,它有著廣泛的應(yīng)用.在計算機科學(xué)中有如判定樹、語法樹、分類樹、搜索樹、目錄樹等等.一.樹(Tree)1.樹的定義:一個連通無回路的無向圖T,稱之為樹.如(a)

(a)

(b)4.森林:一個無向圖的每個連通分支都是樹.如(b)2.葉結(jié)點:度數(shù)為1的結(jié)點,稱為葉結(jié)點.3.分支結(jié)點(內(nèi)結(jié)點):度數(shù)大于1的結(jié)點.15.與樹定義等價的幾個命題定理給定圖T,以下關(guān)于樹的定義是等價的。⑴無回路的連通圖。⑵無回路且e=v-1其中e是T的邊數(shù),v是T的結(jié)點數(shù)。⑶連通的且e=v-1。⑷無回路但添加一條新邊那么得到一條僅有的回路。⑸連通的,但刪去任一條邊,T便不連通。⑹每對結(jié)點之間有一條且僅有一條路。

2二.生成樹(支撐樹)在圖論的應(yīng)用中,找出一個連通圖的所有不同的生成樹,以及找出最小生成樹是很有意義的.1.定義:如果圖G的生成子圖是樹,那么稱此樹為G的生成樹.2.弦:圖G中,不在其生成樹里的邊,稱作弦.所有弦的集合,稱為該生成樹的補.定理連通圖至少有一棵生成樹.v1

v5v4

v2

v33三.賦權(quán)圖的最小生成樹1.定義:一棵生成樹中的所有邊的權(quán)之和稱為該生成樹的權(quán).具有最小權(quán)的生成樹,稱為最小生成樹.最小生成樹很有實際應(yīng)用價值.例如結(jié)點是城市名,邊的權(quán)表示兩個城市間的距離,從一個城市出發(fā)走遍各個城市,如何選擇最優(yōu)的旅行路線.又如城市間的通信網(wǎng)絡(luò)問題,如何布線,使得總的線路長度最短.例如:右圖所示2.求最小生成樹算法---Kruskal算法:(避圈法)v1

v5

v4v2

v3v8

v6v7

122137724866534434Kruskal算法思想：在不形成圈得條件下，優(yōu)先挑選權(quán)小的邊形成生成樹。76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7數(shù)學(xué)建模-圖論

四、最小生成樹問題及其算法5注：算法構(gòu)造的最小生成樹的邊集為E1；標號l具有性質(zhì)：當且僅當u、v之間有一條僅由E1中的邊形成的路時，l(u)=l(v)，因此在步驟(2)發(fā)現(xiàn)l(u)=l(v)時，(u,v)不能放入E1，否那么會形成一個圈。數(shù)學(xué)建模-圖論

四、最小生成樹問題及其算法664686865505061456054例：利用Kruskal算法求出如圖G的最小生成樹：

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論78Sunday,March17,2024

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論89Sunday,March17,2024

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論910Sunday,March17,2024

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論運行結(jié)果如下：T=135163266674c=26上述例題的matlab程序如下：b=[11223334556;26364677677;24458378376];Krusf(b,1);76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v71011Sunday,March17,2024

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論

11例、一個鄉(xiāng)有7個自然村，其間道路如下圖，要以村為中心建有線播送網(wǎng)絡(luò)，如要求沿道路架設(shè)播送線，應(yīng)如何架設(shè)？abcdegf141827168213ae12dcb7gf1951213Sunday,March17,2024

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論1314Sunday,March17,2024

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論1415Sunday,March17,2024

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論

運行結(jié)果如下：T=116663263