been applied. Perhaps the most important application is to taxonomy, Jardine
and Sibson (1971) Ch.7 [17], and Sneath and Sokal (1973) [36]. Here the end of
a branch of the tree represents a species and the ultrametric distance between
them shows how closely the species are related. Hierarchical cluster methods
classify species and also shows how closely species are related. This technique
has also been used in semantics, Shepard and Arabie (1979) [35]. The tech-
nique can become quite complicated because it involves statistical analysis with
continuous variates. Ultrametrics have been applied frequently in the theory of
spin glass, Weissman [39]. Ultrametrics have been used for description of slowly
driven dissipative systems, which exhibit avalanche-like behaviour, these include
earthquakes, extinction events in biological evolution, and landscape formation,
Boettcher and Paiginski (1997) [5]; also ultrametrics can describe systems with
fast relaxation, Vlad (1994) [38]. Ultrametrics are used in the theory of neural
nets, Parga and Virasoro [27]. The dynamics of random walks on ultrametric
spaces have been studied, Ogielchi and Stein (1985) [26]. Ultrametrics have
been applied to the thermodynamics of macromolecules such as RNA, Higgs
(1996) [15], and the directed polymer problem Perlman and Schwarz (1992)[28].
Bounds on the size of ultrametric structure have been discussed by Baldi and
Baun (1986) [1]. From a more theoretical angle, a category theory approach
has been elucidated by Rutten (1996) [34], and a model theoretic approach to
ultrametrics is given by Delon (1984) [10]. The relationship between ultrametric
distance and hierarchy is further discussed in Guenoche (1997) [11]. Construc-
tion of optimal ultrametric trees is discussed by Young and DeSarbo (1995)
[40]. Ultrametrics are related to p-adelic quantities, Karwowski and Mendes
(1994) [19]. P-adelic quantities are used in string theory: the way that ultra-
metrics enters here is explained in §10&§13.4 of Bekke and Freund (1993) [2].
There does not seem to be any straightforward connection of any of the above
to the optimization techniques of Prince and Smolensky (1997) [29]. As well
as ultrametric trees, there are also decision trees Hammer (1998) [14], and the
connection between them is still not known. Some of the above ultrametric
applications have been reviewed by Rammal et al (1986) [30].
1.2 Ultrametric Inequalities
There is the following relationship between trees and ultrametrics. An N -leaf
edge(node)-weighted tree corresponds to an N × N square matrix M in which
Mij = the sum of the weights of the edges (nodes) in the shortest path between
i and j . When the weights are non-zero and non-negative, M is a distance in
the usual sense.
∀x, y, z Mxy = 0 if x = y (1)
Mxy > 0 for x = y (2)
Mxy = Myx (3)
Mxy ≤ Mxz + Mzy. (4)