对图G的支撑树T, 其形心是指这样的顶点v, 使得$T-v$的最大分枝具有尽可能少的顶点, 这个分枝的顶点数称为T的形心分枝度量。最小分枝支撑树问题是寻求G的支撑树T, 使得T的形心分枝度量为最小, 这个最小值称为图G的分枝指数。在通信网络设计中, 其实际意义是使从交换中心(形心)引出的所有分枝的负荷尽可能均衡。我们在2022年提出这种新型的选址问题, 并给出基本的理论结果。本文将加深对理论与算法的研究。首先证明此问题的加权形式即使对平面图也是NP-困难的。然后对一些重要的特殊图类, 如多面体图、超立方体、乘积图$K_m\times K_n$和二部图的补图等, 分别给出这些图类分枝指数的精确值, 并得到一个启发式算法。

For a spanning tree T of graph G, the centroid of T is a vertex v for which the largest component of $T-v$ has as few vertices as possible. The number of vertices of this component is called the centroid branch weight of T. The minimum branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized. This minimum value is called the branch index of G. In application to design of communication networks, the loads of all branches leading from the switch center (centroid) should be as balanced as possible. In 2022, we proposed this new type of location problem and presented basic theoretic results. This paper is devoted to deepen the study on theory and algorithms. We first prove that the weighted version of the problem is NP-hard even for planar graphs. Then, we determine the exact formulas of branch indices for several important graph families, such as polyhedral graphs, hypercubes, and graph product $K_m\times K_n$, co-bipartite graphs, and establish a heuristic algorithm.