Le probleme de trouver un transversal de circuits de cardinalite minimale dans un graphe oriente est l'un des problemes NP-difficiles classiques definis par Karp en 1972. Il consiste a identifier un sous-graphe acyclique a partir d'un graphe donne en enlevant le moins de sommets possible. L'ensemble de sommets enleves constitue alors un transversal de circuits de cardinalite minimale (TCCM).;Un graphe peut posseder plusieurs transversaux de circuits de meme cardinalite minimale. Pour pouvoir enumerer et enregistrer la famille de tous les ensembles de solutions (TCCM) d'un graphe, il est indispensable d'utiliser une structure de donnees permettant de les stocker implicitement et de maniere compacte afin d'optimiser l'espace memoire occupe par la famille et de bien gerer les sommets redondants. Dans cette perspective, nous introduisons une structure de donnees notee arbre et/ou, qui est un arbre dans lequel les noeuds internes sont des connecteurs logiques (, et -) et les feuilles sont des valeurs de l'ensemble de solutions.;Dans ce memoire, nous presentons la definition et l'implementation de la structure de base des arbres et/ou , ainsi que la description et la mise en oeuvre des differents modificateurs, requetes et operations qui peuvent etre appliques a cette structure dans un contexte d'enumeration. Nous terminons notre travail par l'introduction d'un algorithme permettant la construction efficace d'un arbre et/ou representant tous les TCCM d'un graphe oriente.
展开▼
