摘要
通过研究树上的具有非负权重的2-重心问题,得出了下面的结论:若顶点子集a,b V是树的2-重心,在树上连接顶点a和顶点b有唯一的一条路,去掉路的中点所在的边,树分成两个子树,则a和b分别是所在子树的1-重心.根据这个结论,提出了具体的算法,即树上的具有非负权重的2-重心可以通过在其子树上求1-重心来得到。树上的具有非负权重的2-重心问题的反问题,可以转化为线性规划模型求解,存在有效算法。
Based on the studies of the 2-median problem on a tree with non-negative weights, it is concluded that if the subset {a,b}lohtain in V is the 2 median of the tree, there exists an unique path in the tree joining vertex a with vertex b. Through deleting the edge on which the midpoint of the path lies, the tree is divided into two subtrees, then a and b are the 1-median of the two subtrees respectively. Based on this conclusion, a specific algorithm is proposed to solve the 2-median of the tree with non-negative weights; The inverse 2-meidan problem on a tree with non-negative weights can be translated into "a" linear programming model, which could be solved by an effective algorithm.
出处
《青岛大学学报(自然科学版)》
CAS
2008年第4期34-38,共5页
Journal of Qingdao University(Natural Science Edition)