一类树图的最短路的算法

作者：王绍恒; 贾振声; 冯天祥

来源：数学杂志, 2009, (03): 354-358.

• 图
• 边点赋权图
• 质心
• 算法 graph
• edge and vertex weighted graph
• centroid
• algorithm

本文研究了边点赋权图、顶点关于图的运输量及质心,利用比较两个相邻顶点的运输量的方法,得到了一个连通树图的顶点是质心的充要条件及质心个数不大于2的结果.同时给出了求质心及最小运输量的算法,其算法的时间复杂度为O(n2),有利于可建立树图模型的优化问题的求解.

• 单位
  重庆三峡学院; 东莞职业技术学院