A well known result from cluster theory states that there is a 1-to-1 correspondence between dated, compact, rooted trees and ultrametrics. In this paper, we generalize this result yielding a canonical 1-to-1 correspondence between symbolically dated trees and symbolic ultrametrics, using an arbitrary set as the set of (possible) dates or values. It turns out that a rather unexpected new condition is needed to properly define symbolic ultrametrics so that the above correspondence holds. In the second part of the paper, we use our main result to derive, as a corollary, a theorem by H. J. Bandelt and M. A. Steel regarding a canonical 1-to-1 correspondence between additive trees and metrics satisfying the 4-point condition, both taking their values in abelian monoids.
1998 Academic Press
All (di-)graphs G=(V, E V 2 ) studied in this paper will be finite (and by definition without multiple edges). For a vertex v, let
denote its in-degree, and
the associated undirected graph is connected) such that there exists exactly one vertex r # V (the root) with d & (r)=0 while we have d & (v)=1 for all v # V&[r]. The leaves of a rooted tree are the vertices v of out-degree 0, all other vertices are called inner vertices. A rooted tree is called compact if d + (v) 2 holds for all Article No. AI981743 105