最小生成树问题的数学模型及其证明
中图分类号：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的权和最大的生成树。赋权无向图最小生成树模型的建立，有助于研究其他图论问题，如旅行商问题，最短路问题等。
