Structures arborescentes : problèmes
algorithmiques et combinatoires
Thèse de doctorat en informatique -
LaBRI,
Université Bordeaux I
Directeur : Serge Dulucq
Résumé.
La première partie de ce mémoire est consacrée à
l'énumération de diverses familles de structures arborescentes, en
général selon le nombre de sommets. Les trois premiers chapitres
sont consacrés à l'étude des arborescences de Cayley telles que
la racine est inférieure à ses fils et des arborescences
alternantes. La plupart de nos résultats sont prouvés
bijectivement. Nous nous intéressons ensuite aux arborescences
coloriées, et plus particulièrement à la formule d'inversion de
séries formelles multivariées de Good-Lagrange. Nous donnons une
nouvelle preuve bijective d'une variante de cette formule et utilisons
cette preuve pour prouver combinatoirement diverses formules
d'énumération de structures arborescentes et en déduire des
algorithmes de génération aléatoire pour ces structures
(notamment les cactus planaires). Nous concluons cette première
partie par un chapitre consacré aux constellations : en combinant
notre preuve de la formule de Good-Lagrange et la conjugaison
d'arborescences (due à Bousquet-Mélou et Schaeffer), nous prouvons
bijectivement une formule (nouvelle) pour l'énumération de
constellations selon le nombre de sommets et de faces.
Dans la seconde partie, nous étudions le problème de la recherche
de motifs dans une arborescence, en utilisant une structure de
données classique pour les mots : l'arborescence des suffixes. Nous
proposons notamment un algorithme de recherche de motifs dans une
arborescence, basé sur un codage d'une arborescence par des mots et
sur l'utilisation de l'arborescence des suffixes d'un de ces mots, qui
semble avoir de bonnes propriétés expérimentales. Nous concluons
en étendant la notion d'arborescence des suffixes des mots aux
arborescences et en décrivant un algorithme de construction pour
cette structure.
Mémoire :