最小生成树问题的数学模型及其证明

孙培　刘凯

摘要：对图论中赋权无向图中最小生成树问题的数学模型，分析了建立的过程，并证明了各边不构成圈的一个等价条件，最后推广到有向图中，为用数学软件求解图论问题打下基础。

关键词：最小生成树；赋权无向图；赋权有向图

中图分类号：O221.4 文献标识码：A 文章编号：1009-3044（2014）28-6682-03

1 概述

迄今为止，许多学者对赋权无向图中的最小生成树问题已经进行了研究，提出了很多有效地求解算法，例如破圈法、避圈法等。其实最小生成树问题也可以用整数规划来表示，谢金星教授已给出了最小生成树问题的数学表达式[1]，但其中的无圈等价条件没有证明，并且无圈的等价条件还有许多种表示方法[2-9]，这些表示方法虽然数学表达式不同，但本质上是相同的。因此，该文将对无圈的等价条件给出证明，并给出赋权有向图中最小生成树问题的数学模型。

2 赋权无向图中最小生成树问题的数学模型

对一赋权无向图G，我们假定G无重边和环，即G为简单图，事实上，若G不是简单图，则有以下引理保证也可以求G的最小生成树。

引理：给定赋权无向图G，若G有重边和环，则去掉后结果不会比原来的差。

证明：若G有环，直接去掉，若G有重边，则将重边按权从大到小排列，只留下边权最小的边，其余的重边全去掉，得到新图G*。由于最小生成树问题是要求权最小的生成树，故由G*的生成方式知，G*的最小生成树就是G的最小生成树。

我们用有向图的思想来解决无向图的最小生成树问题。事实上，我们把无向图中的边加倍，看成是不同方向的双弧，这样，就把无向图转化成了有向图。我们首先给出有向树及其相关概念。

定义1 如果有向图在不考虑边的方向时，是一棵树，那么这个有向图称为有向树。进一步，如果有一颗有向树T，恰有一个顶点的入度为0，其余顶点的入度都为1，则称T为根树。

定义2 在有向树T=（V，A）中，当（u，v）∈A时，称u是v的父亲，v是u的儿子。

给定赋权无向图G（V，E），我们将它变成有向图，用[dij]表示两顶点[vi]与[vj]之间的距离，即边的权值；用决策变量[xij]表示顶点vi与vj之间的父子关系，xij=1表示顶点vi是vj的父辈，xij=0表示vi不是vj的父亲。在赋权无向图的最小生成树中，我们可以指定任一个分枝点为树的根，故不妨设顶点[v1]为生成树的根。则该问题的数学模型为：

[minD=（vi，vj）∈Edijxij；s.t.vj∈Vx1j≥1，vj∈Vxji=1， i≠1，xij=0或1.各边不构成圈.]

其中第一組约束表示根[v1]至少有一条边连接到其它的顶点；第二组约束表示除根外，每个顶点只能有一条边进入；同时注意到，各条边均不构成圈.目标函数表示总距离最小。

对于数学模型（1.1）中的“各边不构成圈”的条件，从模型应用和实现的角度，我们给出各边不构成圈的充要条件：

定理1 设T（V， A）是有向图，且存在一点v1∈V，满足d-（v1）=0，而对任意的vi（i≠1）有d-（vi）=1，则T无圈当且仅当存在一组[l（vi）∈1，…，n-1]，[i=2，…，n，]使得

[lvj≥l（vi）+xij-（n-2）?1-xij+n-3?xji，i，j=2，3，…，n，i≠j，]

其中xij=1表示（vi，vj）∈A； xij=0表示（vi，vj）[?]A.

证明：

1） 必要性

假设T（V， A）无圈，则由根树的定义，T为一根树，v1为根，现将T的顶点从根开始按下标从小到大排列，则排列后的顶点满足：若[vi]是[vj]的父亲，则i

下证不等式[lvj≥l（vi）+xij-（n-2）?1-xij+n-3?xji，i，j=2，3，…，n，i≠j]成立。

若xij=0，①xji=0，此时

[l（vi）+xij-（n-2）?1-xij+n-3?xji=l（vi）-n-2≤n-1-n-2≤lvj，]

②xji=1，表明vj是vi的父亲，此时

[l（vi）+xij-（n-2）?1-xij+n-3?xji=l（vi）-1=lvj.]

不等式成立。

若xij=1， 表明vi是vj的父辈，此时xji=0，则有

[l（vi）+xij-（n-2）?1-xij+n-3?xji=l（vi）+1=lvj，]

不等式成立。

2） 充分性

由于T（V， A）是有向图，且存在一点v1∈V，满足d-（v1）=0，而对任意的vi（i≠1）有d-（vi）=1，故假定T中有圈[（vi1，vi2，...，vim，vi1），]则有[xi1xi2=xi2xi3=…=xim-1xim=ximxi1=1，]故有

[l（i2）-l（i1）≥1，l（i3）-l（i2）≥1，…，l（im-1）-l（im）≥1，l（i1）-l（im）≥1，]相加得0≥n，矛盾，所以T无圈。

定理2 赋权无向图的最小生成树问题的数学模型为：

[minD=（vi，vj）∈Edijxij；s.t.vj∈Vx1j≥1，vj∈Vxji=1， i≠1，xij=0或1.lvj≥lvi+xij-n-2?1-xij+n-3?xjilvi=0，1，2，…，n-1.]

3 赋权有向图最小生成树问题的数学模型

设T（V，A）是一棵根树，vk（k=1，2，…，n）为树根，则有以下定理：

定理3 当G（V，A）为赋权有向图时，G的最小生成树问题的数学模型为：

[minD=i=1nj=1j≠indijxij；s.t.vj∈Vj≠kxkj≥1，vj∈Vj≠ixji=1， i≠k，xij=0或1.lvj≥lvi+xij-n-2?1-xij+n-3?xjilvi=0，1，2，…，n-1.]

其中第一组约束表示根[vk]至少有一条边连接到其它的顶点；第二组约束表示除根外，每个顶点只能有一条边进入；同时注意到，各条边均不构成圈.目标函数表示总距离最小.模型（1.4）可以利用lingo、matlab数学软件等求解。

4 实例验证

例：考虑具有8个顶点v1，v2，…，v8的赋权无向图，定义在边上的权重如表1所示，求该图的最小生成树。

5 结论

本文对于赋权无向图的最小生成树问题，分析了数学模型，给出了其中无圈的证明，并推广到赋权有向图中，从而使得借助于lingo程序可以方便地求解最小生成树问题。同时，我们还发现，将目标函数换成max，就可以求图G的权和最大的生成树。赋权无向图最小生成树模型的建立，有助于研究其他图论问题，如旅行商问題，最短路问题等。

参考文献：

[1] 谢金星，薛毅.优化建模与lindo/lingo软件[M].北京：清华大学出版社，2005.

[2] 冯俊文.赋权有向图中最小生成树问题的显式整数规划模型[J].系统工程与电子技术，1998（11）：32-36.

[3] 胡红.最小生成树的应用及拓展探讨[J].洛阳师范学院学报，2012（31）.

[4] 李萍，王春红，王文霞，任姚鹏.最小生成树算法在旅行商问题中的应用[J].电脑开发与应用，2011（25）：62-63.

[5] 李洪波，陈军.Prim最小生成树算法的动态优化[J].计算机工程与应用，2007，43（12）：69-72.

[6] 江波，张黎.基于Prim算法的最小生成树优化研究[J].计算机工程与设计，2009，30（31）：3244-3247.

[7] 李萍，王春红，王文霞，任姚鹏. 最小生成树算法在旅行商问题中的应用[J]. 电脑开发与应用，2011，25（1）：62-64.

[8] 崔承宗，马汉杰.基于最小生成树的加权中值滤波算法[J].计算机工程，2010，36（23）：209-212.

[9] 姚建华，杨成涛.用最小生成树解决TSP问题[J].湖北师范学院学报，2004，24（4）：52-54.