摘要
本文研究了边点赋权图、顶点关于图的运输量及质心,利用比较两个相邻顶点的运输量的方法,得到了一个连通树图的顶点是质心的充要条件及质心个数不大于2的结果.同时给出了求质心及最小运输量的算法,其算法的时间复杂度为O(n2),有利于可建立树图模型的优化问题的求解.
In this paper, the edge and vertex weighted graph, the transportation capacity of vertex to the graph and centroid of the graph are introduced and studied. By comparing transportation capacity of two adjacent vertices, it obtains that a necessity and sufficiency condition is that a vertex of a graph is centroid and the number of the centroids of a graph is not greater than 2. In addition, the algorithm on finding the centroid and the minimal transportation capacity are derived, of whih its complexity is O(n2). It is conducive to solve the optimization problem, which can be made by dendrogram.
出处
《数学杂志》
CSCD
北大核心
2009年第3期354-358,共5页
Journal of Mathematics
基金
重庆市教委科技计划资助项目(kj061102)
重庆三峡学院科研项目资助(2007-252)
关键词
图
边点赋权图
质心
算法
graph
edge and vertex weighted graph
eentroid
algorithm