Minimum spanning trees and types of dissimilarities (Q1911844)

The author surveys and brings together a set of observations concerning dissimilarities, i.e., functions \(d\): \(X^2 \to [0, \infty)\) such that \(d(x,x) = 0\) and such that \(d(x,y) = d(y,x)\), and dissimilarity preorders \(R\) (reflexive and transitive relations) on \(X^2\), \(X\) a finite set, with the emphasis on compatibility relationships which may exist between dissimilarity and dissimilarity preorders. In particular, ultrametric and tree dissimilarities are of greatest interest as the penultimate and ultimate types on a ladder conditioned by adding one extra hypothesis at each step. Once this is done a sequence of equivalencies in the form of classification theorems is established and from these theorems corollaries extract simpler but relevant information. Proofs even of known results are thus sometimes novel and often improved as well. The theoretical points emphasize the association of particular spanning trees of \(X\) with particular dissimilarity preorders \(R\) in such a way as to be most compatible and best in the natural order on dissimilarities provided by pointwise comparison on \(X^2\). Results in Data Analysis and Operations Research point to the great utility of these notions. Furthermore, the range of papers noted in the references provide useful leads to non-francophones that could easily be missed but for articles such as these, including several by this author.