Abstract FR:

Dans cette thèse, nous considérons une approche polyédrale pour certains problèmes de connexité dans les graphes, ayant des applications dans la conception des réseaux de télécommunication fiables. Dans le premier chapitre, nous introduisons des nouvelles classes d'inégalités valides pour le polytope des sous-graphes k-arête connexes kECSP(G) et nous donnons des conditions nécessaires et des conditions suffisantes pour que ces inégalités définissent des facettes de ce polytope. Dans le second chapitre, nous caractérisons complètement le polytope kECSP(G) dans les graphes série-parallèles, ainsi que dans une autre classe de graphes généralisant la classe de Halin. Nous donnons également une description complète du polytope des sous-graphes Steiner k-arête connexes kSECSP(G, S) dans les graphes série-parallèles quand k est pair. Le troisième chapitre est consacré à l'étude des graphes dits parfaitement k-arête connexes, c'est-à-dire les graphes pour lesquels le polytope kECSP(G) est donné par les contraintes triviales et les contraintes de coupes. Nous étudions la structure des points extrêmes du polytope donné par ces contraintes. Et nous introduisons des nouvelles classes de graphes parfaitement k-arête connexes. Dans le quatrième chapitre, nous étudions le polytope des sous-graphes Steiner connexe 1SECSP(G, S) et le polytope de l'arbre Steiner STP(G, S). Nous introduisons une nouvelle classe d'inégaliés valides pour ces deux polytopes. En utilisant des procédures de construction de facettes de 1SECSP(G, S), nous caractérisons le polytope 1SECSP(G, S) dans des classes particulières de graphes. Par la suite, nous établissons une relation entre le polytope 1SECSP(G, S) et le dominant de l'arbre Steiner. Ceci nous permet de donner une description complète de ce dernier dans certaines classes de graphes