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

五樹與生成樹

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

(a)

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

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

v5v4

v2

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

v5

v4v2

v3v8

v6v7

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

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

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

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

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

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

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

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

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

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

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

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

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