最优树算法的教学研究①

张爱平，李 强，陈志彬

(湖南工业大学理学院，湖南株洲412000)

在20世纪50年代，美国心理学家吉尔弗德在创造性思维方面作了深入的研究，认为创造性思维包括发散性思维、收敛性思维和直觉性思维等形式。教师若能在教学中巧妙地利用富有创新性的教学内容训练学生的创造性思维，则能充分发挥教育的功能，调动学生的学习积极性，激发学生的创造性，发展学生的创造能力。发掘Kruskal“避圈法”求最优树的方法，以此为实施创造性教育的典型题材，对学生开展多种创造性思维形式的训练，这是研究性教学的一种尝试。笔者试图将创新的思想融入教学中，通过设置教学的问题情境，引导学生推广“避圈法”求最优树的方法，探索研究性教学的有效途径，有效实施创造性教育。

一 实例引入及基本概念

例1在n个城市之间架设通讯线路，要求给出一个设计方案使得n个城市联系起来，且总造价最少。

在现实生活中有许多这种类似的问题，如果用点表示城市，架设在城市之间的通讯线路用带权的边表示，则得到一个n阶赋权图，即关于n个城市的通讯网络图。这个最佳设计方案，用图论的语言描述即归结为在n阶的赋权连通图中求一棵最优树的问题。

定义1 设G=[V，E]表示结点集为V，边集为E的无向图，称图 G中结点与边的交替序列 Γ =vi0ej0vi1ej1…ejlvil为vi0到vil的通路，如果起点vi0与终点vil重合即vi0=vil，则称Γ为回路。

定义2 连通无回路的无向图称为无向树，用符号T表示。

定义3 设无向连通带权图G=[V，E，W]，T是G的一棵生成树，T的各边权之和称为T的权，记作W(T);图G的所有生成树中权最小的生成树称为图G的最小生成树;图G在T中的边称为T的树枝，不在T中的边称为T的弦。

定理［1］1 设G=[V，E]是n阶m条边的无向图，则下面命题是等价的:

(1)G是树。

(2)G中任意两个结点之间存在唯一的路径。

(3)G中无回路且m=n－1。

(4)G中无回路，但在任意两个不同的结点之间加一条新边后所得图中有唯一的含有新边的一个回路。

二 设置问题情境，培养学生的创造性思维

1956年Kruskal给出了用“避圈法”求最小生成树的一个算法，算法第一步:首先将具有n个结点m条边的带权简单连通图G=[V，E，W]中的各条边，按权从小到大依次序排列，如W(e1)≤W(e2)≤…≤W(em)，其中e1的权最小，em的权最大;第二步:取权最小的两条边构成边集T0={e1，e2}，再从第三条边e3开始，按次序逐个将各边加进T0中去，如果出现回路，则将这条边放弃不加进边集T0中，按此法一直进行到T0中的边数共计n－1条为止，则T0导出的边子图就是图G的最小生成树。

定理［1］2 “避圈法”对于带权简单连通图 G=[ V，E，W ]，按Kruskal“避圈法”导出的边子图T0是图G的一棵最小生成树，且其算法如下:

(1)在图G的边集E中选择一条边ei;

(2)若选好边集 Ei= {e1，e2，…ei}，则从边集E－Ei中选取边ei+1，其中边ei+1满足:

(ⅰ)边导出图G[ Ei∪ {ei+1}]无圈;

(ⅱ)W(ei+1)是符合(ⅰ)的条件下尽可能小的权;

(3)到第二步不能再进行时则停止。

求最小生成树的Kruskal“避圈法”直观明了，目前国内的《离散数学》教材向学生介绍的都是这种方法。该方法在不构成回路的条件下优先选择图G中权尽可能小的边成为T0的边，体现的是一种有序优化构造的思想，对学生的思维具有启发性;对于这个知识点的教学可以通过设疑，向学生发问，引导学生思考求最优树的方法;在引导学生对构成最优树要素直观认识的基础上，鼓励学生求同存异，积极开展发散性思维、收敛性思维和直觉性思维。

问题1 如果将Kruskal“避圈法”中图G的边由小到大排序改为由大到小排序，即优先有序选择图G中尽可能大的边，同学们如何求带权简单连通图G=[V，E，W]的最小生成树?

问题2 类似Kruskal“避圈法”同学们能使用“破圈法”求带权简单连通图G=[V，E，W ]的最小生成树吗?

问题3 用“避圈法”和“破圈法”求带权简单连通图G=[V，E，W]的最小生成树还有其它算法吗?

以上的教学过程遵循呈现问题、解决问题和发现问题的途径向学生展开，这样做能较好地把发展学生的创造性思维与解决问题获得知识紧密结合起来。下面是引导学生获得的关于Kruskal“避圈法”推广后的一些命题，其证明方法富有思想启迪性，对学生的思维具有启发性，是有序优化方法的具体应用。

命题1若将图G的边由大到小排序，则可用“破圈法”求带权简单连通图G=[V，E，W]的最小生成树，其算法过程表述为:

第一步:首先将具有n个结点m条边的带权简单连通图G=[V，E，W]中的各条边，按权从大到小依次序排列，如W(e1)≥W(e2)≥…≥W(em)，其中e1的权最大，em的权最小;

第二步:取权最大的边e1，如果图G=[V，E，W]中存在含有边e1的圈，则删去边e1，得到边集E1={e1}，否则保留边e1，得到子图G1;

第三步:按边的次序进行到第i步，如果在图Gi－1中存在含有边ei的圈，则删去边ei，得到边集Ei=Ei－1∪{ei}，否则保留边ei，得到子图Gi，按此法一直进行到Ei中的边数共计m－n+1条为止，则子图Gi就是图G的最小生成树。

证明设n个结点m条边的带权简单连通图G的最小生成树为T，用“破圈法”得到的生成树为T0，若能证明T0的权与T的权相同，则T0是图G的一棵最小生成树。

首先将T0的边按权由大到小排列，不妨设为T0={e1，e2，…en－1}，下面分两种情形证明T0是图G的一棵最小生成树:

(ⅰ)当T0与T无公共边时:将T0中的最大边e1加到T上，由定理1可知必存在一条包含e1的唯一的回路C;在回路C中必存在一条异与e1不是T0的边a且W(a)≥W(e1)，否则，在构造T0时e1∉T0;将边a删除，得到一棵新的生成树T1=T∪{e1}－{a}且树的权为

由于T是最小生成树，即有W(T1)≥W(T)，结合(1)式得W(e1)=W(a)，这样T1是一棵最小生成树，且与T0有一条公共边e1;用T1取代T，再将e2加到T上，同理可得一棵新的生成树T2且T2∩T0={e1，e2}，即T2与T0有两条公共边。

根据以上分析作一归纳假设:设T0与T有i条权是相继递减的公共边，不妨设为e1，e2，…ei(1≤i≤n－1)，对于不在T中而在T0中的第i+1条边ei+1加到T上，由定理1可知必存在一条包含ei+1的唯一的回路C;在回路C中至少存在一条异与 e1，e2，…ei不是 T0中的边 b且 W(b)≥W(ei+1)，否则，在构造 T0时 e1，e2，…ei，ei+1中至少有一条边不在T0中;将b删除，得到一棵新的生成树Ti+1=T∪{ ei+1}－{b}且树的权为

由于T是最小生成树，即有W(Ti+1)≥W(T)，结合(2)式得W(ei+1)=W(b)，这样Ti+1是一棵最小生成树，且与 T0有 i+1 条公共边 e1，e2，…ei，ei+1;用 Ti+1取代 T，重复以上过程直到T与T0有n－1条公共边为止，得到T0与T有权完全相同的边序列，于是T0也是图G的一棵最小生成树。

(ⅱ)当T0与T有不是权相继递减的公共边时:令，不妨设f(T)=k≥1，这表明ei∈T0∩T(i=1，2，…k－1)即边的权相继递减，但边ek∈T0而ek∉T;类似情形(ⅰ)的证明，将边ek加到T上，由定理1可知必存在一条包含ek的唯一的回路C，在回路C中至少存在一条异与e1，e2，…ek－1不是T0中的边g且W(g)≥W(ek)，于是得到一棵新的生成树Tk=T∪{ek}－{ g}且树的权为

由于T是最小生成树，即有W(Tk)≥W(T)，结合(3)式得W(ek)=W(g)，这样Tk是一棵最小生成树，且与T0有k条权公共边e1，e2，…ek;用Tk取代T，重复以上过程，可以保证公共边的权为相继递减直到T与T0有n－1条公共边为止，得到T0与T有权完全相同的边序列，于是T0也是图G的一棵最小生成树。

在教学中以命题的形式启发学生解决问题，然后在解决问题中让学生发现问题，这是开展研究性数学教学不可缺少的一个重要环节。在定理2和命题1的基础上，围绕“避圈法”“破圈法”进一步激发学生的发散思维和直觉思维，引导学生思考求最优树的方法，不难会获得下面的两个命题:

命题［2］2 若不对图G的边排序，则同样可用“破圈法”求带权简单连通图G=[V，E，W ]的最小生成树，其算法表述为:

第一步:任取G中的一个回路，删除这个回路中权最大的边得到子图G1;

第二步:再在G1中任取一个回路，删除这个回路中权最大的边得到子图G2;

第三步:如此下去进行到第i步得到子图Gi，在Gi中任取一个回路，删除这个回路中权最大的边得到子图Gi+1，直到子图Gi+1无回路为止，则子图Gi+1是图G的最小生成树。

命题3若任意选取图G中的结点而不是回路，则可用“避圈法”求带权简单连通图G=[V，E，W]的最小生成树，其算法表述为:

第一步:置边集T为空集:

第二步:任选取图G中的一个结点vi1，得结点集合V1={}与=V－V1，在图G中，选取结点集合V1到中相关联的权尽可能小的边(vi1，vvi2，)，并将此边放入T中，结点放入V1中，此时结点集合

第三步:在图G中选取结点v∈V1，u∈的权尽可能小的边(v，u)且与原T中的边不构成回路，同样将此边放入T中，结点u放入V1中;如此继续直到V1=V，得到边集T的边导出图则是图G的最小生成树。

命题2与命题3的证明类似命题1，故略去。

三 结语

总之，若能运用知识的多样性，选择与现实生活联系密切、富有思想性的内容实施研究性教学，则能较好地激发学生探索问题的兴趣，让学生逐步形成辩证思考问题的思维习惯，启迪他们的创造性思维，提高他们的创新能力;在解决问题中，让他们能较好地发现条件与结论、知识与方法之间的内在联系，获得解决问题的正确方法。以上关于Kruskal“避圈法”开展研究性教学内容的尝试，旨在抛砖引玉。

［1］屈婉玲，耿素云，张立昂.离散数学［M］.北京:高等教育出版社，2007.

［2］陈正一.破圈法求最优树的一个简单证明［J］.哈尔滨船舶工程学院学报，1990，11(4):236 －237.

［3］张德琇.创造性思维的发展与教学［M］.长沙:湖南师范大学出版社，1990.