Abstract FR:

Depuis plusieurs decennies les decompositions de graphes ont ete largement etudiees, en particulier comme des outils destines a mettre en uvre le paradigme diviser pour resoudre. Ici, nous nous interessons a des decompositions dont le point commun est le suivant: identifier des ensembles d'elements d'un graphe qui ont un comportement similaire vis a vis du reste du graphe. Ces ensembles sont appeles ensembles de decomposition. Nous formalisons et etudions un concept central en theorie de la decomposition: la notion de permutation factorisante. Il s'agit d'une permutation sur les sommets ou les arcs du graphe qui respecte la decomposition de ce dernier en ensembles de decomposition. Nous illustrons son interet dans le cadre de plusieurs decompositions: nous montrons que calculer la decomposition par substitution est equivalent a calculer une permutation factorisante. En utilisant la theorie de la decomposition par substitution, nous proposons une nouvelle decomposition: la decomposition en blocs des graphes d'heritage. Les graphes d'heritage (appeles aussi hierarchies d'heritage) sont les graphes orientes sans circuits possedant un plus grand et un plus petit element. Ils modelisent des relations souvent presentes dans les langages a objets ou en representation de connaissances. Nous proposons des algorithmes de calcul de cette decomposition, la aussi bases sur le calcul d'une permutation factorisante