最小生成树(MinimalSpanningTree，MST)问题.doc

(MinimalSpanningTree,MST)问题蚃求解最小生成树的方法虽然很多,但是利用LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的MST问题非常方便。我们主要参考了文[7]。羄在图论中,称无圈的连通图为树。在一个连通图G中,称包含图G全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。膈许多实际问题都可以归结为最小生成树。例如,如何修筑一些公路把若干个城镇连接起来;如何架设通讯网络将若干个地区连接起来;如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题,以下面的问题作为范例。薆范例:假设某电话公司计划在六个村庄架设电话线,各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。肃为了便于计算机求解,特作如下规定:(1)节点V1表示树根;(2)当两个节点之间没有线路时,规定两个节点之间的距离为M(较大的值)。蚄艿V1衿螆V2膀芀V3肇膆V4羁肈V5膅薅V6蚁腿1蒈肄1莁芁2蚆蒄2膂肈2羈袃3袂聿3肇薇3蚂膁4膅羆5莃MST的整数规划模型如下:workModeling罿蚆袅袄肁肈1——3——4——2,,,,4——6——5最短距离为8芄薄袈SolutionforMinimalSpanningTreeProblemroad膇螃07-25-2000 FromNode ConnectTo Distance/Cost FromNode ConnectTo Distance/Cost肀1 Node4 Node2 2 4 Node6 Node5 2袀2 Node1 Node3 1 5 Node4 Node6 1芅3 Node3 Node4 2 膃袁 Total Minimal Connected Distance orCost = 8羁直接用人脑算:避圈法:把图中所以的点分为与两个部分。其步骤为:从图中任选一点为树根,让,图中其余的点均包含在中。从与的连线中最好哦出最短的线,若有两边相等,任取一条即可。则这条包含在最小树里。,。重复之。注意:这就是电脑的思维过程,可以用于编写代码。