Croisements, ordres et ultramétriques

Diday, Edwin

Mathématiques informatique et sciences humaines, Tome 83 (1983), pp. 31-54

Résumé

La représentation visuelle d'une hiérarchie induit un ordre sur les singletons. Si l'on désire représenter la même hiérarchie en tenant compte de contraintes extérieures (ordre des singletons induit par une autre hiérarchie, une partition, un indice de dissimilarité, par exemple) des croisements peuvent apparaître. Il y a un croisement dans la représentation visuelle d'une hiérarchie quand une branche horizontale (associée à un palier) est coupée par une branche verticale associée à un singleton. Il s'agit d'étudier les liens entre croisements, ordres, indices de dissimilarité et ultramétriques. On utilise la notion de compatibilité entre un ordre et un indice de dissimilarité ; on introduit les notions de semi-compatibilité et compatibilité faible. On étudie les aspects matriciels qui débouchent sur une généralisation des matrices de Robinson. On fait le lien entre toutes ces notions et les chaînes de longueur minimales au sens de l'indice de dissimilarité choisi. En introduisant la notion d'élément «compatible à gauche» ou «à droite» d'une chaîne, on donne de nouvelles propriétés concernant les chaînes incluses dans un arbre de longueur minimum. Dans le cas où cet indice est une ultramétrique, on obtient des propriétés intéressantes liant l'ordre des singletons correspondant à la visualisation d'une hiérarchie indicée et l' ultramétrique induite par cette hiérarchie.