求最小支撑树的方法探讨

2001年　　9月第22卷　第3期郑州工业大学学报

JournalofZhengzhouUniversityofTechnologySep.　2001Vol.22　No.3

　　文章编号:1007-6492(2001)03-0104-04

求最小支撑树的方法探讨

周　丽1,黄哲浩2,王　博1,贺北方1

(1.郑州大学环境与水利学院,河南郑州450002;2.温州浅滩围涂工程建设指挥部,浙江温州325000)

摘　要:针对关系矩阵表示的复杂网络图,,的方法:直接生成法和表上作业法.,支撑树,,撑树时有独到之处.

关键词:最小支撑树;:A

0　引言

最小支撑树问题是运筹学重要内容之一,求

解这类问题的通用方法是破圈法和避圈法.若问题复杂,涉及的对象很多,给出的矩阵很庞大,要想画出网络图相当困难,此时无法用上述两方法求问题的最小支撑树.针对这种情况,本文提出不需画出网络图而直接从关系矩阵得到最小支撑树的方法:直接生成法和表上作业法.

的定义,易知n个点的无圈连通图有n-1条边,又因为最小支撑树是所有边长之和最短的树图,易知这n-1条边对应上三角关系矩阵中的n-1个尽可能小的数.有以下定理:

定理2　具有n个点的图的最小支撑树所对应的边是该图的上三角关系矩阵中n-1个数值相对较小且不构成圈的元素.定理3　设G={V,E}为n个点m条边的无向图,则G是树图,与下列命题等价.

G中没有圈,但在G中任两个不同点u,v之间增添边[u,v]所得图含唯一的一个圈[2].

上三角关系矩阵R的主对角线上的元素全为0,因而一个0代表一个点.每个0所在的行和列表示这个点与所有点的关系.矩阵R中的每一个元素所在的行和列各对应主对角线上的一个0,也就是说一个元素联系两个点.当R中m个元素构成图是树图时,则这m个元素所在的行和列对应的主对角线上的m+1个0表示这个树图所涉及的点.根据定理3,若R中另一元素位于这m+1个0中某两个0的行和列方向的交叉处,则增添这一元素后必然在树图中形成圈.若这一元素只是位于m+1个0中某一个0的行或列方向上但并不位于任两个0的行和列方向的交叉处,也就是新增添的这一元素所对应的边只是与原树图中的某一点相连,加上以后并不构成圈,可见增添这一元素后的图仍是树图.易得以下定理.

1　预备知识

定义1　设V为点的集合,E为边的集合,图G1={V1,E1},图G2={V2,E2},且V1=V2,E1<

E2,若G1是树图,则称G1是G2的部分树.

定义2　图的所有部分树中,边长总和最短的树叫该图的最小部分树(也叫最小支撑树).

定理1　图中任一个点i,若j是与i相邻点中距离最近的点,则边[i,j]一定含在该树的最小支撑树内[1].

推论　把图的所有点分成V和V 两个集合,则两集合之间连线的最短边一定包含在最小支撑树内[1].

若把n个点两两之间的关系用n×n阶矩阵R0表示,0表示某一点与它本身的关系,∞表示两点不直接相连,即没有关系,则R0是一个对称矩阵,研究时只取其上三角矩阵记作R.根据树图

　　收稿日期:2001-03-01;修订日期:2001-06-16　　基金项目:河南省自然科学基金资助项目(004041000)

　　作者简介:周　丽(1976-),女,湖北省武汉人,郑州大学硕士研究生,主要从事水资源系统分析及工程经济方面的

研究.

第3期　周　丽等　求最小支撑树的方法探讨　105

定理4　若矩阵R中m个元素构成的图是

树图,将这m个元素所对应的主对角线上的0所在的行和列均用直线涂去,则纳入另一元素仍然构成树图的充要条件是这个元素在直线上且不位于直线的交叉处.

有被“□”框起来;②数值最小;③不位于直线的交叉处.将其用“□”框起来,并将其对应的主对角线上的两个0所在的行和列用直线涂去(已涂去了的不需再涂).

(3)如此重复第2步,直到被“□”框起来的数有n-1个为止.这n-1个数就构成最小支撑树的n-1条边.

2　直接生成法与表上作业法

2.1　直接生成法

直接生成法不需画出原问题的网络图,只需根据各对象间的关系矩阵,直接得到最小支撑树.该方法是从关系矩阵着手,顺序,,圈,n-,为止.:

(1)R中找出数值最小的非零元素rij,画图连接rij对应的i点和j点,边[i,j]为最小支撑树的第1条边,在R中去掉rij,记为R1=R-rij.

(2)从矩阵R1中找出数值最小非零元素rpq,在上图中连接rpq对应的p点和q点,看其是否构成圈.若不是,则边[p,q],边[p,q]为最小支撑树的第2条边.在R中去掉rpq,记为R2=R1-rpq;否则从关系矩阵R1去掉元素rpq,再从剩下元素中找到不构成圈的最小非零元素rmn,边[m,n]为最小支撑树的第2条边,在R1中去掉rmn,记为R2=R1-rmn.

(3)如此重复第2步,直到在该图中出现第n-1条边,这时所得的树图即最小支撑树.2.2　表上作业法

上述的直接生成法是从上三角关系矩阵中找出元素,一步步画出最小支撑树.从中可看出:当关系矩阵的阶数很高、问题涉及的对象很多时,用直接生成法一步步找元素画图求最小支撑树的工作量大且作图复杂,为克服这一弊端可以采用表上作业法求最小支撑树.

表上作业法是在直接生成法的基础上,去掉作图这一步,直接在表上得到构成最小支撑树的n-1个数.该方法的关键是如何判断一元素与其它元素是否构成闭合回路.这一问题可由定理4圆满解决.表上作业法求最小支撑树的步骤如下:

(1)从上三角矩阵R中找出最小非零元素rij,将其对应的主对角线上的两个0所在的行和列用直线涂去,并将rij用“□”框起来.

(2)在上三角矩阵R中,从被直线涂去了的元素中找出一个满足以下条件的非零元素:①没

3　1所示.,为5海里.问从海岸经1

,应如何铺设使输油管长度为最短(为便于计量和检修,油管只准在各井位处分叉).

表1　8口油井间距离

Table1　Distancesbetween8oilwells　　mile

井号

1#2#3#4#5#6#7#

2#1.3

3#2.10.9

4#0.91.82.6

5#0.71.21.70.7

6#1.82.62.51.60.9

7#2.02.31.91.51.10.6

8#1.51.11.00.90.81.00.5

　　首先,用点表示各油井,关系矩阵表示它们相

互间的距离,最优解为网络图的最小支撑树.3.1　避圈法或破圈法求解

先画出整个问题的网络图,用避圈法或破圈法求出最小支撑树,如图1所示.满足题意的最短油管铺设长度为10.2海里

.

图1　8口油井的网络图和最小支撑树

Fig.1　Thewebgraphandtheminimum

spanningtreeof8oilwells

　　从此看出,原网络图共有(1+7)×7/2=28条

边,虽然不算很复杂,却也相当繁琐.3.2　直接生成法求解

据题意可得8个点之间的上三角关系矩阵

106

1.30

2.10.90

R=

郑州工业大学学报　　　　　　　　　　　　　　　　2001年

0.91.82.60

0.71.21.70.70

1.82.62.51.60.90

2.02.31.91.51.10.60

1.51.11.00.90.81.00.50

上的两个0

所在的第6行、第6列用直线涂去.

(3)重复第2步,直到有7个被“□”框起来的元素,如图5所示

.这7个数依次为r78,r67,r58,r45,r15,r38,r23,它们构成最小支撑树的7条边.可见满足题意的油管铺设方案就是这7个元素对应点的连接,输油管长度为10.2海里.

　　(1)从R中找出最小非零元素为r

78=0.5,作图连接7点和8点,边[7,8]为最小支撑树的第1条边,如图2.从R中去掉r78,记R1=R-r78.

(2)从R1r=0在图2中继续作图连接边[6,7]1中去掉r67,记R2=R1r67图3　直接生成法求最小支撑树的结果

Fig.3　Theresultofgettingtheminimumspanning

treeusingthemethodofdirectlygetting