Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

Le problème de trouver un transversal de circuits de cardinalité minimale dans un graphe orienté est l’un des problèmes NP-difficiles classiques définis par Karp en 1972. Il consiste à identifier un sous-graphe acyclique à partir d’un graphe donné en enlevant le moins de sommets possible. L’ensemble de sommets enlevés constitue alors un transversal de circuits de cardinalité minimale (TCCM). Un graphe peut posséder plusieurs transversaux de circuits de même cardinalité minimale. Pour pouvoir énumérer et enregistrer la famille de tous les ensembles de solutions (TCCM) d’un graphe, il est indispensable d’utiliser une structure de données permettant de les stocker implicitement et de manière compacte afin d’optimiser l’espace mémoire occupé par la famille et de bien gérer les sommets redondants. Dans cette perspective, nous introduisons une structure de données notée 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 mémoire, nous présentons la définition et l’implémentation de la structure de base des arbres et/ou, ainsi que la description et la mise en oeuvre des différents modificateurs, requêtes et opérations qui peuvent être appliqués à cette structure dans un contexte d’énumération. Nous terminons notre travail par l’introduction d’un algorithme permettant la construction efficace d’un arbre et/ou représentant tous les TCCM d’un graphe orienté.