最小生成樹

圖論（GraphTheory）是數學的一個分支，它以圖為研究對象．圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系．

最小生成樹問題是圖論中最基本的理論之一，在電路設計、運輸網絡等方面有很高的實用價值.正確地理解掌握如何構造連通圖的最小生成樹問題，將會給我們帶來巨大的經濟效益和社會效益.

比如要在n個城市之間鋪設光纜，主要目標是要使這n個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低.這就需要找到帶權的最小生成樹.本章介紹圖的基本概念，利用MATLAB找圖的最小生成樹.13.1圖的概念13.1.1定義13.1.2圖的鄰接矩陣contents13.3MATLAB求解13.2最小生成樹的算法13.1圖的概念13.1.1定義

定義13.1

一個無向圖G由一個非空點集V(G)和其中元素的無序關系集合E(G)構成，記為G=(V(G),E(G))，簡記為G=(V,E)．

稱為無向圖G的頂點集，每一個元素

稱為圖G的一個頂點；稱為無向圖G的邊集，每一個元素

（即V中兩個元素vkvl的無序對）記為

稱為無向圖G的一條邊．

定義13.2給一個圖的每一條邊（弧）賦予一個數字，則得到一個賦權圖.這些數字可以表示距離、花費、時間等，統稱為權重.

定義13.3在無向圖中，與頂點v關聯的邊數稱為v的度，記為d(v)．例13.1如圖13-1所示，圖

是一個無向圖，其中圖13-1無向圖G

定義13.4在一個無向圖

中，若從頂點vi到頂點vj有路徑相連，則稱vi，vj是連通的．若圖中任意兩點都是連通的，則稱該圖是連通圖，否則就稱為非連通圖．

例如，圖13-1中v1與v3連通（v1e1v2e4v3），v2與v4連通（v2e4v3e5v4）．并且任意兩個點都連通，所以圖13-1是連通圖．

定義13.5連通的無圈圖稱為樹，記為T．度為1的點稱為葉子節(jié)點．定義13.6若圖

及樹T之間滿足

，

則稱T是G的生成．

一個連通圖的生成樹個數有很多，圖13-1的部分生成樹如圖13-2所示．從圖13-2可以看出樹具有性質：1）連通；2）點數＝邊數＋１；3）不存在任何的圈．圖13-2圖13-1的部分生成樹定義13.7在一個賦權圖中，所有邊的權重之和最小的生成樹稱為該圖的最小生成樹．找出賦權圖的最小生成樹的問題稱為最小生成樹問題．13.1.2圖的鄰接矩陣

圖的表示方式除了直觀的點與邊的表示之外，為了借助計算機技術需要采用矩陣形式．

鄰接矩陣是圖中點與點之間的相鄰關系的一種矩陣表示形式．對于無向圖G，其鄰接矩陣為一個方陣

，n為圖G的頂點個數．其中

賦權無向圖的鄰接矩陣也是一個方陣

，n為圖G的頂點個數．其中例13.2

將圖13-3所示的圖用鄰接矩陣和賦權鄰接矩陣表示．解圖13-3所示的圖用鄰接矩陣和賦權鄰接矩陣分別表示為矩陣A和B．

由此可見無向圖的鄰接矩陣是一個對角線全為0的0-1對稱陣．圖13-3賦權圖W13.2最小生成樹的算法求解最小生成樹有Kruskal算法和Prim算法．1Kruskal算法描述如下：

對于一個連通的賦權圖G，按照如下步驟構造其最小生成樹T：1）找出G所有邊中的權重最小的邊e1作為T的第一條邊；2）選擇

，使得e2的權重最?。?）選擇

，使得e3的權重最小，且不能和前面所選的邊構成圈；4）重復步驟3），直到找出n-1條邊，則得到G的最小生成樹．

此算法可以稱為“加邊法”，初始最小生成樹邊數為0，每迭代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合里．例13.3用Kruskal算法求圖13-3所示的最小生成樹．解（1）邊v3v4的權重為所有邊中最小的，選取v3v4∈E作為第一條邊，即e1=v3v4；

（2）邊v1v4的權重為剩下的邊中最小的，選取v1v4∈E-{e1}作為第二條邊，即e2=v1v4；

（3）邊v1v2的權重為剩下的邊中最小的，但是加進來后會構成圈，故在E-{e1,e2,v1v2}中選取權重最小的邊v1v3作為第三條邊，即e3=v1v3；

（4）找到了3條邊，停止．

利用Kruskal算法得到最小生成樹見圖13-4，得到的最小生成樹的權重是15．圖13-4Kruskal算法得到最小生成樹2Prim算法

對于連通的賦權圖

，設置兩個集合P和Q，其中P用于存放G的最小生成樹中的頂點，集合Q存放G的最小生成樹的邊．

1）初始化頂點集P={v1}，v1∈V，邊集Q=?；

2）選擇v2∈V-P使得邊v1v2的賦權最小，P={v1,v2},Q={v1v2}；

3）重復步驟2），知道P=V，停止．

此算法可以稱為“加點法”，每次迭代選擇代價最小的邊對應的點，加入到最小生成樹中.算法從某一個頂點s開始，逐漸長大覆蓋整個連通網的所有頂點．例13.4用Prim算法求圖13-3所示的最小生成樹.解（1）初始化頂點集P={v1}，v1∈V，邊集Q=?；

（2）與v1相連的邊v1v2，v1v3，v1v4中權重最小的是v1v4，故選擇v4，P={v1,v4},Q={V1,V4}；

（3）選擇v2∈V-P，使得在與P中點相連的邊中v2v4的權重是最小的，P={v1,v4,v2},Q={v1v4,v2v4}（4）選擇v3∈V-P，使得在與P中點相連的邊中v1v3的權重是最小的，P={v1,v4,v2,v3},Q={v1v4,v2v4,v1v3}；

（5）P=V，停止．

利用Prim算法得到最小生成樹見圖13-5，得到的最小生成樹的權重是15．圖13-5Prim算法得到最小生成樹13.3MATLAB求解

在MATLAB中利用函數graph和minspantree來求最小生成樹，調用格式如下：

G=graph(A)

使用對稱鄰接方陣A創(chuàng)建一個加權圖.A中的每個非零元素的位置指定圖的一條邊，邊的權重等于該項的值.

例如，如果A(2,1)=10，則G包含節(jié)點2和節(jié)點1之間的一條邊，該邊的權重為10.

T

=minspantree(G)

返回圖

G

的最小生成樹

T，默認使用Prim算法

T

=minspantree(G,Name,Value)

使用一個或多個名稱-值對組參數指定的其他選項

其中G由函數graph得到的圖，minspantree(G,'Method','sparse')

使用Kruskal的算法來計算最小生成樹.例13.5繪制無向圖，并增加邊和頂點．>>G=graph([11],[23]);%創(chuàng)建一個具有3個頂點和2條邊的圖>>e=G.Edges>>G=addedge(G,2,3)>>G=addnode(G,4)>>plot(G)e=2×1tableEndNodes________1213G=graph-屬性:Edges:[3×1table]Nodes:[3×0table]G=graph-屬性:Edges:[3×1table]Nodes:[7×0table]得到無向圖見圖13-6．圖13-6無向邊例13.6創(chuàng)建一個對稱鄰接矩陣

A，該矩陣用于創(chuàng)建4階完整圖．使用鄰接矩陣創(chuàng)建不帶權重的圖．解>>A=ones(4)-diag([1111])A=0111101111011110>>G=graph(A~=0)G=graph-屬性:Edges:[6×1table]%6條邊Nodes:[4×0table]%4個節(jié)點>>G.Edgesans=6×1tableEndNodes________121314232434>>plot(G)得到無向無權圖見圖13-7．圖13-7無向無權圖例13.7繪制一個賦權無向圖．解>>A=[0,1,2;103;230]%一個賦權圖的鄰接矩陣A=012103230>>G=graph(A)G=graph-屬性:Edges:[3×2table]Nodes:[3×0table]>>G.Edges%顯示邊的信息ans=3×2tableEndNodesWeight%3條邊及對應的權重______________121132233>>plot(G,'EdgeLabel',G.Edges.Weight)得到賦權無向圖如圖13-8.圖13-8賦權無向圖例13.8使用每條邊的端節(jié)點列表創(chuàng)建并繪制一個立方體圖．將節(jié)點名稱和邊權重指定為單獨的輸入．解>>s=[111223345567];>>t=[248374656878];>>weights=[10101101101112121212];>>names={'A''B''C''D''E''F''G''H'};>>G=graph(s,t,weights,names);>>plot(G,'EdgeLabel',G.Edges.Weight)得到圖形如圖13-9所示.圖13-9無向賦權圖例13.9利用MATLAB求解圖13-3的最小生成樹．解>>A=[0675;6083;7809;5390];%圖13-3的賦權鄰接矩陣>>G=graph(A)G=graph-屬性:Edges:[6×2table]Nodes:[4×0table]>>p=plot(G,'EdgeLabel',G.Edges.Weight);>>T=minspantree(G)T=graph-屬性:Edges:[3×2table]Nodes:[4×0table]>>highlight(p,T)%粗體顯示G的最小生成樹T>>T.Edges%顯示T的邊信息ans=3×2tableEndNodesWeight______________137145243>>sum(T.Edges.Weight)%對最小生成樹的所有邊權重求和ans=15

圖13-10是利用函數graph繪制的圖13-3對應的賦權圖，圖13-11中用粗線表示的是圖13-10的最小生成樹，與圖13-5的一致．得到最小生成樹的權重為15．圖13-10MATLAB生成的賦權圖圖13-11粗線顯示圖的最小生成樹例13.10（天然氣管道的鋪設）某地區(qū)共有9個村莊，各村莊之間的距離（單位為km）如圖13.12所示，圖中每條連線表示有公路相連．現要沿公路鋪設天然氣管道，鋪設管道的人工和其他動力費用為2萬元/km，材料費用為3萬元/km．如果每個村莊均通天然氣，應如何鋪設管道，才使總的鋪設費用最少？圖13-12各村莊之間的距離表示解該問題就是最小生成樹問題，首先寫圖13-12對應的賦權圖的鄰接矩陣A，再利用函數graph和minspantree得到最小生成樹．MATLAB程序如下：clearA(1,2)=300;A(1,3)=500;A(2,3)=250;A(2,4)=200;A(3,6)=200;A(3,9)=600;A(4,5)=400;A(5,6)=270;A(5,7)=350;A(6,7)=300;A(6,8)=480;A(7,8)=550;A(8,9)=180;A(9,9)=0;A=A+A';G=graph(A);%得到鄰接矩陣A對應的賦權圖Gp=plot(G,'EdgeLabel',G.Edges.Weight);T=