Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs

Let D = (V, A) be a complete directed graph (digraph) with a positive real weight function d : A -> {d(1),..., d(k)) subset of R+ such that 0 < d(1) < ... < d(k). For every i is an element of [k] = (1,..., k}, let us set A(i) = {(u, w) is an element of A vertical bar d(u, w) <= d(i)) and assume that each subgraph D-i = (V, A(i)), i is an element of [k], in the obtained nested family is transitive, that is, (u, w) is an element of A(i) whenever (u, v), (u, w) is an element of A(i) for some v E V. This assumption implies that the considered weighted digraph (D. d) defines a quasi-ultrametric finite space (QUMFS) and, conversely, each QUMFS is uniquely (up to an isometry) is realized by a nested family of transitive digraphs. These simple observations imply important corollaries. For example, each QUMFS can be realized by a multi-pole flow network. Furthermore, k <= (n 2) + n - 1 = -1/2(n - 1)(n + 2), where n = vertical bar V vertical bar, and this upper bound for the number k of pairwise distinct distances is precise. Moreover, we characterize all QUMFSes for which the equality holds. In the symmetric case, d(u, w) = d(w, u), we obtain a canonical representation of an ultrametric finite space (UMFS) together with the well-known bound k <= n - 1. Interestingly, due to this representation, a UMFS can be viewed as a positional game structure of k players {1,..., k} such that, in every play, they make moves in a monotone strictly decreasing order. (C) 2012 Elsevier B.V. All rights reserved.