摘要
本文研究了对于给定结点及边的图,在可新增结点的情况下求最小生成树的问题.利用文献[3]的部分结果和LINGO软件编程计算等方法,获得了费尔马点的坐标表示及n结点图的最小生成树只需至多增加n?2个结点的结果.同时寻找到四结点图的最小生成树的一般解法及理论证明,推广了费尔马点对于平面的结论到三维空间中,有利于某些可建立树图模型的优化问题的求解.
In this article, we focus on the graph which consists of given nodes and edges. We research the minimum spanning tree, in case the newly added nodes are feasible. By using the software LINGO and some of the results of literature [3] for reference, we get the coordinate representation of Fermat-point. Finally, we get that in order to get the minimum spanning tree from the n-node graph; we only need to add n - 2 nodes at most. Meanwhile, we get the common solution and the academic testification to get the minimum spanning tree from a four-node graph. In addition, we extend the results of Fermat-point between plane and space, to be conducive to solve some optimization problem to be feasible to build a tree graph model.
出处
《数学杂志》
CSCD
北大核心
2010年第6期1122-1128,共7页
Journal of Mathematics
基金
重庆市教委科技计划资助项目(KJ071117)
重庆三峡学院科研项目资助(2007-252)
