对于边加权的$n$-顶点图$G$，$(1+\varepsilon)$-伸缩树覆盖是一组树的集合，其中任意一对顶点在这些树之一中都存在一条$(1+\varepsilon)$-伸缩路径。Arya等人[STOC'95]提出的著名哑铃定理表明，任何$d$维欧几里得空间中的$n$个点集都可被一个$(1+\varepsilon)$-伸缩树覆盖，且树的数量为常数，该常数依赖于$\varepsilon$和维度$d$。Bartal等人[ICALP'19]将这一结果推广到了任意加倍度量空间中。虽然Arya等人和Bartal等人的树覆盖总边数均为$O(n)$，但所有已知的树覆盖构造方法的总光度至少为$\Omega(\log n)$；是否能得到光度为常数的树覆盖一直是长期悬而未决的问题，即使对于二维点集也是如此。我们通过提出加倍图的新$(1+\varepsilon)$-伸缩扩展树覆盖构造方法，解决了这一基础问题；在扩展树覆盖中，每棵树仅能使用输入图中的边而非相应的度量空间中的边。据我们所知，这是第一个对于非平凡图族的恒定伸缩扩展树覆盖构造（更不用说$(1+\varepsilon)$-伸缩），且树的数量为常数。我们的扩展树覆盖的具体应用包括加倍图的$(1+\varepsilon)$-伸缩光树覆盖、标记模型下的紧凑$(1+\varepsilon)$-伸缩路由方案以及$(1+\varepsilon)$-伸缩路径报告距离查询结构。[...]

A $(1+\varepsilon)$-stretch tree cover of an edge-weighted $n$-vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated Dumbbell Theorem by Arya et. al. [STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with a constant number of trees, where the constant depends on $\varepsilon$ and the dimension $d$. This result was generalized for arbitrary doubling metrics by Bartal et. al. [ICALP'19]. While the total number of edges in the tree covers of Arya et. al. and Bartal et. al. is $O(n)$, all known tree cover constructions incur a total lightness of $\Omega(\log n)$; whether one can get a tree cover of constant lightness has remained a longstanding open question, even for 2-dimensional point sets. In this work we resolve this fundamental question in the affirmative, as a direct corollary of a new construction of $(1+\varepsilon)$-stretch spanning tree cover for doubling graphs; in a spanning tree cover, every tree may only use edges of the input graph rather than the corresponding metric. To the best of our knowledge, this is the first constant-stretch spanning tree cover construction (let alone for $(1+\varepsilon)$-stretch) with a constant number of trees, for any nontrivial family of graphs. Concrete applications of our spanning tree cover include a $(1+\varepsilon)$-stretch light tree cover, a compact $(1+\varepsilon)$-stretch routing scheme in the labeled model, and a $(1+\varepsilon)$-stretch path-reporting distance oracle, for doubling graphs. [...]