Abstract FR:

Soient g = (v, e) un graphe et r , z v + un vecteur types de connexite associes aux sommets. Un sous-graphe est dit arete-fiable si entre chaque paire de sommets u, v de v, il existe au moins minr(u), r(v) chaines arete-disjointes. Si les aretes sont munies de poids, le probleme de conception de reseaux fiables consiste a determiner un sous-graphe arete-fiable de g de poids minimum. Ce probleme a des applications dans les domaines des telecommunications et des transports. Dans cette these, nous etudions une approche polyedrale pour ce probleme. Tout d'abord, nous montrons que le polytope associe aux solutions de ce probleme, esndp(g, r), est completement caracterise par les contraintes triviales et les contraintes de coupe quand le graphe g est serie-parallele et les types de sommets tous pairs. Comme consequence, nous obtenons un algorithme polynomial pour resoudre le probleme dans ce cas. Dans une deuxieme partie, nous considerons le probleme quand r , 1, 2 v. Nous montrons que le probleme de separation des inegalites dites de partition est polynomial. Nous ramenons ce probleme a la minimisation d'une fonction sous-modulaire. Il est egalement montre que ces contraintes avec les contraintes triviales et les contraintes de coupe suffisent pour decrire le polytope esndp(g, r) dans les graphes serie-paralleles. Ce resultat est ensuite etendu au cas ou r , k, k + 1 v, avec k impair. Des contraintes generalisant les contraintes dites de sp-partition sont alors utilisees dans cette caracterisation. Par la suite, nous examinons le polytope esndp(g, r) lorsque r , 0, 1 v ainsi que le polytope des arbres steiner qui lui est etroitement lie. Nous introduisons une nouvelle classe d'inegalites valides pour ces polytopes. Cette classe