Minimal Spanning Trees on Infinite Sets
- Authors: Ivanov A.O.1, Tuzhilin A.A.1
-
Affiliations:
- Moscow State University
- Issue: Vol 223, No 6 (2017)
- Pages: 711-719
- Section: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/239429
- DOI: https://doi.org/10.1007/s10958-017-3380-x
- ID: 239429
Cite item
Abstract
Minimal spanning trees on infinite vertex sets are investigated. A criterion for minimality of a spanning tree having a finite length is obtained, which generalizes the corresponding classical result for finite sets. It gives an analytic description of the set of all infinite metric spaces which a minimal spanning tree exists for. A sufficient condition for the existence of a minimal spanning tree is obtained in terms of distance achievability between elements of a partition of the metric space under consideration. In addition, a concept of a locally minimal spanning tree is introduced, several properties of such trees are described, and relations of those trees with (globally) minimal spanning trees are investigated.
About the authors
A. O. Ivanov
Moscow State University
Author for correspondence.
Email: aoiva@mech.math.msu.su
Russian Federation, Moscow
A. A. Tuzhilin
Moscow State University
Email: aoiva@mech.math.msu.su
Russian Federation, Moscow