Après une brève introduction aux concepts de base de la théorie des graphes, de la théorie de la complexité et de celle de la combinatoire polyédrique, cet ouvrage se centre sur l'étude de problèmes combinatoires possédant une propriété de "décomposition", c'est-à-dire tels que chacun d'eux puisse être décomposé en plusieurs sous-problèmes distincts dont les solutions permettent de reconstruire la solution du problème initial. Pour ce type de problèmes, une méthode générale conduisant à une formulation du problème sous forme de programmation linéaire est décrite et appliquée à plusieurs problèmes bien connus de la théorie des graphes (coupe maximum, ensemble stable de poids maximum, arbre de Steiner…) restreints à des classes de graphes particulières.
Un second champ d'application, celui de la composition de polytopes monotones, est ensuite exploré, menant à une généralisation et à l'unification de plusieurs résultats connus, faisant de cet ouvrage une des premières monographiques traitant de composition de polytope de manière détaillée.

La méthodologie utilisée simplifie, unifie et généralise des résultats épars dans la littérature et permet d'en trouver des nouveaux.

Etudiants du 3e cycle, enseignants, chercheurs.

Introduction et préliminaires - Propriété des faces projetées - Polytopes associés à des graphes définis par composition - Arbres et arborescences sur un 2-arbre - Monotonisation de polytopes - Composition de systèmes d'indépendants - Bibliographie - Notations - Glossaire.