Je commence à rédiger un ouvrage temporairement intitulé Algorithmic for Knowledge Representation. Et j'ai une petite question de vocabulaire mathématique.

J'étiquette mes hiérarchies (arbres n-aires) à l'aide de l'algorithme du nested set model.


Du coup si on a cette hiérarchie :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
  A
  |
  B-----------------C-----D
  |                 |     |      
  E------F------G   H     I------J
Où :
- A possède 3 enfants : B, C et D
- B possède 3 enfants : E, F et G
- C possède 1 enfant : H
- D possède 2 enfants : I et J

On se retrouve avec cette hiérarchie étiquetée par des intervalles :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
[0,10]
  |
[1,5]-------------[5,7]-[7,10]
  |                 |     |      
[2,3]-[3,4]-[4,5] [6,7] [8,9]-[9,10]
Où :
- un noeud est inférieur à un autre si son intervalle est contenu par celui de l'autre
- un noeud est supérieur à un autre si son intervalle contient celui de l'autre
- un noeud est égal à un autre s'il ont le même intervalle
Sinon :
- un noeud est à gauche de un autre si sa borne maximale est inférieure à la borne minimale de l'autre
- un noeud est à droite de un autre si sa borne minimale est supérieure à la borne maximale de l'autre

J'utilise en plus un algorithme efficace de recherche dans un ensemble d'éléments d'une hiérarchie.
Pour cet algorithme tous les noeuds sont comparables 1 à 1 avec un des 5 résultats ci-dessus. J'ai bien compris qu'il est question d'atteignabilité (reachability).

Ce que je comprends plus mal c'est le genre de relation d'ordre à laquelle j'ai affaire.
Notez que les relation à gauche de et à droite de sont transitives.
Puisque tous les noeuds sont comparables 1 à 1 alors c'est un ordre total ?
Ça paraît bizarre pour une relation d'atteignabilité.
À quel genre d'ordre j'ai vraiment affaire