Si je considère :
• l'ensemble des intervalles d'entiers, comme par exemple les intervalles [2,5] et [3,4]
• la relation d'inclusion ⊆ est une relation réflexive, antisymétrique et transitive, c'est une relation d'ordre partiel dans l'ensemble des intervalles d'entiers
• quelle structure de données correspond à cet ordre partiel, comment puis-je la caractériser
Ce que je veux dire c'est qu'un arbre binaire correspond à un ordre total (sur les entiers).
Avec l'inclusion d'intervalles d'entiers je peux construire (à coup sûr) toutes les structures arborescentes.
J'arrive aussi à construire quelques treillis (lattice), par exemple le treillis :
J'arrive également à construire quelques graphes dirigés, par exemple le digraphe :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 [1,5] / \ [1,4] [2,5] \ / [2,4]
D'une manière plus générale j'aimerais bien savoir quelle est précisément la structure de donnée engendrée par cet ordre partiel.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 [1,5] [2,6] / \ / [1,4] [2,5] \ / [2,4]
L'ensemble des graphes dirigés acycliques ?
Un sous-ensemble des graphes dirigés acycliques ? Mais alors lequel ?
Sachant que ce que je recherche au bout du compte c'est un algorithme qui, étant donnée une structure, soit capable de l'étiqueter avec des intervalles d'entiers. Chaque sommet ayant son étiquette unique dans toute la structure.
(normalement c'est une question pour le forum Algorithmes , mais c'est aussi bien ici, vous ne trouvez pas ?)
Partager