论文标题
树木线性排列中边缘长度的总和
Bounds of the sum of edge lengths in linear arrangements of trees
论文作者
论文摘要
网络科学中的一个基本问题是顶点之间的拓扑或物理距离的归一化，这需要了解非均衡距离的变化范围。在这里，我们研究了树叶顶点的线性排列中物理距离变化的极限。特别是，我们研究了固定尺寸的树木的边缘长度的总和：特定树的最小值和最大值，最小值和最大值的树（Bistar树和毛毛虫树）以及最小的最小值和最大值。我们为一维空间网络的最佳分数研究建立了一些基础。
A fundamental problem in network science is the normalization of the topological or physical distance between vertices, that requires understanding the range of variation of the unnormalized distances. Here we investigate the limits of the variation of the physical distance in linear arrangements of the vertices of trees. In particular, we investigate various problems on the sum of edge lengths in trees of a fixed size: the minimum and the maximum value of the sum for specific trees, the minimum and the maximum in classes of trees (bistar trees and caterpillar trees) and finally the minimum and the maximum for any tree. We establish some foundations for research on optimality scores for spatial networks in one dimension.
