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

1
最小生成树问题的数学模型及其证明
1 概述
　　迄今为止，许多学者对赋权无向图中的最小生成树问题已经进行了争论，提出了很多有效地求解算法，例如破圈法、避圈法等。其实最小生成树问题也可以用整数规划来表示，谢金星教授已给出了最1
最小生成树问题的数学模型及其证明
1 概述
　　迄今为止，许多学者对赋权无向图中的最小生成树问题已经进行了争论，提出了很多有效地求解算法，例如破圈法、避圈法等。其实最小生成树问题也可以用整数规划来表示，谢金星教授已给出了最小生成树问题的数学表达式[1]，但其中的无圈等价条件没有证明，并且无圈的等价条件还有许多种表示方法[2-9]，这些表示方法虽然数学表达式不同，但本质上是相同的。因此，该文将对无圈的等价条件给出证明，并给出赋权有向图中最小生成树问题的数学模型。
　　2 赋权无向图中最小生成树问题的数学模型
　　对一赋权无向图G，我们假定G无重边和环，即G为简洁图，事实上，若G不是简洁图，则有以下引理保证也可以求G的最小生成树。
　　引理：给定赋权无向图G，若G有重边和环，则去掉后结果不会比原来的差。
　　证明：若G有环，直接去掉，若G有重边，则将重边按权从大到小排列，只留下边权最小的边，其余的重边全去掉，得到新图G*。由于最小生成树问题是要求权最小的生成树，故由G*的生成方式知，G*的最小生成树就是G的最小生成树。
　　我们用有向图的思想来解决无向图的最小生成树问题。事实上，我们把无向图中的边加倍，看成是不同方向的双弧，这样，就把无向图转化成了有向图。我们首先给出有向树及其相关概念。
3
　　定义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；∈Vx1j≥1，vj∈Vxji=1， i≠1，xij=.]
　　其中第一组约束表示根[v1]至少有一条边连接到其它的顶点；其次组约束表示除根外，每个顶点只能有一条边进入；同时留意到，。
　　对于数学模型（）中的“各边不构成圈”的条件，从模型应用和实现的角度，我们给出各边不构成圈的充要条件：
　　定理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