Abstract FR:

Un graphe g est dit 2-arete-connexe si entre chaque paire de sommets de g, il existe au moins deux chaines arete-disjointes. Si les aretes sont munies d'un systeme de poids, et si s est un ensemble de sommets distingues de g, le probleme du sous-graphe steiner 2-arete-connexe de g est de determiner un sous-graphe 2-arete-connexe contenant s, de poids minimum. Ce probleme a des applications dans les domaines des telecommunications et de transport. Dans cette these nous etudions une approche polyedrale pour ce probleme. Dans une premiere partie, nous etudions le polyedre associe a ce probleme. Nous donnons une description lineaire complete de ce polyedre quand le graphe est serie-parallele. Nous discutons par la suite de certains polyedres lies au polytope des sous-graphes steiner 2-arete-connexes. Nous examinons tout particulierement le polytope du voyageur de commerce steiner et nous en donnons une description lineaire complete dans la classe des graphes serie-paralleles. Dans la deuxieme partie, nous etudions une methode de coupes pour le probleme du sous-graphe 2-arete-connexe (ou tous les sommets de s ont le meme comportement). Dans un premier temps nous etudions la famille de contraintes dites de partition. En utilisant un algorithme recent de queyranne pour determiner le minimum d'une fonction sous-modulaire symetrique, nous montrons que le probleme de separation associe a ces contraintes peut etre resolu en temps polynomial. Ces contraintes sont utilisees par la suite dans un algorithme de coupes et branchement pour resoudre certaines instances du probleme du sous-graphe 2-arete-connexe. La meme approche est aussi utilisee pour resoudre des instances du probleme du voyageur de commerce. Les resultats experimentaux montrent que les contraintes de partition sont tres efficaces pour resoudre ces problemes